Sticker (Stochastik)

4 Antworten

Vom Fragesteller als hilfreich ausgezeichnet

Erwartungswert = 62,911945 Packungen (exakt: 42822903 / 680680). Also kann man im Durchschnitt erwarten, nach circa 63 Packungen alle 18 Sticker bekommen zu haben.


Rechenweg.

Ich reduziere das Problem auf das folgendes äquivalente Problem,

  • Es gibt s (= 18) verschiedene Sorten
  • Es handelt sich um eine unendliche Folge (X[n]), wobei jedes X[n] ∈ {1; 2; …; s}. Die Zufallsvariablen sind paarweise unabhängig und identisch verteilt. (Die Verteilung ist die gleichmäßige Verteilung auf s-Elemente.)
  • Die zu betrachtende Zufallsvariable ist N := die erste Zahl n, so dass alle Werte 1 bis s unter X[1], …, X[n] vorhanden sind.
  • Diese „Wartezeit“ lässt sich in s Komponenten zerlegen:
    • N = N[1] + N[2] + … + N[s], wobei
    • N[1] = Zeitpunkt, wann erst eine Sorte aufgetaucht ist. Nenn diese Sorte S[1].
    • N[2] = Wartezeit ab N[1]+1, wann erst eine neue Sorte S[2] ≠ S[1] auftaucht.
    • N[3] = Wartezeit ab N[1]+N[2]+1, wann erst eine neue Sorte S[3] ≠ S[1], S[3]≠S[2] auftaucht.
    • … N[s] = Wartezeit ab N[1]+N[2]+…+N[s–1]+1, wann erst eine neue Sorte S[s] ≠ S[1], S[s]≠S[2], …, S[s] ≠ S[s–1] auftaucht.
  • Es gilt E(N) = ∑[k = 1 bis s] aus E(N[k])
  • Es gilt N[1] = 1
  • Es gilt N[k+1] ~ Exponentielverteilt: P(N[k+1]=n) = (k/s)^n · (1 – k/s)
    • Also E(N[k+1]) = 1 / (1 – k/s) = s / (s – k)

Daraus ergibt sich

  • E(N) = ∑[k = 0 bis s–1] aus s / (s – k)
    • = s · ∑[k = 1 bis s] aus 1 / k
    • = s · H(s)

wobei (H(n)) die harmonische Reihe ist.††

Hier eine Tafel der Erwartungszeiten:

 s  E(N) für s Sorten
======================
 1  1 
 2  3
 3  5,5
 4  8,333333
 5  11,416667
 6  14,7
 7  18,15
 8  21,742857
 9  25,460714
10   29,289683
11  33,218651
12  37,238528
13  41,341739
14  45,521873
15  49,773435
16  54,091664
17  58,472393
18  62,911945

†† Es gilt H(n) ~ log(n) + γ, wobei γ eine Konstante zwischen 0 und 1 ist. Dementsprechend E(N) ~ s·(log(s) + γ) für s groß.

Um dieses Ergebnis zu ergänzen: man kann mit 62,911945 ± O(21,272927) Packungen rechnen. Also sollte man ca. 62,9 + 21,3 · z Packungen kaufen, wobei z = Anzahl der Standardabweichungen.


Rechenweg.

Das müsste die geometrische Verteilung heißen. Aber Namen sind vollkommen egal zu den Ergebnissen. Hier eine Berechnung der Varianz:

  • N = ∑[k=1 bis s] aus N[k], wobei die N[…] paarweise unabhängig sind.
    • also Var(N) = ∑[k=1…s] aus Var(N[k]).
    • N[k+1] ~ Geom(Erfolg=1–k/s) für k=0 bis s–1
    • also Var(N[k+1]) = (k/s) / (1–k/s)² = s·k / (s–k)²

Also

  • Var(N) = ∑[k=0…s–1] aus Var(N[k+1])
    • = ∑[k=0…s–1] aus s·k / (s–k)²
    • = ∑[k=1…s] aus s·(s–k) / k²
    • = s²·∑[k=1…s] aus 1 / k² – s·∑[k=1…s] aus 1/k
    • = s²·H(s, 2) – s·H(s, 1),

