Technische Universität München Sommersemester 2024

School of Computation, Information and Technology Übungsblatt 5

Lehrstuhl für Algorithmen und Komplexität 17. Mai 2024
Prof. Dr. Susanne Albers
Sebastian Schubert

Diskrete Wahrscheinlichkeitstheorie

Abgabetermin: 27. Mai 2024, 9 Uhr, Moodle

Tutoraufgabe 1
Das Chamäleon Antonio begegnet jeden Tag X Insekten, wobei X mit Parameter
λ > 0 Poisson-verteilt ist. Allerdings gelingt es Antonio lediglich mit Wahrscheinlich-
keit 0 < p ≤ 1, ein Insekt einzufangen. Sei Y die Gesamtzahl der gefangenen Insekten.
Bestimmen Sie die Verteilung von Y sowie den Erwartungswert und die Varianz.
Hinweis: Nutzen Sie die Reihendarstellung der Exponentialfunktion.

Tutoraufgabe 2
Für die Fahrt zu einem wichtigen Geschäftstermin bestellt Annemarie ein Taxi. Laut
Taxiunternehmen soll das Taxi erwartungsgemäß in µ Minuten ankommen. Sei X eine
geometrisch verteilte Zufallsvariable, die Annemaries Wartezeit in Minuten angibt. Nach
i Minuten wird Annemarie ungeduldig und ruft das Taxiunternehmen an, um nach ihrer
verbleibenden Wartezeit X − i zu fragen. Zeigen Sie, dass ihre erwartete verbleibende
Wartezeit immer noch µ Minuten beträgt, dass also E[X − i | X > i] = µ gilt.

Tutoraufgabe 3
Die lokale Erdmännchenpopulation eines afrikanischen Nationalparks besteht aus n Tie-
ren. Während ihrer Forschungsreise möchte die Biologin Alison die Erdmännchen genauer
erforschen. Hierfür muss sie insgesamt m unterschiedliche Tiere fangen und untersuchen.
Hat Alison ein Erdmännchen eingefangen und untersucht, so entlässt sie es wieder in die
Wildnis, bevor sie das nächste fängt. Wir nehmen an, dass Alison jedes der n Erdmänn-
chen mit der gleichen Wahrscheinlichkeit und unabhängig von vorherigen Untersuchungen
fängt.

(a) Sei Xi eine Zufallsvariable, die angibt, wie oft das i-te Erdmännchen untersucht
wird. Berechnen Sie den Erwartungswert von Xi .

(b) Da die Erdmännchen nicht untersucht werden wollen, senden sie eine zufällige De-
legation der Größe k ≥ m, die sich Alison stellt. Der Rest versteckt sich. Ange-
nommen, jede Delegation der Größe k ist gleich wahrscheinlich und Alison möchte
weiterhin m verschiedene Tiere untersuchen. Wie sollte k gewählt werden, sodass
jedes Erdmännchen seine erwartete Anzahl an Untersuchungen minimiert?

1
Hausaufgabe 1 (4 Punkte)
Am nächsten Tag bestellt Annemarie zur Sicherheit gleich n Taxis bei unterschiedlichen
Anbietern und steigt in das Taxi ein, das am frühesten eintrifft. Die Wartezeit in Minuten
für das i-te Taxi (1 ≤ i ≤ n) sei Xi , eine geometrisch verteilte Zufallsvariable mit Parame-
ter pi . Die Zufallsvariablen Xi seien unabhängig. Zeigen Sie, dass Annemaries Wartezeit
Y = min{X1 , . . . , Xn } geometrisch verteilt ist, und bestimmen Sie den Parameter.
Hinweis: Betrachten Sie Pr[Y > y] für y ∈ N0 .

Hausaufgabe 2 (5 Punkte)
Amelie veranstaltet beim Sommerfest eine Lotterie mithilfe eines Glücksrads. Auf dem
Glücksrad sind insgesamt 50 gleich große Felder. Dabei gibt es nur bei genau einem Feld
den Gewinn, die restlichen 49 Felder sind Nieten. Angenommen alle Drehungen sind un-
abhängig, wobei jedes Feld wird mit gleicher Wahrscheinlichkeit gedreht wird.

(a) Aus Erfahrung schätzt Amelie, dass 200 Personen an ihrem Glücksrad drehen wollen.
Sei X die Anzahl der Gewinne bei 200 Drehungen. Bestimmen Sie die Dichte, den
Erwartungswert und die Varianz von X.

(b) Approximieren Sie den Wert Pr[X ≥ E[X]] mithilfe der Poisson-Verteilung.

(c) Tatsächlich bereitet Amelie genau vier Gewinne vor und lässt so lange Drehungen
zu, bis keine Gewinne mehr vorhanden sind. Sie dürfen vereinfachend annehmen,
dass eine unendliche große Anzahl an Personen am Glücksrad drehen möchten. Sei
Y die Anzahl der Drehungen, bis alle vier Gewinne verteilt werden. Bestimmen Sie
die Dichte und den Erwartungswert von Y .

Hausaufgabe 3 (6 Punkte)
Der Kekshändler Arsatius kauft n Kekse zu einem Stückpreis c und möchte sie zum Preis 2c
weiterverkaufen. Sei X eine Zufallsvariable, die angibt, wie viele Kekse Arsatius verkaufen
kann. Der Nettogewinn ist somit gegeben durch Yn = c · (2 · min{X, n} − n). Bestimmen
Sie die Anzahl Kekse, die Arsatius einkaufen sollte, um seinen erwarteten Nettogewinn zu
maximieren. Gehen Sie dabei wie folgt vor:

(a) Angenommen, Arsatius kauft anstatt n Keksen einen Keks mehr. Zeigen Sie, dass die
erwartete Änderung seines Gewinns gegeben ist durch E[Yn+1 −Yn ] = c·(1−2·FX (n)).

(b) Zeigen Sie, dass das kleinste n, das die Ungleichung FX (n) ≥ 1/2 erfüllt, den erwar-
teten Gewinn von Arsatius maximiert.

(c) Sei X Poisson-verteilt mit Parameter λ = 250. Bestimmen Sie mit einem Taschen-
rechner oder Computer den maximalen Nettogewinn in Abhängigkeit von c, den
Arsatius erwarten kann.

2
Hausaufgabe 4 (5 Punkte)
Ein Floh bewegt sich zufällig auf dem Zahlenstrahl der Menge Z. Dabei hüpft er von einer
Zahl i mit Wahrscheinlichkeit p nach rechts (auf i + 1), andernfalls nach links (auf i − 1).
Dies geschieht unabhängig von den bisherigen Sprüngen. Der Floh startet auf Position 0.

1−p p

i−3 i−2 i−1 i+1 i+2 i+3

(a) Sei Xn die Position nach n Sprüngen. Bestimmen Sie den Erwartungswert und die
Varianz von Xn .
Hinweis: Betrachten Sie die Indikatorvariablen Yi für 1 ≤ i ≤ n, wobei Yi = 1 ist gdw. der
i-te Sprung nach rechts geht.

(b) Wann verlässt der Floh erwartungsgemäß das Intervall [−1, 1] zum ersten Mal?