Das Sammelbildproblem

Wer Sammelbilder in ein Album einklebt möchte wissen, wie viele Sammelbilder (m) man kaufen muss, um einen vollständigen Satz (n) zu erhalten. Häufig wird hierfür die Formel für die Wahrscheinlichkeit P(γ) mit m=n*Hn angegeben. Dabei ist m die Anzahl der gekauften Sammelbilder und n die Anzahl der verschiedenen Bilder einer Serie. Hn wird als harmonische Serie bezeichnet und ist definiert als: . Weiterhin gilt folgender Zusammenhang: γ=(Hn-ln(n)).  γ wird als Euler-Mascheroni-Konstante bezeichnet und beträgt für große n ≈0,5772... Für 42 Sammelbilder ist Hn etwa 181,7. Weiterführende Informationen findet man im Netz auch unter „Coupon Collector’s Problem“ oder unter „Problem der vollständigen Serie“.

 

Der Wahrscheinlichkeitsbaum

 

Zunächst einige Grundüberlegungen:

  1. das erste Sammelbild kann (m=1) kann immer eingeklebt werden. Somit ist die Position (n=1; m=1) immer mit "1" belegt (Wahrscheinlichkeit 100%)
  2. das zweite Sammelbild (m=2) kann mit einer Wahrscheinlichkeit von das gleiche wie das erste sein. Position (n=1; m=2) mit einer Wahrscheinlichkeit von P(1;2)=P(1;1)* =0,0238
  3. das zweite Sammelbild (m=2) kann zum ersten unterschiedlich sein mit der Wahrscheinlichkeit , die Position (n=2; m=2) hat eine Wahrscheinlichkeit von P(2;2)=P(1;1)* =0,976
  4.  

  1. Somit kann von Position (n=1; m=1) immer nur Pos. (n=1; m=2) wie in Pkt. 2 oder Pos.(n=2; m=2) wie in Pkt. 3 erläutert erreicht werden. Es gilt: Von einer beliebigen Position im Wahrscheinlichkeitsbaum kann immer nur die Position unmittelbar darunter (wenn das Sammelbild schon vorhanden ist) oder  unten rechts (wenn das Sammelbild vorher noch nicht existierte) die nächste sein.

Hier ein Beispiel für einen möglichen Weg durch den Wahrscheinlichkeitsbaum, von sechs gekauften (m=6) Sammelbildern sind zwei doppelt (n=4).

Die Berechnung in Excel:

Wie bereits erläutert gibt es für jeden Schritt nur zwei Möglichkeiten (neues oder bereits vorhandenes Sammelbild). Daher kann jede mögliche Position auch nur von zwei davor liegenden Positionen aufgerufen werden. Im Beispiel wird Pos(3;4) entweder von Pos(2;3) oder von Pos(3;3) erreicht. Andere Varianten gibt es nicht.

Die Wahrscheinlichkeit in Zelle P(3;4) ergibt sich aus der Summe zweier Einzelwahrscheinlichkeiten, hier für n=42:

von links oben: P(2;3)*40/42=0,06972789*40/42=0,066407514

von oben: P(3;3)*3/43=0,92970522*3/42=0,066407515

Beide Ergebnisse addiert: 0,13281503

Hier eine fertige Excel-Tabelle für n=42, wie sie beispielsweise auf die Sammelbildaktionen zu Fußballevents der "längsten Praline der Welt"  angewendet werden kann.

In der Spalte für n=42 ergeben sich die Wahrscheinlichkeiten für eine vollständige Serie, die als Funktion P(n,m) dargestellt werden kann

 

Man erkennt, dass etwa 172 Sammelbilder gekauft werden müssen, um mir 50-prozentiger Wahrscheinlichkeit eine vollständige Serie zu erhalten. Im nachfolgenden Diagramm ist die Einzelwahrscheinlichkeit einer vollständigen Serie in Abhängigkeit der gekauften Sammelbilder dargestellt.

 

Programm zur Berechnung der Wahrscheinlichkeiten

Die Ergebnisse aus der Excel-Tabelle können mit diesem Programm verifiziert werden.

 

 

Es werden per Zufallszahlen die Ereignisse für den Kauf der Sammelbilder simuliert. Je größer die Anzahl der Sammler gewählt wird, umso genauer ist das Ergebnis. Zum nachvollziehen finden Sie hier den Quellcode und hier die Umsetzung in VB.Net 2008.

 

 

 

schreibfaul1 <at> t-online.de