Solution dwt endterm-online PDF

Preview

Summary

LösungsvorschlagLehrstuhl für Algorithmen und Komplexität Fakultät für Informatik Technische Universität MünchenEsolution Sticker mit SRID hier einklebenHinweise zur Personalisierung: - Ihre Prüfung wird bei der Anwesenheitskontrolle durch Aufkleben eines Codes personalisiert. - Dieser enthält ledig...

Description

Lehrstuhl für Algorithmen und Komplexität Fakultät für Informatik Technische Universität München Hinweise zur Personalisierung:

ch la g

Esolution Sticker mit SRID hier einkleben

• Ihre Prüfung wird bei der Anwesenheitskontrolle durch Aufkleben eines Codes personalisiert. • Dieser enthält lediglich eine fortlaufende Nummer, welche auch auf der Anwesenheitsliste neben dem Unterschriftenfeld vermerkt ist. • Diese wird als Pseudonym verwendet, um eine eindeutige Zuordnung Ihrer Prüfung zu ermöglichen.

Diskrete Wahrscheinlichkeitstheorie (Online) IN0018 / Endterm-Online Prof. Dr. Susanne Albers

Bearbeitungshinweise

Datum: Uhrzeit:

Dienstag, 3. August 2021 14:15 – 16:15

vo rs

Klausur: Prüfer:

Lö su ng s

• Diese Klausur umfasst 20 Seiten mit insgesamt 6 Aufgaben. Bitte kontrollieren Sie jetzt, dass Sie eine vollständige Angabe erhalten haben. • Die Gesamtpunktzahl in dieser Prüfung beträgt 40 Punkte. • Als Hilfsmittel sind zugelassen:

– ein handgeschriebener Spickzettel (DIN A4, beide Seiten) – ein analoges Wörterbuch Deutsch ↔ Muttersprache ohne Anmerkungen

• Unterschreiben Sie in dem obigen Unterschriftenfeld. Damit versichern Sie, dass Sie – alle Antworten selbstständig und ohne Austausch mit Dritten angefertigt haben,

– keine anderen als die erlaubten Hilfsmittel benutzt haben und

– unter Ihrem eigenen Namen abgeben.

• Es werden nur solche Ergebnisse gewertet, bei denen der Lösungsweg erkennbar ist. Begründen Sie alle Antworten, solange es in der jeweiligen Teilaufgabe nicht ausdrücklich anders vermerkt ist. • Schreiben Sie weder mit roter / grüner Farbe noch mit Bleistift.

– Seite 1 / 20 –

Aufgabe 1

Gewinnspiel (6.5 Punkte)

Sie nehmen an folgendem Gewinnspiel teil: Zuerst ziehen Sie einen Ball beschriftet mit einer Zahl aus einer Urne. Die gezogene Zahl gibt an, wie viele Lose Sie anschließend ohne Zurücklegen aus einem Lostopf ziehen dürfen. In der Urne befinden sich drei Bälle beschriftet mit den Zahlen 1, 2 und 3. Im Lostopf befinden sich genau ein Gewinnlos und sieben Nieten. Angenommen Sie ziehen jeden Ball bzw. jedes noch übrige Los mit gleicher Wahrscheinlichkeit.

1 2 3

a) Zeigen Sie, dass Sie das Gewinnlos mit einer Wahrscheinlichkeit von

1 4

ziehen.

Die verschiedenen Varianten dieser Aufgabe unterscheiden sich in der Anzahl m der Nieten im Lostopf. Seien A1 , A2 und A2 die Ereignisse, dass der Ball mit Zahl 1, 2 bzw. 3 aus der Urne gezogen wurde. Es gilt Pr[A1 ] = Pr[A2 ] = Pr[A3 ] = 13 . Sei G das Ereignis, dass das Gewinnlos aus dem Lostopf gezogen wird. Nach dem Satz der totalen Wahrscheinlichkeit gilt

ch la g

0

Pr[G] = Pr[G | A1 ] · Pr[A1 ] + Pr[G | A2 ] · Pr[A2 ] + Pr[G | A3 ] · Pr[A3 ] .

