Der Frosch startet auf dem Startfeld Feld n und hüpft dann nach rechts bis zum Zielfeld Feld 0, wobei die Weite jedes Hüpfers gleichverteilt zufällig, aber mindestens 1 ist.
Aufgaben:
- Wieviele Möglichkeiten gibt es, vom Startfeld ins Zielfeld zu kommen?
- Wieviele Hüpfer braucht der Frosch im Durchschnitt von Startfeld bis ins Zielfeld?
- Was ist die durchschnittliche Sprungweite?
- Wie wahrscheinlich wird wird dabei das Feld k besucht?
- Wie wahrscheinlich braucht der Frosch genau h Hüpfer vom Startfeld bis ins Zielfeld?
- Wie oft im Schnitt springt der Frosch d Felder weit?
Animation mit Statistik
Achtung: Ändern der Startposition löscht die Statistik!
| #Hüpfer | Häufigkeit | Anteil |
|---|---|---|
| 1 | ||
| 2 | ||
| 3 | ||
| 4 | ||
| 5 | ||
| 6 | ||
| 7 | ||
| 8 | ||
| 9 | ||
| 10 | ||
| Feld | #Besuche | Prozent |
|---|---|---|
| 0 | ||
| 1 | ||
| 2 | ||
| 3 | ||
| 4 | ||
| 5 | ||
| 6 | ||
| 7 | ||
| 8 | ||
| 9 | ||
| 10 |
1. Zahl möglicher Sprungfolgen
Zum Aufwärmen: wieviele Möglichkeiten ⟪C_n⟫ hat der Frosch, vom Startfeld n zum Zielfeld 0 zu springen?
- Vom Feld 1 landet der erste Sprung im Ziel, es gibt also nur eine Möglichkeit.
⟪ C_1 = 1 = 2^0 ⟫
- Vom Feld 2 kann der Frosch das Feld 1 als Zwischenziel besuchen oder nicht,
bevor er im Ziel landet. Es gibt also 2 Möglichkeiten.
⟪ C_2 = 2 = 2^1 ⟫
- Vom Feld 3 kann der Frosch Feld 2 und Feld 1
jeweils als Zwischenziel besuchen oder nicht, bevor er im Ziel landet.
Es gibt also 2*2 gleich 4 Möglichkeiten.
⟪ C_3 = 4 = 2^2 ⟫
Allgemein gibt es bei Start auf Feld n genau n-1 mögliche Zwischenziele, die der Frosch jeweils besuchen kann oder nicht. Damit gilt:
(1) ⟪ C_n = 2^(n-1) ⟫
Der
hat die
Zweierpotenzen
entdeckt.
2. Durchschnittliche Anzahl der Sprünge
Wir bezeichnen die durchschnittliche Anzahl von Sprüngen von Feld ⟪n⟫ bis ins Ziel als Hüpfzahl ⟪H_n⟫.
Feld 0 ist das Ziel, die durchschnittliche Zahl von Sprüngen bis zu Ziel ist also ⟪0⟫:
(2) ⟪ H_0 = 0 ⟫
Von Feld 1 landet der Frosch mit dem ersten Sprung auf Feld 0, damit gilt:
⟪ H_1 = 1 + ( H_0 ) = 1/1 ⟫
Von Feld 2 landet der Frosch mit dem ersten Sprung mit gleicher Wahrscheinlichkeit auf Feld 0 oder Feld 1; die durchschnittliche Zahl der Sprünge ist also der erste Sprung plus der Durchschnitt aus ⟪H_0⟫ und ⟪H_1⟫:
⟪ H_2 = 1 + 1/2 * ( H_0 + H_1 ) = 3/2 ⟫
Auf Feld 3 haben wir drei Möglichkeiten:
⟪ H_3 = 1 + 1/3 * ( H_0 + H_1 + H_2 ) = 11/6 ⟫
Und so weiter:
⟪ H_4 = 1 + 1/4 * ( H_0 + H_1 + H_2 + H_3 ) = 25/12 ⟫
⟪ H_5 = 1 + 1/5 * ( H_0 + H_1 + H_2 + H_3 + H_4 ) = 137/60 ⟫
Wir verallgemeinern für Feld ⟪n⟫, wobei wir wegen (2)
die Summe mit ⟪i=1⟫ beginnen können.
Damit erhalten wir die Rekursionsformel:
(3) ⟪ H_n = 1 + 1/n * sum_(i=1)^(n-1) H_i if n ge 1⟫
Wir geben uns mit dieser rekursiven Definition nicht zufrieden und bestimmen die Beziehung zwischen den Werten ⟪H_n⟫ und ⟪H_(n+1)⟫.
Dazu formen wir (3) um:
(4) ⟪ H_n * n = n + sum_(i=1)^(n-1) H_i ⟫
Wir setzen für ⟪n⟫ den Wert ⟪n+1⟫ ein und trennen den letzten Wert der Summe ab:
⟪ H_(n+1) * (n+1) = (n+1) + sum_(i=1)^n H_i ⟫
(5) ⟪ H_(n+1) * (n+1) = (n+1) + sum_(i=1)^(n-1) H_i + H_n ⟫
⟪ H_(n+1) * (n+1) - H_n * n = 1 + H_n ⟫
und erhalten eine vereinfachte Rekursionsformel:
⟪ H_(n+1) * (n+1) = H_n * (n+1) + 1 ⟫
(6) ⟪ H_(n+1) = H_n + 1/(n+1) ⟫
Zusammen mit (2) ergibt sich daraus die Formel zur direkten Berechnung:
(7) ⟪ H_n = sum_(i=1)^n 1/i ⟫
Der
hat die
Harmonischen Zahlen
entdeckt.
Beobachtung: die Werte der Hn steigen nur sehr langsam an:
| n | Hn |
|---|---|
| 1 | 1.0000 |
| 2 | 1.5000 |
| 3 | 1.8333 |
| 4 | 2.0833 |
| 5 | 2.2833 |
| 6 | 2.4500 |
| 7 | 2.5929 |
| 8 | 2.7179 |
| 9 | 2.8290 |
| 10 | 2.9290 |
| n | Hn |
|---|---|
| 10 | 2.9290 |
| 100 | 5.1874 |
| 1 000 | 7.4855 |
| 10 000 | 9.7876 |
| 100 000 | 12.0901 |
| 1 000 000 | 14.3927 |
| 10 000 000 | 16.6953 |
| 100 000 000 | 18.9979 |
| 1 000 000 000 | 21.3005 |
| 10 000 000 000 | 23.6031 |
3. Was ist die durchschnittliche Sprungweite?
Die durchschnittliche Sprungweite ist die Entfernung n dividiert durch die durchschnittliche Anzahl an Sprüngen Hn. Letztere haben wir im vorhergehenen Abschnitt berechnet. Wir erhalten
(8) ⟪ W_n = n / H_n = n / (sum_(i=1)^n 1/i) ⟫
⟪ W_1 = 1 / H_1 = 1 / (1/1) = 1 ⟫
⟪ W_2 = 2 / H_2 = 2 / (1/1 + 1/2) = 2 / (3/2) = 4/3 ⟫
⟪ W_3 = 3 / H_3 = 3 / (1/1 + 1/2 + 1/3) = 3 / (11/6) = 18/11 ⟫
⟪ W_3 = 4 / H_4 = 4 / (1/1 + 1/2 + 1/3 + 1/4) = 4 / (25/12) = 48/25 ⟫
Der
hat das
Harmonische Mittel
der ersten n natürlichen Zahlen entdeckt.
| n | Wn |
|---|---|
| 1 | 1.0000 |
| 2 | 1.3333 |
| 3 | 1.6364 |
| 4 | 1.9200 |
| 5 | 2.1898 |
| 6 | 2.4490 |
| 7 | 2.6997 |
| 8 | 2.9435 |
| 9 | 3.1814 |
| 10 | 3.4142 |
| n | Wn |
|---|---|
| 10 | 3.4 |
| 100 | 19.3 |
| 1 000 | 133.6 |
| 10 000 | 1 021.7 |
| 100 000 | 8 271.2 |
| 1 000 000 | 69 479.5 |
| 10 000 000 | 598 970.6 |
| 100 000 000 | 5 263 740.7 |
| 1 000 000 000 | 46 947 295.5 |
| 10 000 000 000 | 423 673 761.2 |
4. Wie oft werden die einzelnen Felder besucht?
Wir bezeichnen Wahrscheinlichkeit, dass ein Zielfeld z von einem Startfeld s erreicht wird, als ⟪F_z(s)⟫.
Vom einem Startfeld s werden im nächsten Schritt mit gleicher Wahrscheinlichkeit ⟪1/s⟫ die Felder Feld s-1 bis Feld 0 erreicht.
Wenn das Startfeld gleich dem Zielfeld ist oder rechts davon liegt, ist keines dieser Felder das Zielfeld, und es ist auch von keinem dieser Felder das Zielfeld zu erreichen.
(9) ⟪F_z(s) = 0 if s le z⟫
Wenn das Startfeld s unmittelbar links vom Zielfeld z liegt (⟪s = z+1⟫), führen von den s Sprungmöglichkeiten nur eine ins Zielfeld und die anderen darüber hinaus. Die Wahrscheinlichkeit, das Zielfeld zu erreichen, ist also:
(10) ⟪F_z(s) = 1/(s) = 1/(z+1) if s = z+1⟫
Wenn das Startfeld s weiter links vom Zielfeld z liegt (⟪s ge z+2⟫), wird mit der Wahrscheinlichkeit ⟪1/s⟫ das Zielfeld erreicht, dazu mit einer Wahrscheinlichkeit von jeweils ⟪1/s⟫ die Felder t (⟪z lt t lt s⟫) zwischen dem Startfeld und dem Zielfeld, von denen das Zielfeld mit einer jeweiligen Wahrscheinlichkeit ⟪F_z(t)⟫ erreicht werden kann:
⟪F_z(s) = 1/s + (F_z(z+1))/s + (F_z(z+2))/s + ... + (F_z(s-2))/s + (F_z(s-1))/s ⟫
⟪F_z(s) = 1/s ( 1 + F_z(z+1) + F_z(z+2) + ... + F_z(s-2) + F_z(s-1) )⟫
Damit erhalten wir die Rekursionsformel:
(11) ⟪F_z(s) = 1/s ( 1 + sum_(t=z+1)^(s-1) F_z(t) ) if s ge z+2⟫
Wir geben uns mit dieser rekursiven Definition nicht zufrieden und bestimmen die Beziehung zwischen den Werten ⟪F_z(s)⟫ und ⟪F_z(s+1)⟫:
Dazu formen wir (11) um:
(12) ⟪F_z(s) * s = 1 + sum_(t=z+1)^(s-1) F_z(t)⟫
Wir setzen für ⟪s⟫ den Wert ⟪s+1⟫ ein und trennen den letzten Wert der Summe ab:
⟪F_z(s+1) * (s+1) = 1 + sum_(t=z+1)^(s) F_z(t)⟫
(13) ⟪F_z(s+1) * (s+1) = 1 + sum_(t=z+1)^(s-1) F_z(t) + F_z(s)⟫
Wir subtrahieren (12) von (13):
⟪F_z(s+1) * (s+1) - F_z(s) * s = F_z(s)⟫
Und formen um:
⟪F_z(s+1) * (s+1) = F_z(s) * (s+1)⟫
(14) ⟪F_z(s+1) = F_z(s) ⟫
Die Wahrscheinlichkeit, dass ein bestimmtes Feld erreicht wird, ist, sofern das Feld erreichbar ist, konstant und unabhängig vom Ausgangsfeld.
Mit (9) und (10) erhalten wir die Formel zur direkten Berechnung:
(15) ⟪F_z(s) = { ( F_z := 1/(z+1), if s gt z ), ( 0 , if s le z ) :}⟫
Der
hat die
Harmonische Folge
entdeckt.
5. Wahrscheinlichkeit für eine bestimmte Zahl von Sprüngen
Wir bezeichnen die Wahrscheinlichkeit, dass der Frosch von Feld n auf Feld 0 genau k Sprünge braucht, mit Pn,k.
- Von Feld 0 braucht der Frosch immer 0 Sprünge zu Feld 0:
(16) ⟪ P_(0,0) = 1 ⟫
- Von anderen Feldern ist Feld 0 nicht in 0 Sprüngen erreichbar:
(17) ⟪ P_(n,0) = 0 if n ge 1⟫
- Der Frosch braucht maximal so viele Sprünge wie die Nummer des Feldes,
auf dem er steht:
(18) ⟪ P_(n,k) = 0 if k gt n ⟫
- Von Feld n+1 erreicht der Frosch mit einem Sprung die Felder 0
bis n jeweils mit einer Wahrscheinlichkeit vom 1/(n+1).
Die Wahrscheinlichkeit, mit k Sprüngen das Ziel zu erreichen, ist also die gemittelte Wahrscheinlichkeit, von einem dieser Felder das Ziel mit k-1 Schritten zu erreichen:
(19) ⟪ P_(n+1,k) = 1/(n+1) sum_(i=0)^n P_(i,k-1) if n ge 1 ^^ 1 le k le n⟫
Diese Rekursionsformel lässt sich anders darstellen:
⟪ P_(n+1,k) = 1/(n+1) sum_(i=0)^(n) P_(i,k-1) ⟫
⟪ P_(n+1,k) = 1/(n+1) ( P_(n,k-1) + sum_(i=0)^(n-1) P_(i,k-1) )⟫
⟪ P_(n+1,k) = 1/(n+1) ( P_(n,k-1) + n * ubrace(1/(n) sum_(i=0)^(n-1) P_(i,k-1) )_(P_(n,k)) )⟫⟪ P_(n+1,k) = 1/(n+1) ( P_(n,k-1) + n * P_(n,k) )⟫
Eine weitere Vereinfachung ist leider nicht möglich.
Fassen wir zusammen:
(20) ⟪{: ( P_(0,0) , = 1 , ), ( P_(n,0) , = 0 , if n ge 1 ), ( P_(n,k) , = 0 , if k gt n ), ( P_(n+1,k) , = 1/(n+1) sum_(i=0)^n P_(i,k-1), if n ge 1 ^^ 1 le k le n ), ( , = 1/(n+1) (P_(n,k-1)+n P_(n,k)) , ) :}⟫
Die Werte von Pn,k bis n=10 in Tabellenform:
| k | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 1 | 1.00000000 | |||||||||
| 2 | 0.50000000 | 0.50000000 | ||||||||
| 3 | 0.33333333 | 0.50000000 | 0.16666667 | |||||||
| 4 | 0.25000000 | 0.45833333 | 0.25000000 | 0.04166667 | ||||||
| 5 | 0.20000000 | 0.41666667 | 0.29166667 | 0.08333333 | 0.00833333 | |||||
| 6 | 0.16666667 | 0.38055556 | 0.31250000 | 0.11805556 | 0.02083333 | 0.00138889 | ||||
| 7 | 0.14285714 | 0.35000000 | 0.32222222 | 0.14583333 | 0.03472222 | 0.00416667 | 0.00019841 | |||
| 8 | 0.12500000 | 0.32410714 | 0.32569444 | 0.16788194 | 0.04861111 | 0.00798611 | 0.00069444 | 0.00002480 | ||
| 9 | 0.11111111 | 0.30198413 | 0.32551808 | 0.18541667 | 0.06186343 | 0.01250000 | 0.00150463 | 0.00009921 | 0.00000276 | |
| 10 | 0.10000000 | 0.28289683 | 0.32316468 | 0.19942681 | 0.07421875 | 0.01743634 | 0.00260417 | 0.00023975 | 0.00001240 | 0.00000028 |
| k | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 1 | ⟪1/1⟫ | |||||||||
| 2 | ⟪1/2⟫ | ⟪1/2⟫ | ||||||||
| 3 | ⟪1/3⟫ | ⟪1/2⟫ | ⟪1/6⟫ | |||||||
| 4 | ⟪ 1/4⟫ | ⟪11/24⟫ | ⟪ 1/4⟫ | ⟪ 1/24⟫ | ||||||
| 5 | ⟪ 1/5⟫ | ⟪ 5/12⟫ | ⟪ 7/24⟫ | ⟪ 1/12⟫ | ⟪ 1/120⟫ | |||||
| 6 | ⟪ 1/6⟫ | ⟪137/360⟫ | ⟪ 5/16⟫ | ⟪ 17/144⟫ | ⟪ 1/48⟫ | ⟪ 1/720⟫ | ||||
| 7 | ⟪ 1/7⟫ | ⟪ 7/20⟫ | ⟪ 29/90⟫ | ⟪ 7/48⟫ | ⟪ 5/144⟫ | ⟪ 1/240⟫ | ⟪ 1/5040⟫ | |||
| 8 | ⟪ 1/8⟫ | ⟪ 363/1120⟫ | ⟪ 469/1440⟫ | ⟪ 967/5760⟫ | ⟪ 7/144⟫ | ⟪ 23/2880⟫ | ⟪ 1/1440⟫ | ⟪ 1/40320⟫ | ||
| 9 | ⟪ 1/9⟫ | ⟪ 761/2520⟫ | ⟪ 29531/90720⟫ | ⟪ 89/480⟫ | ⟪ 1069/17280⟫ | ⟪ 1/80⟫ | ⟪ 13/8640⟫ | ⟪ 1/10080⟫ | ⟪ 1/362880⟫ | |
| 10 | ⟪ 1/10⟫ | ⟪ 7129/25200⟫ | ⟪ 1303/4032⟫ | ⟪ 4523/22680⟫ | ⟪ 19/256⟫ | ⟪ 3013/172800⟫ | ⟪ 1/384⟫ | ⟪ 29/120960⟫ | ⟪ 1/80640⟫ | ⟪ 1/3628800⟫ |
| k | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 1 | ⟪1/1⟫ | |||||||||
| 2 | ⟪1/2⟫ | ⟪1/2⟫ | ||||||||
| 3 | ⟪2/6⟫ | ⟪3/6⟫ | ⟪1/6⟫ | |||||||
| 4 | ⟪ 6/24⟫ | ⟪11/24⟫ | ⟪ 6/24⟫ | ⟪ 1/24⟫ | ||||||
| 5 | ⟪ 24/120⟫ | ⟪ 50/120⟫ | ⟪ 35/120⟫ | ⟪ 10/120⟫ | ⟪ 1/120⟫ | |||||
| 6 | ⟪120/720⟫ | ⟪274/720⟫ | ⟪225/720⟫ | ⟪ 85/720⟫ | ⟪ 15/720⟫ | ⟪ 1/720⟫ | ||||
| 7 | ⟪ 720/5040⟫ | ⟪1764/5040⟫ | ⟪1624/5040⟫ | ⟪ 735/5040⟫ | ⟪ 175/5040⟫ | ⟪ 21/5040⟫ | ⟪ 1/5040⟫ | |||
| 8 | ⟪ 5040/40320⟫ | ⟪13068/40320⟫ | ⟪13132/40320⟫ | ⟪ 6769/40320⟫ | ⟪ 1960/40320⟫ | ⟪ 322/40320⟫ | ⟪ 28/40320⟫ | ⟪ 1/40320⟫ | ||
| 9 | ⟪ 40320/362880⟫ | ⟪109584/362880⟫ | ⟪118124/362880⟫ | ⟪ 67284/362880⟫ | ⟪ 22449/362880⟫ | ⟪ 4536/362880⟫ | ⟪ 546/362880⟫ | ⟪ 36/362880⟫ | ⟪ 1/362880⟫ | |
| 10 | ⟪ 362880/3628800⟫ | ⟪1026576/3628800⟫ | ⟪1172700/3628800⟫ | ⟪ 723680/3628800⟫ | ⟪ 269325/3628800⟫ | ⟪ 63273/3628800⟫ | ⟪ 9450/3628800⟫ | ⟪ 870/3628800⟫ | ⟪ 45/3628800⟫ | ⟪ 1/3628800⟫ |
5a. Ergänzung
Schauen wir uns die Zähler aus Tabelle 6 an und nennen sie Sn,k.
⟪S_(n,k) = n! \ P_(n,k)⟫
⟪P_(n,k) = 1/(n!) \ S_(n,k)⟫
Als Rekursionsformel ergibt sich:
⟪ S_(n+1,k) = (n+1)! \ P_(n+1,k) ⟫
⟪ S_(n+1,k) = (n+1)! \ 1/(n+1) ( P_(n,k-1) + n * P_(n,k) ) ⟫
⟪ S_(n+1,k) = (n+1)! \ 1/(n+1) ( S_(n,k-1)/(n!) + n * S_(n,k)/(n!) ) ⟫
⟪ S_(n+1,k) = n! ( S_(n,k-1)/(n!) + n * S_(n,k)/(n!) ) ⟫
⟪ S_(n+1,k) = S_(n,k-1) + n * S_(n,k) ⟫
Zusammengefasst:
(21) ⟪{: ( S_(0,0) , = 1 , ), ( S_(n,0) , = 0 , if n ge 1 ), ( S_(n,k) , = 0 , if k gt n ), ( S_(n+1,k) , = S_(n,k-1) + n * S_(n,k), if n ge 1 ^^ 1 le k le n ) :}⟫
| k | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 1 | 1 | |||||||||
| 2 | 1 | 1 | ||||||||
| 3 | 2 | 3 | 1 | |||||||
| 4 | 6 | 11 | 6 | 1 | ||||||
| 5 | 24 | 50 | 35 | 10 | 1 | |||||
| 6 | 120 | 274 | 225 | 85 | 15 | 1 | ||||
| 7 | 720 | 1764 | 1624 | 735 | 175 | 21 | 1 | |||
| 8 | 5040 | 13068 | 13132 | 6769 | 1960 | 322 | 28 | 1 | ||
| 9 | 40320 | 109584 | 118124 | 67284 | 22449 | 4536 | 546 | 36 | 1 | |
| 10 | 362880 | 1026576 | 1172700 | 723680 | 269325 | 63273 | 9450 | 870 | 45 | 1 |
Der
hat die
Stirling-Zahlen erster Ordnung
entdeckt.
6. Wie oft im Schnitt springt der Frosch d Felder weit?
Wir bezeichnen die durchschnittliche Anzahl von Sprüngen der Distanz d bei Start auf Feld f als Jd(f).
Von einem Feld f ist offensichtlich kein Sprung mit einer Weite d größer als f möglich:
(22) ⟪J_d(f) = 0 if d gt f⟫
Für Sprungweiten d kleiner oder gleich der Feldnummer f ist die Wahrscheinlichkeit, dass der Frosch diese Sprungweite wählt, jeweils 1/f. Mögliche Ziele sind sind die Felder 0 bis f-1, von denen im Schnitt Jd(0) bis Jd(f-1) mal die Sprungweite d gewählt wird. Diese Felder werden mit der Wahrscheinlichkeit von je 1/f erreicht.
(23) ⟪J_d(f) = ubrace(1/f)_"erster Sprung" + ubrace(1/f sum_(i=0)^(f-1) J_d(i))_"weitere Sprünge" if d le f⟫
Umformung (gleiche Methode wie im Abschnitt 4) ergibt:
(24) ⟪J_d(f) * f = 1 + sum_(i=0)^(f-1) J_d(i) if d le f⟫
Wir setzen f+1 für f ein und trennen den letzten Term der Summe ab:
⟪J_d(f+1) * (f+1) = 1 + sum_(i=0)^f J_d(i) if d le f⟫
(25) ⟪J_d(f+1) * (f+1) = 1 + J_d(f) + sum_(i=0)^(f-1) J_d(i) if d le f⟫
Subtraktion der Formel (24) von (25) ergibt:
⟪J_d(f+1) * (f+1) - J_d(f) * f = J_d(f) if d le f⟫
⟪J_d(f+1) * (f+1) = J_d(f) * (f+1) if d le f⟫
(26) ⟪J_d(f+1) = J_d(f) if d le f⟫
Zusammen mit (22) und (23) erhalten wir:
(27) ⟪J_d(f) = { ( 0 , if d gt f ), ( 1/d, if d le f ) :}⟫
Die durchschnittliche Häufigkeit einer bestimmten Sprungweite ist, sofern diese Sprungweite überhaupt erreichbar ist, konstant und unabhängig vom Ausgangsfeld.