Rzucamy sto razy monetą. Jakie są szanse, że orzeł wypadnie 5 razy z rzędu? A jakie, że wypadnie 10 razy z rzędu? A, że 10 razy z rzędu wypadnie orzeł lub 10 razy z reszka? A co jeśli rzucimy monetą 1000 razy? I co mają z tym wszystkim wspólnego liczby Fibonacciego? W tym wpisie nauczymy się liczyć tego typu prawdopodobieństwa.
Pewnego sierpniowego wieczoru 1913 roku w kasynie w Monte Carlo wydarzyła się rzecz, na pierwszy rzut oka, przedziwna. Kulka ruletki zatrzymała się na czarnym polu 26 razy z rzędu.
Po którymś razie gracze zaczęli uważać, że skoro szanse na wypadnięcie tego samego koloru kilkanaście razy z rzędu są bardzo mało, to następnym razem już musi wypaść kolor czerwony. Zaczęli więc stawiać na kolor czerwony. Zapomnieli przy tym, ku wielkiej uciesze właścicieli kasyna, że wynik zakręcenia ruletką w żaden sposób nie zależy od wyników poprzednich.
Jest to klasyczny przypadek tzw. złudzenia Monte Carlo, gdy zdarzenia przedłużające pewną serię uznajemy, z tylko tego powodu, za mniej prawdopodobne mimo iż wszystkie są od siebie niezależne.
Gdybyśmy rzucali monetą i 26 razy z rzędu wypadłby orzeł, to większość osób uznałaby takie zdarzenie za co najmniej mocno podejrzane. Przy założeniu, że moneta jest uczciwa, to szanse na wypadnięcie orła jak i reszki wynoszą \(\dfrac{1}{2}\). Wobec tego orzeł i reszka powinny wypadać mniej więcej tyle samo razy, prawda?
W długiej perspektywie stosunek orłów do reszek powinien oscylować wokół jedynki. Jednakże jeśli rzucamy monetą np. 1000 razy, to każdy możliwy 1000-elementowy ciąg orłów i reszek jest tak samo prawdopodobny.
Szanse na ten, który byśmy otrzymali rzucając byłyby przed rzucaniem identyczne jak na tysiąc orłów. Czym innym jest szansa na konkretną ilość otrzymanych orłów. Tysiąc orłów możemy otrzymać tylko na jeden sposób, a 500 już na znacznie więcej.
Nie oznacza to jednak, że długa seria orłów dowodzi iż moneta nie jest uczciwa. Prawdę mówiąc, podejrzane by było gdyby, w miarę rzucania, coraz dłuższe serie się nie zdarzały.
Trzy to mała liczba, więc seria tylu orłów nikogo by nie zdziwiła. Podczas rzucania monetą przytrafia się bardzo często. Spośród wszystkich tych serii trzech orłów, jeżeli rzucanie jest kontynuowane, to w kolejnym rzucie czasami wypadnie orzeł a czasami reszka. Otrzymamy więc pewną liczbę serii czterech orłów. I znowu, jeżeli kontynuujemy rzucanie, to w kolejnym rzucie czasami trafi się orzeł czasami reszka itd.
Czyli aby otrzymać serię orłów dowolnej długości wystarczy rzucać dostatecznie długo! Powyższe rozumowanie nie jest oczywiście żadnym dowodem. Mimo to pozwala przekonać się, że długie serie np. orłów czy tego samego koloru w ruletce czasami się zdarzają i jest to jak najbardziej naturalne.
Można przeprowadzić ciekawy eksperyment. Poprosić jedną osobę o rzucenie kilkaset razy prawdziwą monetą oraz poprosić inną aby wymyśliła wynik rzucania. Większość osób, wymyślając wynik takiego doświadczenia, unikałaby dłuższych serii. Byłaby to przesłanka pozwalająca nabrać podejrzeń, co do wyniku takiego eksperymentu. Oszukiwać w końcu trzeba umieć.
Zanim przejdziemy do konkretów, przyda się wiedza czym są liczby Fibonacciego. Otóż ciąg Fibonacciego to taki ciąg, że \[F_1=F_2=1\ \textrm{ oraz }F_n=F_{n-1}+F_{n-2}\textrm{ dla } n>1.\]
Nie licząc pierwszych dwóch wyrazów, każdy wyraz ciągu jest sumą dwu poprzednich. \[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …\]
Więcej o ciągu Fibonacciego można poczytać tutaj. Z ciągiem tym jest związana słynna złota proporcja, z którą związanych jest wiele mitów. Zainteresowanych tym tematem odsyłam tutaj.
Na potrzeby tego wpisu przyjmiemy nieco ogólniejszą definicję ciągu Fibonacciego rozszerzając ją również na indeksy ujemne oraz indeks zerowy. Dokładniej przyjmujemy, że \[F_n=\left\{\begin{array}{lll}
0 & \textrm{ dla } & n < 1,\\ 1 & \textrm{ dla } & n=1,\\ F_{n-1}+F_{n-2} & \textrm{ dla } & n>1.
\end{array}\right.\]
Sumując więcej niż dwa poprzedniki możemy otrzymać uogólnione liczby Fibonacciego. Przykładowo, dla \(k=3\) zdefiniujmy liczby \(F_n^{(3)}\) przyjmując
\[F_n^{(3)}=\left\{\begin{array}{lll}
0 & \textrm{ dla } & n < 1,\\ 1 & \textrm{ dla } & n=1,\\ F_{n-1}^{(3)}+F_{n-2}^{(3)}+F_{n-3}^{(3)} & \textrm{ dla } & n>1.
\end{array}\right.\]
Kolejne wyrazy o indeksach dodatnich to: \[1, 1, 2, 4, 7, 13, 24, 44, 81, \ldots \] Nazwijmy ten ciąg roboczo ciągiem 3-Fibonacciego. Ogólnie, liczby k-Fibonacciego definiujemy dla \(k>1\) następująco:
\[F_n^{(k)}=\left\{\begin{array}{lll}
0 & \textrm{ dla } & n < 1,\\ 1 & \textrm{ dla } & n=1,\\ F_{n-1}^{(k)}+F_{n-2}^{(k)}+F_{n-3}^{(k)}+\ldots+F_{n-k}^{(k)} & \textrm{ dla } & n>1.
\end{array}\right.\]
Dla \(k=2\) otrzymujemy standardowe liczby Fibonacciego. Ogólnie dla \(k>1\) liczby k-Fibonacciego indeksowane liczbami naturalnymi, to \[1, 1, 2^1, 2^2,\ldots, 2^{k-1}, 2^k-1=F_{k+2}^{(k)},\ldots.\]
Okazuje się, że prawdopodobieństwo \(P_n(k)\) otrzymania co najmniej \(k\) orłów z rzędu w \(n\) rzutach uczciwą monetą, dla \(k\leqslant n\), jest równe \[P_n(k)=1-\dfrac{F_{n+2}^{(k)}}{2^n}.\]
Udowodnimy to licząc prawdopodobieństwo zdarzenia przeciwnego, tj. takiego, że orzeł ani razu nie wypadnie \(k\) razy z rzędu. Wbrew pozorom idea dowodu jest bardzo prosta. Dla prostoty przeprowadzimy go najpierw dla \(k=2\).
Łatwo zauważyć, że \(P_1(2)=0\) bo przy jednym rzucie ciężko otrzymać 2 orły. Podobnie łatwo sprawdzić, że \(P_2(2)=\frac{1}{4}\), gdyż mamy 4 możliwe wyniki, a dwa orły mogą wypaść na jeden sposób. Załóżmy teraz, że \(n>2\).
Oznaczmy przez \(X_n\) liczbę wszystkich takich wyników \(n\)-krotnego rzutu monetą, w których orzeł ani razu nie wypadł \(k\) razy z rzędu. Ponieważ wszystkich możliwych wyników \(n\)-krotnego rzutu monetą jest \(2^n\), to \[P_n(k)=1-\dfrac{X_n}{2^n}.\]
Oznaczmy również przez \(R_n\) zbiór tych elementów \(X_n\), które kończą się reszką, a przez \(O_n\) te kończące się orłem. Zbiory te są rozłączne oraz \(X_n=R_n\cup O_n\). Wobec tego \[|X_n|=|R_n|+|O_n|,\]
gdzie \(|U|\) oznacza liczbę elementów zbioru \(U\).
Zauważmy, że jeżeli \(A\in R_n\), to usuwając ostatnią reszkę z ciągu \(A\), otrzymujemy element zbioru \(X_{n-1}\). Podobnie, jeżeli \(B\in X_{n-1}\), to dodając na koniec ciągu \(B\) reszkę, otrzymujemy element zbioru \(R_n\).
Nietrudno się przekonać, że zbiory \(R_n\) oraz \(X_{n-1}\) mają po tyle samo elementów. Mówiąc bardziej matematycznie, obie operacje wyznaczają funkcje \(R_n\to X_{n-1}\) oraz \(X_{n-1}\to R_n\), które są wzajemnie odwrotne tzn. są bijekcjami, więc \[|X_{n-1}|=|R_n|.\]
Każdy ciąg \(A\in O_n\) musi na przedostatnim miejscu mieć reszkę. Zatem usuwając końcowego orła otrzymujemy element zbioru \(R_{n-1}\). Natomiast gdy \(B\in R_{n-1}\), to dodając na koniec orła dostajemy element zbioru \(O_n\). Jak poprzednio, operacje te są wzajemnie odwrotne co pokazuje, że \[|O_n|=|R_{n-1}|=|X_{n-2}|.\]
Pozostały już tylko proste obliczenia: \[|X_{n+1}|=|R_{n+1}|+|O_{n+1}|=|X_n|+|X_{n-1}|.\]
Otrzymaliśmy związek analogiczny do definiującego liczby Fibonacciego. Ponieważ, jak łatwo sprawdzić, \(|X_1|=2\) oraz \(|X_2|=3\), to \(|X_{n}|=F_{n+2}\). Prawdopodobieństwo tego, że przy \(n\)-krotnym rzucie monetą otrzymamy co najmniej raz dwa orły z rzędu jest więc równe \[P_n(2)=1-\dfrac{F_{n+2}}{2^n}.\]
Podobne rozumowanie pozwoli nam obliczyć prawdopodobieństwo otrzymania co najmniej \(k\) orłów z rzędu dla \(k\leqslant n\), gdy rzucamy \(n\) razy uczciwą monetą. Wprowadźmy oznaczenia:
- \(X_n,\ R_n\) – jak poprzednio,
- \(O_n^j\) – elementy zbioru \(X_n\) kończące się dokładnie \(j\) orłami dla \(j\in\{1, 2, \ldots, k-1\}\).
Zbiory \(R_n, O_n^1, O_n^2,\ldots, O_n^{k-1}\) są rozłączne, więc \[|X_n|=|R_n|+|O_n^1|+|O_n^2|+\ldots + |O_n^{k-1}|.\] Podobnie jak wcześniej mamy \(|R_n|=|X_{n-1}|.\)
Każdy ciąg z \(O_n^1\) jest zakończony na \(RO\). Usuwając ostatnie \(O\), otrzymujemy element zbioru \(R_{n-1}\). Nietrudno więc zauważyć, że \[|O_n^1|=|R_{n-1}|=|X_{n-2}|\].
Podobnie, gdy \(A\in O_n^2\), to usuwając dwa ostatnie orły, otrzymujemy element zbioru \(R_{n-2}\), który ma tyle samo elementów co zbiór \(X_{n-3}\).
Ogólnie, mamy \[|O_n^j|=|R_{n-j}|=|X_{n-j-1}|\] dla \(j\in\{1, 2, \ldots, k-1\}\). Z tego wynika, że \[|X_{n}|=|X_{n-1}|+|X_{n-2}|+\ldots +|X_{n-k}|.\]
Jeżeli \(j < k\), to nie ma możliwości otrzymania w \(j\) rzutach serii \(k\) orłów z rzędu. Dla \(j=k\) taka możliwość jest dokładnie jedna, gdy wypadną same orły. Zatem \[|X_1|=2, |X_2|=4,\ldots, |X_{k-1}|=2^{k-1}, |X_k|=2^k-1.\] Z tego wynika, że \(X_{n}=F_{n+2}^{(k)}\).
Korzystając ze zdobytej właśnie wiedzy możemy wyliczać stosowne prawdopodobieństwa. Najpierw rozważymy przypadek \(n=100\). Ponieważ \[\begin{array}{lll}2^{100} & = & 1267650600228229401496703205376, \\ F_{102}^{(5)} & = & 240714680556315819945145376976, \\ F_{102}^{(7)} & = & 865145690433457063670671045568, \\ F_{102}^{(10)} & = & 1211700015849788251502892752696, \end{array}\] to \[P_{100}(5)\approx 0,51;\ P_{100}(7)\approx 0,32;\ P_{100}(10)\approx 0,04. \]
A ponieważ \[\begin{array}{lll}2^{1000} & = & 107150860718626732094842504906000181056140481170553360744\\ & & 375038837035105112493612249319837881569585812759467291755 \\ & & 31468251871452856 9231404359845775746985748039345677748242 \\ & & 309854210746050623711418779541821530464749835819412673987 \\ & & 675591655439460770629145711964776865421676604298316526243 \\ & & 86837205668069376, \\ F_{1002}^{(7)} & = &
1951931694374203392380153643460319928198396047620781292307 \\ & & 3430794149234107978654015978599705725554008738281498169429 \\ & & 8002061875860379953551331290319389637874292574187774904885 \\ & & 6773253485488789323911261414311339149623223238459108363958 \\ & & 7673638371643391184603365115712897171498383885917124763463 \\ & & 8852771589, \\
F_{1002}^{(8)} & = &
1487845321697007010537344184349323529508312342548785512871 \\ & & 9982441495251034169781579077695793948782233146122500100273 \\ & & 8850027726867931266531118335113875745214362541458524439070 \\ & & 1195697419719241980253811232225283809268222881037002582988 \\ & & 1230574489357550307678852742376480653231406056081145719294 \\ & & 75080519168, \\
F_{1002}^{(10)} & = & 658495879838477541098956866739106498262609377937967858942 \\ & & 388829693542980328166481902255993601937934368450020223591 \\ & & 820474434750402893624690433833741750470189631892660786901 \\ & &
620234862745956888955126711810965381926187846094626950721 \\ & & 869014489236794868982193591641358214332609805650275251955 \\ & & 6568695574716415, \end{array}\]
to \(P_{1000}(7)\approx 0,98, P_{1000}(8)\approx 0,86, P_{1000}(10)\approx 0,39.\)
Identyczne prawdopodobieństwa otrzymamy gdy orła zastąpimy reszką. A jak obliczyć szanse na to, że rzucając monetę 1000 razy otrzymamy 10 orłów z rzędu lub 10 reszek z rzędu? Idee prowadzące do wyniku są tutaj podobne. Wprowadźmy oznaczenia:
- \(X_n^k\) zbiór wszystkich wyników \(n\)-krotnego rzutu monetą, w których ani orzeł ani reszka nie padły \(k\) raz z rzędu;
- \(O_n^j\) – zbiór elementów \(X_n^k\) kończących się dokładnie \(j\) orłami,
- \(R_n^j\) – zbiór elementów \(X_n^k\) kończących się dokładnie \(j\) reszkami.
Każdy ciąg \(A\in X_n^k\) kończy się pewną, mniejszą od \(k\), ilością orłów albo reszek. Wobec tego nietrudno zauważyć, że \[|X_n^k|=|O_n^1|+|O_n^2|+\ldots +|O_n^{k-1}|+|R_n^1|+|R_n^2|+\ldots +|R_n^{k-1}|.\] Każdy element zbioru \(R_{n+1}^1\) jest zakończony reszką poprzedzoną pewną liczbą orłów, więc \[|O_n^1|+|O_n^2|+\ldots +|O_n^{k-1}|=|R_{n+1}^1|\] i analogicznie \[|R_n^1|+|R_n^2|+\ldots +|R_n^{k-1}|=|O_{n+1}^1|.\]
Czyli \[|X_n^k|=|O_{n+1}^1|+|R_{n+1}^1|.\]
Dalej zauważmy, że
\[\begin{array}{lllll}
|O_n^2| & = & |O_{n-1}^1|, & & \\ |O_n^3| & = & |O_{n-1}^2| & = & |O_{n-2}^1|,\\ |O_n^j| & = & \ldots & = & |O^1_{n-j+1}|.
\end{array}\]
Analogicznie \[|R_n^j|=|R_{n-j+1}^1|.\]
Dalej mamy \[\begin{array}{l}|O_n^1|+|R_n^1|=|X_{n-1}^k|, \\ |O_n^2|+|R_n^2|=|O_{n-1}^1|+|R_{n-1}^1|=|X_{n-2}^k|, \\ |O_n^j|+|R_n^j|=|O_{n-j+1}^1|+|R_{n-j+1}^1|=|X_{n-j}^k|.\end{array}\]
Wobec tego \[\begin{array}{lll}|X_n^k| & = & |O_n^1|+|O_n^2|+\ldots +|O_n^{k-1}|+|R_n^1|+|R_n^2|+\ldots +|R_n^{k-1}| \\ & = & (|O_n^1|+|R_n^1|) + (|O_n^2|+|R_n^2|)+\ldots + (|O_n^{k-1}|+|R_n^{k-1}|) \\ & = & |X^k_{n-1}|+|X^k_{n-2}|+\ldots +|X^k_{n-(k-1)}|.\end{array}\]
Otrzymaliśmy zatem wzór analogiczny do definiującego liczby \((k-1)\)-Fibonacciego. Na koniec wystarczy zauważyć, że dla \(i\) mniejszego od \(k\) mamy \(|X_i^k|=2^i\). Natomiast dla \(i=k\) mamy \(|X_i^k|=2^i-2\), gdyż mamy dwa ciągi nienależące do \(X_i^k\): ciąg samych reszek oraz ciąg samych orłów.
Oznaczmy przez \(\tilde{P}_n(k)\) szukane prawdopodobieństwo, że w ciągu \(n\) rzutów uczciwą monetą otrzymamy przynajmniej raz \(k\) orłów z rzędu lub \(k\) reszek z rzędu. Oczywiście \(k\leqslant n\).
Ponieważ
\[\begin{array}{lll} X_{100}^5 & = & 35887606673100025828208205026 \\ X_{100}^7 & = & 580156959829221175647260088196\\ X_{100}^{10} & = & 1157797210644823936815585091586,\end{array}\] to \(\tilde{P}_{100}(5)\approx 0,97, \tilde{P}_{100}(7)\approx 0,54, \tilde{P}_{100}(10)\approx 0,09.\) Podobnie można pokazać, że \(\tilde{P}_{1000}(7)\approx 0,9997, \tilde{P}_{1000}(10)\approx 0,62.\)