vo rs

G | Ai] für i ∈ { 1, 2, 3 } bestimmt werden. Beim Ziehen von j Losen ohne Es muss nun nur noch  Pr[  Zurücklegen gibt es m+1 verschiedene Ziehungen (ohne Beachtung der Reihenfolge), die alle gleich j m wahrscheinlich sind. Des Weiteren gibt es j−1 verschiedene Ziehungen, bei denen das Gewinnlos j − gezogen wird (wir ziehen die anderen 1 Lose aus den restlichen m ). Mit dem Laplace-Prinzip folgt Pr[G] = Pr[G | A1 ] · Pr[A1 ] + Pr[G | A2 ] · Pr[A2 ] + Pr[G | A3 ] · Pr[A3 ] m 

m m 1 1 1 1 2 = · + m+1  · + m+1 · 3 3 3 2 3 2 3 2 1 . + + = = m+1 3(m + 1) 3(m + 1) 3(m + 1) 0 m+1  1

 

Lö su ng s

Varianten:

 

Anzahl Nieten m

Pr[G]:

5

1/3

6

2/7

7

1/4

8

2/9

– Seite 2 / 20 –

b) Ihr Kommilitone berichtet Ihnen, dass er das Gewinnlos gezogen hat. Mit welcher Wahrscheinlichkeit hat er zuvor den Ball mit Zahl 2 aus der Urne gezogen? Sind die Ereignisse »Der Ball mit Zahl 2 wird aus der Urne gezogen« und »Das Gewinnlos wird gezogen« stochastisch unabhängig?

0 1

Gesucht ist Pr[A2 | G]. Durch Umformen ergibt sich Pr[A2 | G] =

Pr[G | A2 ] · Pr[A2 ] Pr[A2 ∩ G] = = Pr[G] Pr[G]

2 1 m+1 · 3 2 m+1

=

1 . 3

ch la g

Wir haben also gezeigt, dass Pr[ A2 | G] = Pr[A2 ] gilt. Durch Umformen erhalten wir Pr[ A2 ∩ G] = Pr[A2 ] · Pr[G], woraus die Unabhängigkeit der Ereignisse A2 und G folgt. Dieses Ergebnis ist für alle Varianten gleich.

vo rs

c) Wie viele zusätzliche Bälle beschriftet mit der Zahl 3 müsste man mindestens in die Urne hinzugeben, damit die Wahrscheinlichkeit, mit der das Gewinnlos gezogen wird, mindestens 1/3 ist?

Lö su ng s

In dieser Teilaufgabe soll die kleinste Anzahl an zusätzlichen Bällen beschriftet mit der Zahl 3 3 bestimmt werden, sodass die Wahrscheinlichkeit das Gewinnlos zu ziehen mindestens m+2 ist. Angenommen es werden N − 1 Bälle beschriftet mit der Zahl 3 in die Urne hinzugegeben. Damit verändern sich die Wahrscheinlichkeiten der Ereignisse A1 ,A2 und A3 zu Pr[A1 ] = Pr[A2] = N1+2 und Pr[A3 ] = NN+2 . Entsprechen erhalten wir nun 1 1 2 3 N 1 · + · · + N +2 m+1 N +2 m+1 N +2 m+1 ! 3N + 3 3 = ≥ . (N + 2)(m + 1) m+2

Pr[G] =

Durch Umformungen erhalten wir

3(N + 1) N +1 3 3 3N + 3 = = · ≥ (N + 2)(m + 1) (N + 2)(m + 1) N +2 m+1 m+2 m+1 N +1 . ≥ ⇐⇒ N +2 m+2

Wir können folgern, dass N + 1 ≥ m+ 1 gelten muss, oder N ≥ m. Wir müssen demnach mindestens N − 1 = m − 1 Bälle beschriftet mit der Zahl 3 in Urne 1 hinzugeben. Varianten: Anzahl Nieten m

Benötigte Bälle:

5

4

6

5

7

6

8

7

– Seite 3 / 20 –

0 1 2

