Technische Universität München Sommersemester 2024
School of Computation, Information and Technology Übungsblatt 1
Lehrstuhl für Algorithmen und Komplexität 19. April 2024
Prof. Dr. Susanne Albers
Sebastian Schubert
Diskrete Wahrscheinlichkeitstheorie
Abgabetermin: 29. April 2024, 9 Uhr, Moodle
Tutoraufgabe 1
Die drei Rennpferde Anastasia, Beatrix und Cameron treten in einem Rennen gegenein-
ander an. Konstruieren Sie einen diskreten Wahrscheinlichkeitsraum für den Ausgang des
Rennens, sodass die Ereignisse Anastasia erreicht das Ziel vor Beatrix“, Beatrix erreicht
” ”
das Ziel vor Cameron“ und Cameron erreicht das Ziel vor Anastasia“ jeweils mit einer
”
Wahrscheinlichkeit größer als 1/2 eintreten.
Hinweis: Sie dürfen vereinfachend davon ausgehen, dass es keinen Gleichstand zwischen
den Pferden gibt.
Tutoraufgabe 2
Bei einer Forschungsreise durch Afrika fällt der Biologin Alison auf, dass Zebras mit
einer geraden Streifenzahl doppelt so häufig vorkommen wie Zebras mit einer ungeraden
Streifenzahl. Sei En das Ereignis, dass ein zufällig ausgewähltes Zebra genau n Streifen
hat. Modellieren Sie einen diskreten Wahrscheinlichkeitsraum, der dem Ereignis En für alle
n ∈ N eine positive Wahrscheinlichkeit zuordnet und der gleichzeitig Alisons Beobachtung
entspricht. Begründen Sie die Korrektheit Ihrer Konstruktion.
Tutoraufgabe 3
Der Konditor Alfred möchte für einen prestigeträchtigen Backwettbewerb m Blaubeer-
muffins zubereiten. Dazu gibt er n Blaubeeren in den Muffinteig und teilt diesen nach
gründlichem Rühren gleichmäßig auf m Formen auf. Angenommen jede Blaubeere kommt
mit der gleichen Wahrscheinlichkeit in jeden der m Muffins.
(a) Mit welcher Wahrscheinlichkeit enthält Alfreds i-ter Muffin keine Blaubeeren?
(b) Damit ein Muffin ein echter Blaubeermuffin ist, muss er mindestens eine Blaubeere
enthalten. Sei E das Ereignis, dass alle m Muffins echte Blaubeermuffins sind. Finden
Sie mit Hilfe der Siebformel einen Ausdruck zur Berechnung von Pr[E].
(c) Angenommen Alfred backt sechs Muffins. Bestimmen Sie mit einem Taschenrechner
oder Computer die Mindestanzahl an Blaubeeren, die Alfred in den Teig geben muss,
sodass Pr[E] > 9/10.
1
Hausaufgabe 1 (4 Punkte)
Wir betrachten ein Glücksrad, das mit den natürlichen Zahlen von 1 bis 150 beschriftet
ist. Berechnen Sie die Wahrscheinlichkeit, dass das Glücksrad auf einer Zahl stehen bleibt,
die
(a) durch 4 oder 9 (oder beides) teilbar ist
(b) eine Quersumme größer als 3 hat.
Wir nehmen dabei an, dass jede Zahl mit der gleichen Wahrscheinlichkeit auftritt.
Hausaufgabe 2 (4 Punkte)
Nach einem langen Spieleabend stehen Agathe und Balthasar allein am U-Bahnhof Ma-
rienplatz, von wo alle 10 Minuten eine U-Bahn abfährt. Leider sind die Züge so überfüllt,
dass immer nur eine Person einsteigen kann. Dies gelingt jeder Person am Bahnsteig mit
der gleichen Wahrscheinlichkeit. Zusätzlich treffen in der Zeit bis zur nächsten U-Bahn
jeweils zwei neue Personen an der Haltestelle ein. Bestimmen Sie die Wahrscheinlichkeit,
mit der Agathe
(a) in die n-te U-Bahn
(b) spätestens in die n-te U-Bahn
einsteigen kann, wobei n ∈ N sei.
Hausaufgabe 3 (6 Punkte)
Die DWT-Tutorin Angelika betreut eine Übungsgruppe, in der n Hausaufgaben ohne
Namen abgegeben wurden. Nach der Korrektur teilt Angelika die namenlosen Blätter
daher zufällig an die n vergesslichen Studierenden aus. Angenommen alle Zuordnungen
von Hausaufgaben an Studierende sind gleich wahrscheinlich. Mit welcher Wahrschein-
lichkeit gibt Angelika niemandem die eigene Hausaufgabe zurück? Wie verhält sich diese
Wahrscheinlichkeit für n → ∞?
Hinweis: Benutzen Sie die Siebformel aus der Vorlesung und machen Sie sich mit der
Reihendarstellung der Exponentialfunktion vertraut.
Hausaufgabe 4 (6 Punkte + 3 Bonuspunkte)
Arabella würfelt n faire Würfel, deren Seiten jeweils mit den Augenzahlen von 1 bis 6
beschriftet sind. Sei En,k das Ereignis, dass die Summe aller Augenzahlen von Arabellas
Wurf k ergibt. Konstruieren Sie eine Formel für die Berechnung von Pr[En,k ]. Gehen Sie
dabei wie folgt vor.
(a) Stellen Sie einen Zusammenhang zwischen Pr[En,k ] und den Koeffizienten des Po-
lynoms f (x) = (x + x2 + x3 + x4 + x5 + x6 )n in ausmultiplizierter Form her. Eine
kurze Begründung ist ausreichend.
(b) (Bonusaufgabe) Sei 0 < x < 1. Beweisen Sie mithilfe der geometrischen Reihe und
dem allgemeinem binomischen Lehrsatz die folgende Identität.
∞ X n
X
i n n + j − 1 n+6i+j
f (x) = (−1) x .
j=0 i=0
i j
2
(c) Leiten Sie aus der ersten und zweiten Teilaufgabe eine Formel für die Berechnung
von Pr[En,k ] ab.
(d) Bestimmen Sie mit einem Taschenrechner oder Computer den exakten Wert von
Pr[E15,62 ]. Zur Selbstkontrolle: Pr[E15,62 ] ≈ 2/100