Blatt2

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?
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 → ∞).
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?
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?
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?
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?
b) genau eine Lösung?
Bitte wenden
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.
b) keiner der Plätze bleibt leer.
c) keiner der Plätze wird doppelt besetzt (”keine Kollision”)
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