Aufgabe 2

Forschungsreise (5.5 Punkte)

Der Biologin Alison begegnen auf ihrer Forschungsreise an einem Tag X Wolpertinger. Die Dichte der diskreten Zufallsvariablen X ist gegeben durch   1

fX (k) = ln(5) 0 1

 k 4 ·1 5

für k ∈ N,

k

sonst.

a) Berechnen Sie die Wahrscheinlichkeit, dass Alison an einem Tag mindestens zwei Wolpertinger sieht. Die Varianten dieser Aufgabe unterscheiden sich durch den Parameter p ∈ { 21 , 23 , 43 , 45 } in der Dichtefunktion  k ·p   1 für k ∈ N, k ln 1/(1−p) fX (k) =  0 sonst.

ch la g

0

·

Die gesuchte Wahrscheinlichkeit Pr[X ≥ 2] rechnen wir über das Gegenereignis und erhalten Pr[X ≥ 2] = 1 − Pr[X = 1] = 1 −

Pr[X ≥ 2]

1/2

2/3

3/4

vo rs

Parameter p

p  . ln 1/(1 − p)

1−

1 2 ln(2)

1−

2 3 ln(3)

3 4 ln(4)

1−

4/5

1−

4 5 ln(5)

0

b) Zeigen Sie, dass für alle s ∈ [0,1] die wahrscheinlichkeitserzeugende Funktion von X gegeben ist durch

1

ln 1 − (4/5)s . GX (s) = − ln(5) 

Lö su ng s

Hinweis: Sie können ohne Beweis verwenden, dass



P∞

k=1 x

k

/k = ln 1/(1 − x) für x ∈ [0, 1). 



Es soll in dieser Teilaufgabe gezeigt werden, dass GX (s) = −

ln(1 − ps)  . ln 1/(1 − p)

Wir setzen die Definition der wahrscheinlichkeitserzeugenden Funktion an und rechnen: GX (s) = E[sX ] =

∞ ∞ X X sk · fXi (k) = sk · k=1

k=1

∞ X (ps)k pk 1 1 · . · =  k ln 1/(1 − p) ln 1/(1 − p) k=1 k



Für die hintere Reihe verwenden wir den Hinweis mit x = ps, wobei wir feststellen, dass ps ∈ [0, 1), da s ∈ [0, 1] und p ∈ (0, 1). Wir erhalten GX (s) =

ln(1 − ps) ln(1/(1 − ps)) ,   =−  ln 1/(1 − p) ln 1/(1 − p)

wobei wir im letzten Schritt ln 1/(1 − x) = − ln(1 − x) verwenden. 

Parameter p 1/(1-p) GX



1/2

2/3

3/4

4/5

2

3

4

5

s) − ln(1−1/2 ln(2)

−

ln(1−2/3 s) ln(3)

– Seite 4 / 20 –

−

ln(1−3/4 s) ln(4)

−

ln(1−4/5 s) ln(5)

c) Die Dauer von Alisons Forschungsreise beträgt Y Tage, wobei Y eine mit Parameter λ = ln(5) Poissonverteilte Zufallsvariable ist. Alison begegnet am i-ten Tag ihrer Reise Xi Wolpertingern, wobei alle Xi identisch verteilt zu X sind. Die Zufallsvariablen Y, X1 , X2 , . . . sind unabhängig. Wie vielen Wolpertingern begegnet Alison auf ihrer gesamten Forschungsreise erwartungsgemäß? Je nach Variante ist Y Poisson-verteilt mit Parameter λ = ln 1/(1 − p) . Da die Dauer von Alisons Forschungsreise Y Tage beträgt, lässt sich die Gesamtzahl Z an getroffenen Wolpertinger schreiben P als Z = Yi=1 Xi. Da die Zufallsvariablen X1 , . . . , XY und Y unabhängig sind, können wir Satz 77 anwenden. Da Y Poisson-verteilt ist mit Parameter λ, lautet die wahrscheinlichkeitserzeugende Funktion GY (s) = eλ(s−1). Es folgt 

