Fakultät für Mathematik 20. Mai 1998 Universität Regensburg

Übungen zur Vorlesung

Einführung in die Wahrscheinlichkeitstheorie

Blatt 3: Klassische Wahrscheinlichkeitsverteilungen

Aufgabe 11: Beim Spiel “Mensch ärgere Dich nicht” darf die Figur eines Spielers erst dann auf das Feld, wenn dieser eine Sechs würfelt.

a) Wie groß ist die Wahrscheinlichkeit, daß ein Spieler nach zehn Runden immer noch nicht draußen ist?

b) Wieviele Runden müssen vier Spieler mindestens spielen, bis mit 90 Prozent Wahrscheinlichkeit alle vier draußen sind?

Aufgabe 12: Für n ≥ 2 sei Ω = {0, 1}^{n} der n-te Bernoulli-Raum mit Bernoulli-Verteilung P zum Parameter p ∈ [0, 1]. Wir betrachten die Ereignisse A_{i} = {X_{i} = 1} für i = 1, …, n und B = {(ω_{1}, …, ω_{n}) ∈ Ω | ω_{1} + ⋯ + ω_{n} ungerade }.

a) Berechnen Sie P (B). Stellen Sie P (B) mit Hilfe der Werte der Binomialverteilung dar und folgern Sie eine Formel für Binomialkoeffizienten.

b) Welche der Familien F_{1} = {A_{1}, …, A_{n}}, F_{2} = F_{1}∪{B} und F_{3} = {A_{2}, …, A_{n}, B} sind unabhängig?

Aufgabe 13: Der Korrektor einer Staatsexamensklausur stellte in 10 Prozent der Fälle einen Fehler in der Lösung einer Aufgabe fest. Ein Nachkorrektor fand heraus, daß dabei eine fehlerhafte Lösung mit 94 Prozent Wahrscheinlichkeit als solche erkannt wurde, und eine korrekte Lösung wurde mit 4,2 Prozent Wahrscheinlichkeit als falsch bezeichnet.

a) Wie groß ist die Wahrscheinlichkeit dafür, daß eine als falsch bezeichnete Lösung tatsächlich falsch ist?

b) Mit welcher Wahrscheinlichkeit kommt eine fehlerhafte Lösung unerkannt durch?

c) Arbeitet das Korrekturverfahren zufriedenstellend?

d) Wie ändern sich die Ergebnisse von a), b) und c), wenn es einen unabhängigen Zweitkorrektor gibt, der mit derselben (Un-) Zuverlässigkeit arbeitet, und wenn nur Lösungen verworfen werden, die von beiden Korrektoren bemängelt wurden?

Aufgabe 14: Sei (Ω, P) der Stufenraum, der das Urnenmodell von Polya beschreibt, sei ω = (ω_{1}, …, ω_{n}) ∈ Ω, und sei k = #{i | ω_{i} = w}.

a) Beweisen Sie die Formel

P (ω) = \frac{w(w+c)···(w+(k−1)c) · s(s+c)···(s+(n−k−1)c)}{(w+s)(w+s+c)···(w+s+(n−1)c}

b) Folgern Sie, daß für jede Permutation σ von {1, …, n} die Gleichung P (ω) = P ((ω_{σ(1)}, …, ω_{σ(n)})) gilt.

Aufgabe 15: (Das Josephus-Problem)

Während des jüdischen Aufstands gegen Rom (70 n. Chr.) wurden n Juden in einer Höhle eingeschlossen. Um der Sklaverei zu entgehen, vereinbarten sie sich gegenseitig wie folgt zu vernichten. Sie stellten sich entlang eines Kreises auf und numerierten sich mit 1 bis n durch. Beginnend mit Nummer k, wurde jede k-te Person niedergemacht, wobei sich der Kreis sofort wieder schloß. Der spätere Geschichtsschreiber Flavius Josephus stellte sich so auf, daß er als letzter übrig blieb, schreckte dann aber vor dem vereinbarten Selbstmord zurück.

a) Zeigen Sie, daß man die Nummer der s-ten eliminierten Person mit folgendem Algorithmus finden kann:

1) Setze x_{0} := 1 + k(n − s) und q := \frac{k}{k−1}.

2) Für i = 1, 2, … berechne x_{i} := ⌈qx_{i−1}⌉, wobei ⌈y⌉ für y ∈ ℝ die kleinste ganze Zahl ≥ y bezeichne.

3) Ist a = max{x_{i} | x_{i} ≤ kn}, so gib kn + 1 − a als Ergebnis zurück.

b) Schreiben Sie eine Maple-Prozedur Josephus(n, k, s), die die Nummer der sten umgebrachten Person ermittelt und ausgibt. Berechnen Sie Josephus(40, 7, 40), die Nummer, die angeblich dem historischen Fall entspricht.

c) Beweisen Sie, daß im Fall k = 2 der letzte Überlebende die Nummer 1 + 2n − 2^{m} hat, wobei m = ⌊log_{2}(n)⌋ + 1 ist. (Für y ∈ ℝ sei dabei ⌊y⌋ die größte ganze Zahl ≤ y.)

d)^{∗} Die Nummer einer bestimmten Person bei der ersten Zählung sei y_{1}, bei der zweiten Zählung y_{2}, etc. Beweisen Sie y_{i+1} = y_{i} + n − ⌊\frac{y_{i}}{k} ⌋, falls y_{i+1} definiert ist. Zeigen Sie hiermit y_{i} = ⌊\frac{(y_{i+1}−n)k−1}{k−1}⌋ und folgern Sie einen schnellen Algorithmus zur Berechnung von Josephus(n, k, s). Implementieren Sie diesen.