wobei H(n, a) = ∑[k=1…n] aus 1/n^a.

Noch eine Tafel:

 s   E(N)    σ(N)  für s Sorten
===============================
 1   1,000   0,000
 2   3,000   1,414
 3   5,500   2,598
 4   8,333   3,801
 5  11,417   5,017
 6  14,700   6,244
 7  18,150   7,479
 8  21,743   8,718
 9  25,461   9,963
10  29,290  11,211
11  33,219  12,462
12  37,239  13,716
13  41,342  14,971
14  45,522  16,229
15  49,773  17,488
16  54,092  18,748
17  58,472  20,010
18  62,912  21,273
1

http://img5.fotos-hochladen.net/uploads/vert809dxic43l.png

Hier die exakte Verteilung (berechnet durch die Faltung aus der Verteilungen der 18 geometrisch verteilter Zufallsvariabler). Es gilt für die Untersuchung Min{n : P(Anzahl ≤ n) ≥ p}:

 p        n
=============
80,0%     78
90,0%     91
95,0%    103
99,0%    132
99,9%    172

Also, um mit z. B. 99% Sicherheit alle Sticker zu bekommen, sollte man 132 Packungen kaufen. Wenn man ca. 80 kauft, gibt es nur eine Garantie von 80%.

1

Vielen Dank schonmal ich habe diesen Weg ebenfalls gebraucht. Ich hätte da nurnoch die Frage, auf was sich die Konstante y bezieht bzw. was sie bedeutet. lg Mf

0

Das ist kein Ypsilon, sondern der griechische Buchstabe, gamma. Es ist für den Beweis nicht maßgebend, es ist ne Konstante und wurde nur für eine Näherung der Lösung erwähnt.

0

Klingt nach ner Scherzfrage. Wenn du 18 Packungen hast, wobei in jeder ein anderer Sticker ist, musst du alle 18 Packungen haben, um alle 18 Sticker zu bekommen.

Ja, auf den ersten Blick klingt blöd — habe auch etwas ähnliches gedacht. Man muss jedoch genauer lesen: die Aufgabe hat eine nicht triviale Lösung — obwohl sie gar nicht so schwierig ist.

0

Wie viele Packungen gibt es insgesamt bzw. werden produziert? Gibt es darüber Informationen?

ich soll eine Formel dazu herleiten die beschreibt wie viele Packungen ich in etwa brauche damit ich alle 18 verschiedene Sticker bekomme.

Was denn nun? Eine Formel für die Wahrscheinlichkeit, alle Packungen zu bekommen oder die Anzahl an Packungen, um eine gewisse vorgegebene Wahrscheinlichkeit zu überschreiten?

Ne es soll keine Scherzfrage sein Ich muss lediglich mit der Formel raus bekommen wie viele Packungen ich kaufen muss um alle 18 verschiedene Sticker zu bekommen es gibt auch keine Auskunft darüber wie viel produziert wird.Jedoch wird von jedem Sticker die gleiche Anzahl produziert

Zu welcher Wahrscheinlichkeit willst du alle bekommen? Zu 100 Prozent!? Also ich hab das Gefühl, dass die Aufgabe irgendwie anders gemeint ist, aber sei's drum:

Wenn die Produktion der 18 verschiedenen Sticker (diskret) gleichverteilt ist, dann muss ja die Gesamtproduktion ein Vielfaches von 18 sein, also g := 18*n, n∈N

Um dann auf jeden Fall von jedem einen zu bekommen, brauchst du dann 17n+1 Päckchen, denn im äußersten Fall ziehst du mit deinen ersten 17n Päckchen nur Sticker von 17 Sorten und übrig sind dann im verbleibenden Stapel n Päckchen mit dem dir fehlenden Sticker. Also musst du noch einen kaufen.

So seh ich das, aber glaube kaum, dass die Aufgabe so gemeint ist.

1

Was möchtest Du wissen?