ln(1 − ps)  −1 GZ (s) = GY (GX (s)) = exp λ −  ln 1/(1 − p)

!!

ch la g



= exp − ln(1 − ps) − ln 1/(1 − p) 





,

wobei der letzte Schritt aus der Wahl von λ = ln 1/ (1 − p ) folgt. Diesen Term können wir nun wie folgt vereinfachen: 



GZ (s) = exp − ln(1 − ps) − ln 1/(1 − p) 





=

Um den Erwartungswert von Z zu bestimmen leiten wir GZ ab:

1 1 . · (−p) · (1 − p) = p(1 − p) · (1 − ps)2 (1 − ps)2

vo rs

G′Z (s) = −

1 · (1 − p) . 1 − ps

Abschließend erhalten wir den Erwartungswert durch Einsetzen von s = 1: E[Z] = G′Z (1) = p(1 − p) · 1/2

2/3

Lö su ng s

Parameter p 1/(1-p)

λ

E[Z]

p 1 = 2 (1 − p) 1−p 3/4

4/5

2

3

4

5

ln(2)

ln(3)

ln(4)

ln(5)

1

2

3

4

– Seite 5 / 20 –

0 1 2 3

Aufgabe 3

Quadratisches Beet (6 Punkte)

Landwirt Alfred legt ein quadratisches Beet an. Der Flächeninhalt (in Quadratmetern) ist durch die mit Parameter λ = 1/5 exponentialverteilte Zufallsvariable X gegeben.

1 2

a) Bestimmen Sie die Dichte der Seitenlänge S des quadratischen Beetes. 1 Die Varianten dieser Aufgabe unterscheiden sich in der Wahl des Parameters λ ∈ { 15 , 61, 18 , 10 }.√Sei X ∼ Exp(λ). Da X der Flächeninhalt eines quadratischen Beets ist, gilt für die Seitenlänge S = X . √ Für S ≥ 0 ist FS (s) = Pr[ X ≤ s] = FX (s2 ). Also

FS (s) =

(

1 − e−λs

2

0

für s ≥ 0

ch la g

0

sonst.

Durch Ableiten erhalten wir nun die Dichtefunktion von S : fS (s) =

(

2λse−λs 0

Varianten:

für s ≥ 0 sonst

Verteilung FS (s)

Dichte fS (s)

vo rs

Parameter λ

2

−s2 /5

für s ≥ 0

2 −s2 /5 5 se

für s ≥ 0

1/5

1−e

1/6

1 − e−s

2 /6

für s ≥ 0

1 −s2 /6 3 se

für s ≥ 0

1/8

1 − e−s

2 /8

für s ≥ 0

1 −s2 /8 4 se

für s ≥ 0

2 /10

für s ≥ 0

1 −s2 /10 5 se

für s ≥ 0

1 − e−s

Lö su ng s

1/10

– Seite 6 / 20 –

b) Alfreds Nachbar Bernd möchte auch ein Beet anlegen. Der Flächeninhalt Y (in Quadratmetern) von Bernds Beet ist ebenfalls exponentialverteilt mit Parameter λ = 1/5 und unabhängig von X. Berechnen Sie die Dichte der Summe Z der Flächeninhalte der beiden Beete und geben Sie E[Z] an.

0 1 2

Für jede Variante ist Y identisch verteilt zu X, das heißt ebenfalls exponentialverteilt mit gleichem λ . Es gilt Z = X + Y , wobei X und Y unabhängig sind. Demnach können wir die Dichte von Z mithilfe von Satz 105 (Faltung) bestimmen. Für z ≥ 0 gilt: fZ (z) =

Z ∞

−∞

fX (x) · fY (z − x) dx =

Z z 0

−λx

λe

−λ(z −x)

· λe

2 −λz

dx = λ e

·

Z z

3

1 dx = λ2 ze−λz .

0

Parameter λ

Dichte FZ (z) 1 −z/5 25 ze

1/6

1 −z/6 36 ze

1/8

1 −z/8 64 ze

1/10

1 −z/10 100 ze

für z ≥ 0 für z ≥ 0 für z ≥ 0

Erwartungswert E[Z ]

10

12

vo rs

1/5

ch la g

Da WX = WY = R+ 0 , gilt offensichtlich fZ (z) = 0 für z < 0. Außerdem folgt aus der Linearität des Erwartungswerts 1 1 2 E[Z] = E[X + Y ] = E[X] + E[Y ] = + = . λ λ λ Varianten:

Lö su ng s

für z ≥ 0

16

20

c) Alfred und Bernd legen zusammen insgesamt 25 Beete an, deren Größe jeweils unabhängig und identisch zu X bzw. Y verteilt sind. Berechnen Sie die erwartete Größe des kleinsten Beetes. Je nach Variante war eine andere Anzahl n an gemeinsamen Beeten von Alfred und Bernd gegeben. Seien X1 , . . . , Xn die Flächeninhalte. Es gilt, dass jedes Beet unabhängig anderer Beete exponentialverteilt ist mit Parameter λ. Sei nun K = min{X1 , . . . , Xn } die Größe des kleinsten Beetes. Nach Satz 102 ist K ist exponentialverteilt mit Parameter λK = nλ. Also ist E[K] = 1/(nλ). Varianten: Parameter λ

