Lösung 2

J. W. GOETHE UNIVERSITÄT
N. KISTLER
SS 2016
BLATT 2
ELEMENTARE STOCHASTIK
Abgabe: Montag 2/5, in der Vorlesung
Aufgabe 1.
a) Wieviele 0-1 Folgen der Länge 2n gibt es mit n Nullen und n Einsen?
Lösung. Wähle Positionen der 0en ⇒ 2n
Folgen.
n
b) Ein ”gewöhnlicher Irrfahrter” auf Z setzt Schritte von +1 und −1 nach Manier eines fairen
Münzwurf aneinander. Wie wahrscheinlich ist es, dass er, wenn er im Ursprung startet,
nach 2n Schritten wieder im Ursprung ist? Geben Sie zuerst das exakte Resultat an, und
approximieren Sie es dann mit Stirling (n → ∞).
Lösung. Der Irrfahrer muss genau n mal nach rechts und n mal nach links ⇒ 2n
Möglichkeiten
n
(siehe a mit 0 entspricht Schritt nach rechts und 1 entspricht Schritt nach links). Jeder Weg
2n
hat Wkeit 21 .
2n 2n
2n √
4nπ
2n
1
2n
1
1
e 2n
·
·
p=
≈
·
=√
n
2
2nπ
e
n
2
nπ
Aufgabe 2. Sei 1 ≤ b ≤ n.
a) Wieviele Permutationen π der Länge n gibt es, deren die 1 enthaltender Zyklus die Länge
b hat und für die π(1) = 2 gilt?
Lösung. Schreibe den Zyklus als Z(1), ..., Z(b). Es gilt nach Voraussetzung 1 = Z(1) →
2 = Z(2) und Z(b) → Z(1). Für Z(i) mit 1 < i < b ist der Nachfolger frei aus [n] \
{1, 2, Z(3), ..., Z(i)} wählbar. Die Kardinalität dieser Menge beträgt n − i. Außerdem
können die n − b Elemente die nicht in dem Zykel liegen frei permutiert werden. Es folgt
dass die Anzahl der gesuchten Zykel
(n − 2) · ... · (n − (b − 1)) · (n − b)! = (n − 2)!
beträgt.
b) Wieviele Permutationen der Länge n gibt es, deren die 1 enthaltender Zyklus die Länge b
hat und auch die 2 enthält?
Lösung. Für k ≤ b gibt es aufgrund der Symmetrie genau so viele Permutationen der
Länge b die die 1 enthalten mit der 2 an k-ter Stelle wie welche mit der 2 an 2-ter Stelle.
Also gilt
|{der 1-enthaltende Zyklus der Länge b enthält auch die 2}|
=
b
X
|{der 1-enthaltende Zyklus der Länge b hat die 2 an k-ter Stelle}|
k=2
(1)
=
b
X
|{der 1-enthaltende Zyklus der Länge b hat die 2 an 2-ter Stelle}|
k=2
=(b − 1)(n − 2)!
c) Wie wahrscheinlich ist es, dass in einer rein zufällige Permutation der Länge n die Zahlen
1 und 2 im selben Zyklus liegen?
Lösung. Sei E das gesuchte Ereignis und definiere
Eb = {der die 1 enthaltende Zyklus hat Länge b und enthält die 2}
Dann gilt
n
E = ∪˙ b=2
und es folgt
P(E) =
n
X
P(Eb ) =
b=2
(2)
=
n
X
b−1
b=2
n−1
(n − 2)! X
n!
n!
(n − 2)!
b
b=1
(n − 2)! (n − 1)n
1
=
=
n!
2
2
Aufgabe 3. Sei Z = (Z1 , Z2 ) uniform verteilt auf dem Einheitsquadrat [0, 1]×[0, 1]. Mit welcher
Wkeit besitzt die zufällige Gleichung x2 + Z1 x + Z2 = 0
a) zwei reelle Lösungen?
Lösung. Die (zufälligen) Lösungen sind:
Z1
x1 = − +
2
(3)
Z1
x2 = − −
2
s
s
Z1
2
2
Z1
2
2
− Z2
− Z2
2
Das Argument der Wurzel ist genau dann echt positiv, falls Z21 − Z2 > 0. Da Z =
(Z1 , Z2 ) uniform auf dem Einheitsquadrat verteilt ist, ist die Wkeit dieses Ereignisses nach
2
dem Transformationssatz gleich dem Lebeguemaß von {(x, y) ⊂ [0, 1]2 | x4 > y}
Z
[0,1]2
Z
1 x 2 >y dλ =
(2)
1
0
Z
0
1
Z
1 x 2 >y dydx =
(2)
0
1
x2
1
dx =
4
12
b) genau eine Lösung?
Lösung. Nun muss das Argument der Wurzel verschwinden. Das Lebeguemaß von {(x, y) ⊂
2
[0, 1]2 | x4 = y} und damit die Wkeit des Ereignisses sind 0.
Aufgabe 4. Sei Z = (Z1 , . . . , Zr ) eine uniform verteilte Besetzung von r Plätzen mit n Objekten.
Berechnen Sie die Wkeit folgender Ereignisse:
a) Platz 1 bleibt leer.
Lösung. Der Zustandsraum ist (siehe Seite 11):
S = {(k1 , ...kr )|k1 + ... + kr = 0}
,
n+r−1
|S| =
n
Die günstigen Elemente sind die aus
A = {(0, k2 , ..., kr )|k2 + ... + kr = 0}
,
n + (r − 1) − 1
|A| =
n
Also gilt
p=
r−1
|A|
=
|S|
n+r−1
Lösung. Für n < r ist die Wkeit 0. Sei also r ≤ n. Dann gilt
n−r+r−1
n−1
A = {(k1 , ..., kr )|ki > 0, k1 + ... + kr = 0} ,
=
n−r
n−r
(Wähle zunächst r Einsen fest und verteile die restlichen n − r beliebig.
p=
n! · (n − 1)!
(n − r)! · (n + r − 1)!
Lösung. Für n > r ist die Wkeit 0. Sei n ≤ r
A = {(k1 , ..., kr )|ki ≤ 1, k1 + ... + kr = n}
n
,
|A| = r
(Wähle n Plätze die besetzt werden sollen)
p=
r! · (r − 1)!
(r − n)! · (n + r − 1)!
Desweiteren (challenging!): ab welcher Grössenordnung von n = n(r) kommt es für grosse r
mit merklicher Wahrscheinlichkeit zu Kollisionen? Was man sich unter merklich vorstellen soll:
finden Sie ein möglichst grosses α, sodass für r → ∞ und n(r) = o(rα ) gilt
lim Pr,n(r) [es kommt zu Kollisionen] = 0.
r→∞
Wir benutzen dabei die klein-oh Notation: an = o(bn ) ⇐⇒ limn→∞ an /bn = 0 (an ist ”viel
kleiner” als bn .)

Download Report