Zadanie
Unavený Féro sa nudí, a tak sa pozerá na polarizáciu fotónov. Polarizácia je kvantový jav, ktorý môže skolabovať do horizontálneho alebo vertikálneho stavu s rovnakou pravdepodobnosťou. Teda funguje ako férová minca. Féro si povedal, že skončí, keď dvakrát po sebe uvidí vertikálne polarizované fotóny. V závislosti od \(n\) určte, aká je pravdepodobnosť, že skončí po pozretí sa na presne \(n\) fotónov.
Preformulujme si úlohu pomocou hodov mincou. Nech hlava (pozorovanie vertikálne polarizovaného fotónu) je reprezentovaná jednotkou a orol (pozorovanie horizontálne polarizovaného fotónu) je reprezentovaný nulou. Platná séria hodov môže vyzerať nasledovne: \[01001(0{\color{red}\underline{11}})\]
Najprv skúsime spočítať počet možností pre série hodov, ktoré končia práve \(n\)-tým hodom. Pozrieme sa na to, ako taká séria hodov musí vyzerať.
Môžeme si všimnúť, že pre \(n \geq 3\) sú posledné tri hody pevne dané. Posledné dva hody (hod \(n-1\) a hod \(n\)) musia byť dve \(1\), aby sa séria hodov ukončila práve \(n\)-tým hodom a \((n-3)\)-tí hod musela byť \(0\), ináč by sme skončili na \((n-1)\)-vom hode. Každá séria \(n \geq 3\) hodov je preto jednoznačne daná prvými \(n-3\) hodmi.
Zamerajme sa na spočítanie sérií týchto \(m = n-3\) hodov, keďže ich počet je rovnaký ako počet sérii \(n\) hodov so zakončením \((011)\).
Každá séria hodov sa môže začínať \(0\) alebo \(1\), teda celkový počet sérii hodov dĺžky \(m\) (ďalej označených \(P_m\)) je rovný súčtu
počtu takýchto sérií hodov začínajúcich s \(0\) (označených \(P^{(0)}_m\)),
a počtu takýchto sérii hodov začínajúcich s \(1\) (označených \(P^{(1)}_m\)).
Zapíšeme si to rovnicou ako \[P_m = P^{(0)}_m + P^{(1)}_m.\]
Pozrime sa teraz na série hodov s dĺžkou \(m+1\). Všimneme si, že ich vieme vytvoriť zo sérií hodov s dĺžkou \(m\). \[01001(0{\color{red}\underline{11}}) \rightarrow ({\color{blue}\underline{0/1}})01001(0{\color{red}\underline{11}})\]
Ak sa nejaká séria hodov dĺžky \(m\) začína \(1\), tak na začiatok vieme pridať len \(0\) (ináč by sme dostali dve za sebou idúce \(1\)) a ak sa nejaká séria hodov dĺžky \(m\) začína \(0\), tak na začiatok vieme pridať aj \(0\) aj \(1\). Z toho dostávame, že \[\begin{align} P^{(0)}_{m+1} &= P^{(0)}_m + P^{(1)}_m = P_m,\\ P^{(1)}_{m+1} &= P^{(0)}_m,\\ P_{m+1} &= P^{(0)}_{m+1} + P^{(1)}_{m+1} = P_m + P^{(0)}_m.\end{align}\]
To isté vieme urobiť pre série hodov dĺžky \(m+2\), čím dostaneme \[P_{m+2} = P^{(0)}_{m+2} + P^{(1)}_{m+2} = P_{m+1} + P^{(0)}_{m+1}.\]
Už sme ale zistili, že \(P^{(0)}_{m+1} = P_m\), teda \[P_{m+2} = P_{m+1} + P^{(0)}_{m+1} = P_{m+1} + P_m,\]
čo je identické predpisu Fibonacciho postupnosti \[F_{n+2} = F_{n+1} + F_{n},\ F_0 = 0,\ F_1 = 1.\]
Na to, aby sme mohli povedať, že sú úplne totožné, overíme \(P_3\) a \(P_4\). Očividne existuje jediná séria hodov, ktorá skončí úspechom po troch hodoch, a to \(011\). Po štyroch hodoch môžeme skončiť dvomi spôsobmi, a to \(0011\) a \(1011\). Vidíme teda, že \(P_3 = 1 = F_2, P_4 = 2 = F_3\), čiže vo všeobecnosti dostávame \(P_n = F_{n-1}\).
Samozrejme, vynechali sme \(n = 1\) a \(n = 2\), kde si ale všimneme, že náš predpis platí:
\(n = 1\rightarrow\) nevieme ukončiť hádzanie, teda \(P_1 = 0 = F_0\).
\(n = 2\): \(11 \rightarrow P_2 = 1 = F_1\).
Spočítali sme počty možností sérií hodov pre \(n\) hodov, teraz z toho spočítame hľadanú pravdepodobnosť.
Pravdepodobnosť, že nastane nejaká konkrétna séria hodov dĺžky \(n\) je \(\frac{1}{2^n}\), pretože pravdepodobnosť, že konkrétny samostatný hod dopadne tak, ako dopadol v danej sérii, je \(\frac{1}{2}\). Hľadaných sérií dĺžky \(n\) je \(F_{n-1}\), teda hľadaná pravdepodobnosť je \[F_{n-1} \cdot \cfrac{1}{2^n} = \cfrac{F_{n-1}}{2^n}.\]
Poznámka: Uznávali sme aj riešenia, ktoré výsledok reprezentovali prehľadnou a dobre odôvodnenou rekurenciou, ak rekurencia výsledok jednoznačne udávala, nakoľko aj samotná Fibonacciho postupnosť je reprezentovaná rekurenciou.
Diskusia
Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.
Pre pridávanie komentárov sa musíš prihlásiť.