Anzahl n

Erwartungswert E[Z ]

1/5

25

1/5

1/6

24

1/4

1/8

24

1/3

1/10

20

1/2

– Seite 7 / 20 –

0 1

Aufgabe 4

Weltraummission (7 Punkte)

Astronaut Alex bereitet sich auf eine 200 Tage lange Weltraummission vor, für die mehrere Sauerstoffflaschen benötigt werden. Die Anzahl an Tagen, die eine Flasche benutzt werden kann bevor sie verbraucht ist und ausgetauscht werden muss, ist geometrisch verteilt mit einem Erwartungswert von 2 Tagen und unabhängig von den anderen Flaschen. Sobald eine Sauerstoffflasche vollständig verbraucht wurde, wird sie am Ende des Tages durch eine neue ersetzt. 0 1

a) Angenommen es besteht ein unendlich großer Vorrat an Sauerstoffflaschen. Zeigen Sie, dass der Erwartungswert und die Varianz der Anzahl an vollständig verbrauchten Flaschen A während der gesamten Weltraummission gegeben ist durch E[A] = 100 bzw. Var[A] = 50. Die Varianten dieser Aufgabe unterscheiden sich in der Länge a der Weltraummission in Tagen. Seien T1 , T2 , . . . die Anzahl Tage, die die verschiedenen Sauerstoffflaschen durchhalten. Es gilt, dass T1 , T2 , . . . alle unabhängig geometrisch verteilt sind mit Parameter p = 12 . Hierbei entspricht p der Trefferwahrscheinlichkeit im Sinne der geometrischen Verteilung. Gesucht ist die Anzahl A der verbrauchten Flaschen während der gesamten a Tage langen Weltraummission. Gemäß Vorlesung gilt: Wenn die zeitlichen Abstände Ti der Treffer geometrisch verteilt ist, so ist die Anzahl der Treffer A in einem festen Zeitraum binomialverteilt. Die entsprechenden Parameter sind p = 12 für die Trefferwahrscheinlichkeit und a für die Anzahl an Versuchen. Alternativ kann dies auch direkt berechnet werden: Aufgrund der Gedächtnislosigkeit der geometrischen Verteilung ist die Wahrscheinlichkeit, dass an einem bestimmten Tag die aktuell benutzte Flasche i leer wird, gleich Pr[Ti = 1] = p(1 − p )0 = p. Entsprechend ist die Wahrscheinlichkeit, dass die aktuelle Flasche nicht leer wird gleich 1 − p. Die Wahrscheinlichkeit Pr[A = k] für k ∈ {0 , . . . , a} entspricht nun der Wahrscheinlichkeit, dass die aktuelle Flasche an genau k der insgesamt a Tage leer wird. An allen anderen Tagen wird die   Flasche nicht aufgebraucht. Da es ak Möglichkeiten für die Ausfalltage gibt, folgt

