A.S.: Jo, singulár slova ‚kostka‘ je zřejmě ‚kostka‘. 😉
Po internetu koluje záludná programátorská úloha, kterou lze, jak jste si možná domysleli z mého pokusu o pragmatický název, formalizovat takto:
Máte-li k dispozici funkci, která vrací rovnoměrně náhodné číslo v rozsahu 1 až 5 (včetně), navrhněte funkci, která vrací rovnoměrně náhodné číslo v rozsahu 1 až 7 (včetně).
Pokud jsou průsečíky algoritmů a statistiky vaším koníčkem, neváhejte a zkuste to! Další výzvou je, aby váš algoritmus byl časově omezený. Zjistil jsem, že je to zábavné cvičení, jen jsem si uvědomil, že zde hrají roli zásadní omezení.
Kostkou se zde samozřejmě myslí dokonale rovnoměrný náhodný generátor, který existuje pouze teoreticky. Kostky reálného světa se řídí přírodními zákony a nedokonalostmi prostředí takovým způsobem, že jsou pouze aproximací (i když dobrou) tohoto abstraktního modelu.
Neomezené řešení
Podívejme se na rodinu neomezených algoritmů. Abychom vytvořili generátor náhodných čísel, který bude mít alespoň 7 výsledků, budeme muset hodit pětistěnnou kostkou alespoň dvakrát. Dvojím hodem vznikne 5^2=25 možných výsledků, a přestože to není násobek 7, můžeme prvních 21 výsledků přiřadit do 7 skupin o stejné velikosti 3. Pokud však skončíme u jednoho ze zbývajících 4 výsledků, musíme postup začít znovu. Žádnému z těchto 4 nešťastných koncových stavů nemůžeme jednoduše přiřadit výstup, protože bychom tím narušili vlastnost rovnoměrné náhodnosti.
V uvedeném grafu představují kroužky „stavy“ našeho programu a text uvnitř je poslední hodnota hozené kostky. Zelená pole pak představují výstup, který přiřadíme v závislosti na koncovém stavu (= po dvojím hodu kostkou). V 84 % případů dostaneme výstup po dvou hodech a algoritmus skončí. Jak vidíte, je zde přítomna smyčka, která činí algoritmus neohraničeným. To znamená, že pro každé celé číslo, bez ohledu na jeho velikost, existuje malá, ale nenulová pravděpodobnost, že celkový počet hodů překročí tuto hodnotu, aby bylo možné vypočítat jednu výstupní hodnotu. Aplikace v reálném čase s přísnými časovými požadavky tedy nepřipadají v úvahu, pokud nejste ochotni přistoupit na kompromisy ohledně statistické přesnosti algoritmu.
Varianta tohoto řešení zpočátku hází až třemi kostkami, než se restartuje: tím vznikne 5^3=125 koncových stavů, z nichž můžeme nejvýše 119 přiřadit 7 skupinám o stejné velikosti po 17. Nyní existuje 95,2% pravděpodobnost, že skončíme po maximálně třech hodech. Všimněte si, že v průměru musíme házet méněkrát než dříve (280/119 ≈ 2,35 oproti 50/21 ≈ 2,38), protože většinou můžeme již po prvních dvou hodech udělat zkratku a tyto mezistavy přímo namapovat na výstup. Toto průměrné množství hodů se s pokračujícím trendem stále snižuje.
Jestliže jste obeznámeni s teorií informace, pak uvažujte o tom, že jeden hod pětistěnnou kostkou (= rand5) generuje log2(5) ≈ 2,32 bitu informace a jeden hod sedmistěnnou kostkou (= rand7) generuje log2(7) ≈ 2,81 bitu informace. Ukazuje se, že v mezním případě potřebujeme na každou hodnotu rand7, kterou chceme získat, právě log(7)/log(5) ≈ 1,21 vyvolání rand5. Přesná implementace, která funguje libovolně blízko této meze, je poměrně složitá a přesahuje rámec tohoto článku. Potřebovali bychom ukládat stavové informace mezi několika voláními rand7 a algoritmus, který mám na mysli, je stále neomezený nejen časově, ale i paměťově. Rád vás vyzvu, abyste mě informovali o metodě, která tento druhý problém řeší!“
Vázané řešení
Neexistuje nic takového jako vázaný algoritmus, který by počítal dokonale rovnoměrnou náhodnou hodnotu mezi 1 a 7, pokud je dán generátor náhodných hodnot pouze mezi 1 a 5. V tomto případě se jedná o algoritmus, který by počítal dokonale rovnoměrnou náhodnou hodnotu. Uvažujme výše uvedenou rodinu neohraničených řešení. Jak jsem naznačil, v každém bodě bude vždy existovat množství „zbytkových“ stavů (v rozmezí od 1 do 6), které způsobí restart algoritmu. Je to proto, že 5 a 7 jsou prvočísla a žádná mocnina 5 nemůže být nikdy násobkem 7. Jakkoli může být lákavé použít Fermatovu malou větu, takové pokusy povedou k chybám mimo jedničku, protože základní teorie čísel ohraničené řešení v této rodině znemožňuje.
Můžete správně poukázat na to, že počet koncových stavů není vždy mocninou 5, například v případě „až tří hodů“, kdy můžeme vzít zkratku již po dvou hodech. Možná bychom mohli stavový diagram uspořádat tak, aby vznikl ohraničený algoritmus s cestami proměnné délky a 7n koncovými stavy? Uvažujme však následující:
- Tyto koncové stavy nebudou stejně pravděpodobné, protože ne každá cesta má stejnou délku (= množství volání rand5).
- Můžeme velmi snadno rozšířit strom tak, aby každá cesta byla stejně dlouhá, a to tak, že budeme zbytečně volat rand5 příslušný početkrát, kdykoli se budeme nacházet v předčasném koncovém stavu. Nyní se množství koncových stavů opět stává mocninou 5 a všechny koncové stavy jsou stejně pravděpodobné.
To samozřejmě není formální důkaz, ale doufám, že jsem vám poskytl určitou intuici o problému. Jak vidíme, někdy se problém může zdát velmi realistický, jen abychom narazili na takováto matematická fakta. Dokážete po této analýze zjistit, zda je možné simulovat osmistěnnou kostku počínaje čtyřstěnnou kostkou?“
.