vo rs

3

ch la g

2

!

Lö su ng s

a k Pr[A = k] = p (1 − p)a−k k

für k ∈ {0, . . . , a}

Damit ist A binomialverteilt mit Parametern a und p = 12 . Der Erwartungswert von A ist demnach E[A] = a2 und die Varianz Var[A] = Varianten: Länge der Mission a

E[A]

Var[A]

120

60

30

160

80

40

200

100

50

240

120

60

– Seite 8 / 20 –

a 4.

b) Schätzen Sie die Wahrscheinlichkeit, dass die Anzahl der vollständig verbrauchten Flaschen mindestens den halben Wert der Varianz vom Erwartungswert abweicht, mithilfe der Chebyshev-Ungleichung nach oben ab. In Teilaufgabe a) haben wir gezeigt, dass E[A] = a2 und Var[A] = a4 gilt. Nun ist nach der Wahrscheinlichkeit gefragt, dass die Anzahl der verbrauchten Flaschen mindestens Var[A ]/2 vom Erwartungswert abweicht, also Pr [|A − E[A]| ≥ Var[A]/2]. Die Chebyshev-Ungleichung liefert. 4 8 Var[A] = = . (Var[A]/2)2 Var[A] a

Varianten:

ch la g

Pr [|A − E[A]| ≥ Var[A]/2] ≤

Länge der Mission a

Chebyshev-Ungleichung

120

Pr [|A − E[A]| ≥ 15] ≤ 152

160

Pr [|A − E[A]| ≥ 20] ≤

200

Pr [|A − E[A]| ≥ 25] ≤

240

Pr [|A − E[A]| ≥ 30] ≤

1 10

Lö su ng s

vo rs

2 25 1 15

– Seite 9 / 20 –

0 1

0 1 2

c) Jeden Tag während der Weltraummission schaut Alex aus dem Fenster und sieht dabei am i-ten 1 und Tag Si Sternschnuppen vorbeifliegen. Aus Erfahrung weiß Alex, dass für alle i ∈ [200] E[Si ] = 20 1 Var[Si] = 50 gilt und dass S1 , S2 , . . . , S200 unabhängig sind. Approximieren Sie die Wahrscheinlichkeit, dass Alex während der gesamten Weltraummission mehr als 7 Sternschnuppen sieht, mithilfe des Zentralen Grenzwertsatzes. Hinweis: Benutzen Sie die Tabelle der Standardnormalverteilung am Ende der Klausur.

"

ch la g

Je nach Variante war E [Si ] = 10a bzw. Var[Si ] = 4a gegeben. Sei S die Anzahl an Sternschnuppen, P die Alex während der gesamten a Tage langen Weltraummission sieht. Es gilt S = ai=1 Si. Gesucht ist Pr[S > 7] = 1 − Pr[S ≤ 7]. Aus dem zentralen Grenzwertsatz folgt 7 − a · E[Si ] S − a · E[Si ] ≤ p Pr [S ≤ 7] = Pr p a · Var[Si ] a · Var[Si ]   7 − 10 √ = Φ (−1.5) . =Φ 4

#

Nun benutzen wir die Identität Φ(−x) = 1 − Φ(x) und lesen aus der Tabelle ab

Pr[S > 7] = 1 − Pr[S ≤ 7] = 1 − (1 − Φ(1.5)) = Φ(1.5) = 0.933 .

Lö su ng s

vo rs

Dieses Ergebnis ist für alle Varianten gleich.

– Seite 10 / 20 –

Aufgabe 5

Dreiecksverteilung (7 Punkte)

Die Dichtefunktion einer kontinuierlichen Zufallsvariable X sei abhängig von einem Parameter c ∈ (0, 1) gegeben durch  x  für x ∈ [0, c]  2 c 1−x fc (x) = 2 1−c für x ∈ (c, 1]   0

sonst.

a) Zeigen Sie, dass die Funktion fc für alle Werte c ∈ (0, 1) eine zulässige Dichtefunktion ist.

 

0

sonst.

ch la g

Die Varianten die...