Recepty z programátorské kuchařky
Pravděpodobnost

Náhodná čísla a pravděpodobnost hrají v informatice důležitou roli. Když neumíme pro nějakou úlohu najít algoritmus, který je rychlý i v nejhorším případě, můžeme se spokojit s algoritmem rychlým alespoň v průměru. Nebo naopak s algoritmem, který je sice vždy rychlý, ale někdy odpoví špatně. Často se přitom hodí, aby si algoritmus „házel korunou“, tedy generoval nějaká náhodná čísla. Takovým algoritmům se říká pravděpodobnostní nebo také randomizované. V této kuchařce nahlédneme do základů teorie pravděpodobnosti a vybudujeme jí dost na to, abychom uměli zkoumat jednoduché randomizované algoritmy.

Po dlouhá staletí lidé přemýšleli nad pravděpodobností bez toho, aby jí rozuměli matematicky. Pravděpodobnost často není intuitivní, a proto i slavní matematici, jako třeba Newton, někdy v úvahách o náhodě chybovali. Naštěstí v minulém století přišel ruský matematik Andrej Kolmogorov s matematickým vysvětlením pravděpodobnosti, které nám dovoluje použít matematiku k přemýšlení o náhodných jevech, a vyhnout se tak chybám.

Jelikož „opravdová“ teorie pravděpodobnosti závisí na poměrně pokročilé matematice (takzvané teorii míry), vybudujeme ji trochu jednodušším způsobem. Bude výrazně intuitivnější než ta kolmogorovská, ale zvládne popsat jen konečné objekty. Budeme tedy moci zkoumat kostky, karty, algoritmy používající náhodná čísla z nějakého daného rozsahu (třeba celá čísla od 1 do 100) a podobně. Nezvládneme naopak korektně uvažovat o náhodných reálných číslech, náhodných bodech v rovině a jiných nekonečných věcech.

Jevy a jejich pravděpodobnost

Pro začátek si pravděpodobnost ukážeme na příkladu: Máme obyčejnou hrací kostku. Pokud kostkou hodíme, můžeme si být jisti, že na ní padne číslo od 1 do 6. Číslům 1 až 6 budeme říkat elementární jevy. Obecně, kdykoliv provedeme nějaký náhodný experiment (to je třeba hod kostkou), vždy nastane právě jeden elementární jev – v našem příkladu vždy padne jedno z čísel 1 až 6. Každému elementárnímu jevu můžeme přiřadit jeho pravděpodobnost. To je nějaké reálné číslo mezi 0 nebo 1, přičemž pravděpodobnosti všech elementárních jevů se sečtou na 1. To odpovídá tomu, že pokaždé nastane právě jeden z elementárních jevů – kostka nezůstane stát na rohu, ani nepadne jednička a dvojka současně. Prozatím tedy řekněme, že pravděpodobnost je funkce, která každému elementárnímu jevu přiřadí číslo od 0 do 1 a že se všechny pravděpodobnosti sečtou na 1.

Co kdybychom chtěli něco říci o pravděpodobnosti toho, že nám padne liché číslo. Takový výsledek pokusu už není elementární jev, ale můžeme ho stále z elementárních jevů poskládat: lichá čísla popíšeme množinou elementárních jevů L={1,3,5}. Obecně můžeme za (náhodný) jev prohlásit jakoukoliv množinu elementárních jevů. Pro kostku to může být třeba jev A={5,6} (padlo aspoň 5), jev ∅ (ten nenastane nikdy), nebo V={1,2,3,4,5,6} (takovýto jev nastane vždy).

Pravděpodobnost jevu pak můžeme definovat jako součet pravděpodobností těch elementárních jevů, ze kterých se daný jev skládá. Jelikož všechny elementární jevy na kostce mají pravděpodobnost 1/6, bude pravděpodobnost, že padne liché číslo (to je náš jev L), rovna 1/6 + 1/6 + 1/6 = 3/6 = 1/2. Označíme-li pravděpodobnost jevu J jako P(J), vyjde pro ostatní zmíněné jevy P(A)=2/6=1/3, P(∅)=0, P(V)=1.

Jevy jsou tedy množiny a můžeme o nich jako o množinách mluvit. Můžeme například říct, že jevy A a B jsou disjunktní, tedy že A∩B = ∅. To odpovídá tomu, že tyto dva jevy nemohou nastat najednou. Například jevy „padlo sudé číslo“ a „padlo liché číslo“ jsou zjevně disjunktní, protože žádné číslo není současně sudé a liché. Podobně jev A ∪B odpovídá tomu, že nastane jev A nebo jev B, a jev A∩B tomu, že nastane současně A a B.

Zkusme si nyní rozmyslet, že pro jakékoliv dva disjunktní jevy A a B platí P(A ∪B) = P(A) + P(B). Tedy pravděpodobnost (disjunktního) sjednocení A a B je součet pravděpodobností A a B. Toto tvrzení platí proto, že jsme definovali pravděpodobnosti A a B jako součty pravděpodobností elementárních jevů v A a B. Když tedy sečteme pravděpodobnosti všech elementárních jevů, které jsou v A, nebo v B (ale ne v obou, protože A a B mají prázdný průnik), dostaneme to samé, jako když sečteme P(A) a P(B).

Princip inkluze a exkluze

Pro každé dvě množiny A a B platí |A ∪B| = |A| + |B| - |A ∩B|. To proto, že do |A| + |B| jsme prvky v průniku započítali dvakrát, a musíme tedy odečíst jejich počet, abychom dostali správný počet prvků ve sjednocení. Tomuto tvrzení (respektive jeho zobecnění pro libovolný počet množin) se někdy říká princip inkluze a exkluze, česky by asi dalo říci princip zahrnutí a vyloučení.

Podobně pro pravděpodobnosti se dá náhlednout rovnost P(A ∪B) = P(A) + P(B) - P(A ∩B). Vzpomeňme si, že pravděpodobnost jevu je součtem pravděpodobností elementárních jevů, ze kterých se skládá. Pravděpodobnosti elementárních jevů v průniku jsme tedy v P(A) + P(B) započetli dvakrát a musíme je odečíst, abychom dostali pravděpodobnost sjednocení. Všimněme si, že pokud jsou množiny A a B disjunktní, dostaneme P(A ∪B) = P(A) + P(B), jak jsme si rozmysleli před chvílí.

Princip inkluze a exkluze je užitečné pravidlo k počítání pravděpodobností, ale jeho hlavní síla spočívá v následujícím. Uvědomme si, že pravděpodobnosti jsou nezáporná čísla. Platí tedy, že P(A∪B) = P(A) + P(B) - P(A ∩B) ≤ P(A) + P(B), protože P(A ∩B) je nezáporné číslo. Jinými slovy pravděpodobnost toho, že nastane A nebo B je nejvýše součet pravděpodobnosti, že nastane A, a pravděpodobnosti, že nastane B. Tomuto odhadu se říká odhad sjednocení (anglicky union bound) a bývá obzvláště přesný, pokud jevy, na které ho použijeme, mají malé pravděpodobnosti. (Raději zmiňujeme, že matematici slovem odhad míní nerovnost, nikoliv nějaké „odhadnutí od oka“.)

Co kdybychom teď měli sjednocení tří jevů? Pak si to sjednocení správně uzávorkujeme! A ∪B ∪C = (A ∪B) ∪C. Poté můžeme použít odhad sjednocení na dvojice jevů.

Můžeme pokračovat indukcí a dokázat, že pravděpodobnost sjednocení libovolného počtu jevů je nejvýše součet jednotlivých pravděpodobností.

Podmíněná pravděpodobnost

Náš kamarád hodil kostkou a řekl nám, že padlo číslo menší než 4 (padlo tedy 1, 2 nebo 3). Jaká je pravděpodobnost, že padlo liché číslo? V tomto případě není těžké si rozmyslet, že správná odpověď je 2/3. Ale teorie pravděpodobnosti tak, jak jsme si ji zatím vymysleli, nám na podobné úvahy nestačí.

Definujeme tedy podmíněnou pravděpodobnost. Řekneme, že P(A | B) je pravděpodobnost, že nastal jev A, pokud už víme, že nastal jev B. Čteme to obvykle „pravděpodobnost A za podmínky B“.

Čemu by se ale měla P(A | B) rovnat? Předpokládejme, že uděláme hodně náhodných experimentů. P(B) říká, v jakém zlomku z nich nastal jev B. Z nich si vybereme ty, v nichž nastal i jev A. Ty tvoří zlomek P(A∩B) ze všech experimentů, takže z těch, kdy nastalo B, je to zlomek P(A ∩B) / P(B). Definujeme tedy:

Ve zmíněném příkladu dostaneme

což se opravdu rovná 2/3, protože všechny elementární jevy mají v našem případě stejnou pravděpodobnost.

Můžeme si to také představit tak, že z množiny všech elementárních jevů vyřadíme ty, o nichž víme, že nenastaly. Zbudou nám tedy ty elementární jevy, které leží v B. Počítáme-li pak pravděpodobnost jevu A, musíme vyřazené jevy smazat, tedy uvážit průnik A∩B. To ovšem nestačí: vyřazením jsme porušili pravidlo, že pravděpodobnosti všech elementárních jevů se sečte na jedničku: nyní se sečtou na P(B). Proto ještě „změníme měřítko“ vydělením všech pravděpodobností číslem P(B).

Nezávislé jevy

Nyní zkusíme hodit dvěma kostkami po sobě a výsledek přečíst jako dvojciferné desítkové číslo. Elementárních jevů je tedy celkem 36 jsou to čísla od 11 do 66. Uvažme tyto jevy:

Jejich pravděpodobnosti snadno spočítáme jako P(A)=P(B)=6/36=1/6 a P(C)=12/36=1/3.

Představme si nyní, že víme, že nastal jev A, tedy padlo jedno z čísel 11 až 16. Co jsme schopni říci o tom, zda nastal jev B? Jeho pravděpodobnost zůstává stále stejná: 1/6. Jev A nám tedy o jevu B nedává žádnou informaci. Tehdy říkáme, že jevy A a B jsou nezávislé.

Kdybychom naopak věděli, že nastal jev C, pravděpodobnost jevu A by se změnila na 1/2, protože z čísel 11 až 26 celá polovina začíná jedničkou. Tyto jevy jsou tedy závislé.

Nezávislost jevů A a B můžeme popsat požadavkem

Dosadíme-li definici podmíněné pravděpodobnosti, dostaneme:

čili

Za definici nezávislosti se většinou považuje tato poslední rovnost, protože funguje i pro P(B)=0, kdy by podmíněná pravděpodobnost nebyla vůbec definovaná. Také je z ní hned vidět, že nezávislost je symetrická vlastnost. Dodejme ještě, že samozřejmě platí i P(B | A) = P(B).

Definovat nezávislost pro více jevů je složitější, obecně nestačí říci, že pravděpodobnost toho, že nastanou současně, je součin jednotlivých pravděpodobností. Je potřeba, aby to platilo pro kteroukoliv podmnožinu jevů.

Náhodné proměnné a střední hodnota

Představme si nyní jednoduchý pravděpodobnostní algoritmus. Funkce random(x) bude vracet náhodné celé číslo z rozsahu 0 až x-1.

1. x ← random(2)
2. Pokud x=1:
3. y ← random(2)

Algoritmus si tedy hodí korunou (vygeneruje náhodný bit) a v případě, že padla jednička, hodí ještě jednou. Jak ho pomocí teorie pravděpodobnosti popíšeme? Možné průběhy výpočtu můžeme popsat jako elementární jevy. Jelikož pro pevný vstup (tady dokonce žádný nemáme) je průběh výpočtu jednoznačně určený hodnotami náhodných čísel, můžeme říci, elementární jevy jsou možné posloupnosti náhodných čísel.

Pro náš jednoduchý program to jsou posloupnosti 0, 10 a 11. Přitom 0 má pravděpodobnost 1/2, zbylé dvě 1/4.

Co kdybychom chtěli říci, jak dlouho náš program běží? Pro jednoduchost to budeme počítat v příkazech. V nejhorším případě se provedou 3, ale kdybychom to chtěli říci přesněji, mohli bychom říci, že pro posloupnost 0 se provedou 2, zatímco pro 10 a 11 se provedou 3. Doba běhu randomizovaného algoritmu je hezkým příkladem takzvané náhodné proměnné, kterou teď zavedeme obecně.

Když provedeme náhodný experiment (třeba hodíme kostkou), nastane jeden z elementárních jevů. Náhodná proměnná (nebo také náhodná veličina) je jedno číslo určené tím, který elementární jev nastal. Příkladem by mohla být náhodná proměnná L, která je 0, pokud padlo na kostce sudé číslo, a 1, pokud liché. Dalším příkladem náhodné proměnné může být třeba „číslo, které padlo na kostce, umocněné na druhou“. Tu označme třeba D.

Všimněte si, že podmínka, ve které figurují náhodné proměnné, vždy určuje nějaký jev: množinu elementárních jevů, pro které podmínka platí. Například L=1 platí pro {1,3,5}, D<10 pro {1,2,3} a D<10 ∧ L=0 pro {2}. Proto se můžeme ptát na pravděpodobnost toho, že podmínka platí, což se obvykle značí pomocí hranatých závorek: P[D<10] = P({1,2,3}) = 3/6 = 1/2.

Také se můžeme ptát, jaká je průměrná hodnota náhodné proměnné. Zkusme si to na proměnné D z předchozího příkladu, ale uvažujme obecné pravděpodobnosti stěn kostky p₁,… ,p₆ (kostka by tedy mohla být falešná). Představme si, že hodíme kostkou N-krát pro nějaké hodně velké číslo N. Jedniček padne přibližně p₁ · N, dvojek p₂ · N atd., takže průměr proměnné D vyjde:

To také můžeme zapsat jako

Je to tedy vážený průměr, v němž roli vah hrají pravděpodobnosti jednotlivých možností. Pro poctivou kostku (p₁=… =p₆=1/6) se z toho stane obyčejný aritmetický průměr s hodnotou 91/6.

Obecně můžeme definovat střední hodnotu náhodné proměnné X (značíme E[X]) jako průměr hodnot, které proměnná přiřazuje jednotlivým elementárním jevům, vážený pravděpodobnostmi těchto jevů:

kde suma probíhá přes všechny elementární jevy ω a X(ω) je hodnota proměnné pro elementární jev ω.

Pokud jsou hodnoty proměnné celá čísla, někdy je praktičtější pro každou hodnotu posbírat všechny elementární jevy, pro které proměnná této hodnoty nabývá. Dostaneme:

(Nenechte se vyvést z míry tím, že sčítáme nekonečně mnoho členů. Pro konečný počet elementárních jevů je jen konečně mnoho sčítanců nenulových.)

Lze matematicky dokázat (byť my to zde dělat nebudeme), že pokud zprůměrujeme hodně pokusů, bude výsledek blízko E[X], a pokud budeme průměrovat více a více pokusů, tak se bude přibližovat (jazykem matematické analýzy: průměr bude konvergovat) k E[X].

Linearita střední hodnoty

Jednou z důležitých vlastností střední hodnoty je, že je lineární. Tím se myslí, že pro libovolné dvě náhodné proměnné platí E[X+Y] = E[X] + E[Y] a také E[cX]=c · E[X] pro každé číslo c. Uvědomte si, že X+Y a cX jsou také náhodné proměnné.

Předtím, než tuto vlastnost dokážeme poctivě, rozmysleme si, že je velmi intuitivní. Představme si, že máme dva randomizované algoritmy používající náhodnost. Označme X a Y náhodné proměnné, které udávají jejich doby běhu. Linearita střední hodnoty pak říká, že když spustíme X a poté Y, bude průměrná celková doba běhu stejná jako součet průměrných dob běhu jednotlivých algoritmů. Podobně pokud algoritmus dvakrát zpomalíme, bude i průměrná doba běhu dvakrát větší. To není nikterak překvapivé.

Nyní matematický důkaz, nejprve pro násobení konstantou. Stačí dosadit do definice střední hodnoty:

A teď pro součet:

Raději zdůrazníme, že jsme nikde nepotřebovali předpokládat žádný druh nezávislosti: linearita střední hodnoty funguje za všech okolností.

Nyní si ukažme dva příklady využití linearity. Házíme dvěma kostkami, zapisujeme dvojciferný výsledek D a ptáme se, jaká je jeho střední hodnota E[D]. Mohli bychom zajisté rozebrat všech 36 možností, ale existuje jednodušší cesta. Uvážíme náhodné veličiny pro číslo na první kostce X a to na druhé Y. Jistě je D = 10X+Y, takže podle linearity E[D] = 10E[X] + E[Y]. Ovšem X a Y jsou úplně obyčejné hodnoty na kostkách, takže jejich střední hodnoty vyjdou (1+… +6)/6 = 7/2. Proto E[D] = (10+1) · 7/2 = 77/2.

V druhém příkladu hodíme N-krát kostkou a budeme se ptát, kolik padlo šestek. Označme tuto náhodnou proměnnou S. Elementární jevy jsou posloupnosti hodů, takže jich je 6^N. Ovšem E[S] spočítáme snadno trikem takřka kouzelnickým. Rozložíme S na součet proměnných S₁+… +S_N, kde S_i říká, kolik padlo šestek v i-tém hodu. To je trochu přihlouplá otázka, protože padla buď jedna, anebo žádná. Ale každopádně se snadno spočítá, že střední hodnota E[S_i] je 0 · P[S_i=0] + 1 · P[S_i=1] = P[S_i=1], což je pravděpodobnost, že v i-tém hodu padla šestka, tedy 1/6. Proto E[S] = E[S₁ + … + S_N] = E[S₁] + … + E[S_N] = N · 1/6 = N/6. Žádné překvapení se nekoná.

Mimochodem, tato úvaha je speciálním případem obecné techniky: Libovolnému jevu J můžeme přiřadit jeho indikátor, což je náhodná proměnná I_J, která nabývá hodnoty 1, pokud jev nastane, a jinak je nulová. Vychází pak E[I_J] = P[I_J=1] = P(J).

Lemma o džbánu

Představte si, že opakovaně házíte kostkou, dokud nepadne šestka. Kolikrát v průměru hodíte? Obecněji: opakujeme nějaký pokus, který se pokaždé povede s nějakou pravděpodobností p. Pokud vám to připomíná přísloví o chození se džbánem pro vodu, jste na správné stopě. Suchým vědeckým jazykem jde o tzv. střední hodnotu geometrického rozdělení, ale nám přijde džbán s vodou výstižnější.

Jak to zapadá do naší teorie? Posloupnosti hodů jsou elementární jevy, počet hodů je náhodna proměnná a my se ptáme na její střední hodnotu. Nenechte se prosím znepokojit tím, že elementárních jevů je nekonečně mnoho, s čímž naše teorie nepočítala. Pohybujeme se sice na tenkém ledu, ale slibujeme, že se nepropadneme, protože toto nekonečno je „dostatečně krotké“.

Lemma říká následující: Mějme džbán. Kdykoliv s ním jdeme pro vodu, tak se jeho ucho utrhne s pravděpodobností p, nezávisle (ve smyslu popsaném výše) na ostatních pokusech. Pak ve střední hodnotě půjdeme se džbánem pro vodu (1/p)-krát, než se ucho utrhne.

Než lemma dokážeme, rozmysleme si, co říká o našem čekání na šestku: Pravděpodobnost šestky je 1/6, takže v průměru hodíme 1/(1/6) = 6-krát.

Nyní důkaz: Nechť U je náhodná proměnná, která nám říká, při kolikátém pokusu se utrhlo ucho. Střední hodnotu budeme chtít spočítat podle definice:

Potřebujeme tedy znát pravděpodobnosti toho, že ucho se poprvé utrhne v i-tém kroku. Pro i=1 je to triviální: ucho se utrhne hned napoprvé s pravděpodobností p. Pro i=2 uvážíme, že se napoprvé neutrhlo (to má pravděpodobnost 1-p) a napodruhé utrhlo (tedy p). Jelikož oba jevy jsou nezávislé, můžeme jejich pravděpodobnosti vynásobit a dostaneme P[U=2] = (1-p) · p. Pro obecné i se při prvních i-1 pokusech ucho neutrhne a v i-tém pokusu utrhne, tedy dostaneme P[U=i] = (1-p)^i-1 · p.

Teď dosadíme spočtené pravděpodobnosti:

To je nějaká nekonečná suma, u níž budeme věřit, že se sečte na konečné číslo (znalci analýzy mohou použít podílové kriterium konvergence). Jak ji spočítáme?

Označme S hodnotu druhé sumy, platí tedy E[U] = pS. Abychom lépe viděli, co se děje, sumu si rozepíšeme:

Podívejme se, co se stane po vynásobení obou stran 1-p:

To se nepočítá o nic lépe, ale je to docela podobné výrazu pro S: v jednom případě je u (1-p)ⁱ koeficient i+1, v druhém i. Zkusíme tedy od sebe oba výrazy odečíst:

Levou stranu můžeme zjednodušít na pS, napravo je nějaká geometrická řada s kvocientem 1-p. Tabulkový vzoreček pro součet geometrické řady s kvocientem q říká, že q⁰ + q¹ + q² + … = 1/(1-q). V našem případě je q=1-p, takže pS = 1/(1-(1-p)) = 1/p. My už ovšem víme, že pS je také rovnou hledané střední hodnotě E[U]. Hotovo.

(Mimochodem, kdyby vám vrtalo hlavou, jak se odvozuje vzoreček pro součet geometrické řady, dělá se to trikem velmi podobným tomu našemu: Pokud G=q⁰+q¹+… , pak qG=q¹+q²+q³+… . Opět obě řady odečteme a získáme G-qG = q⁰ = 1. Proto (1-q)G = 1, a tedy G=1/(1-q).)

Odbočka k hledání pivota

Lemma o džbánu si vyzkoušíme na analýze algoritmu. V třídícím algoritmu Quicksort potřebujeme najít pivota, který bude přibližně mediánem. Řekněme, že v setříděném pořadí prvků má pivot ležet v prostřední třetině. Pak by stále platilo, že Quicksort poběží v čase O(n log n). Jak ale takového pivota najít? Pomůže jednoduchý pravděpodobnostní algoritmus: vybereme pivota náhodně ze zadaných prvků, spočítáme, kolik prvků je menších a kolik větších, a pokud pivot neleží v prostřední třetině, algoritmus prostě zopakujeme.

Jeden průchod algoritmu trvá O(n). Algoritmus může uspět hned v prvním průchodu, takže v nejlepším případě skončí v lineárním čase. Také by se mohlo stát, že budeme mít smůlu a pokaždé vybereme minimum, a tehdy se algoritmus nezastaví nikdy – to nás ovšem nemusí trápit, tento průběh algoritmu má pravděpodobnost rovnu 0.

Ukážeme, že průměrná časová složitost je také lineární. Střední hodnota času výpočtu je určitě O(n) krát střední hodnota počtu průchodů (všimněte si, jak jsme zde použili linearitu střední hodnoty). Průchod uspěje, pokud se trefí do prostřední třetiny. Jelikož všechny prvky vybíráme se stejnou pravděpodobností, nastane to s pravděpodobností 1/3. Podle lemmatu o džbánu tedy musíme udělat v průměru 3 průchody, než se ucho utrhne a my najdeme prvek v prostřední třetině.

Zesilování pravděpodobnosti

Představme si nakonec, že máme nějaký pravděpodobnostní algoritmus, který vždy doběhne rychle, ale nezaručuje správný výsledek. Typickým příkladem je třeba takzvaný Rabinův-Millerův test prvočíselnosti. Nebudeme ho vysvětlovat detailně, podrobnosti najdete například v Medvědových Algoritmech okolo teorie čísel. Důležité ale je, že se chová takto: Dáme-li mu na vstupu prvočíslo, vždy správně odpoví „ano, je to prvočíslo.“ Složené číslo odhalí s pravděpodobností aspoň 1/2: pokud mu ho dáme, odpoví s pravděpodobností alespoň 1/2 ne, jinak ano.

Poloviční pravděpodobnost chyby nezní moc užitečně, ale můžeme ji snadno vylepšit tím, že algoritmus k-krát zopakujeme. Číslo budeme považovat za prvočíslo jen tehdy, když se na tom shodlo všech k opakování algoritmu.

Jaká je nyní pravděpodobnost chyby? Pokud je číslo doopravdy prvočíslem, pokaždé to zjistíme správně, takže celkově odpovíme ano. Pokud je složené, odpověděli bychom špatně (tedy ano) jen tehdy, kdyby se každé z k spuštění algoritmu zmýlilo. Jelikož tato selhání jsou navzájem nezávislá (algoritmus si pokaždé vygeneruje nová náhodná čísla nezávisle na těch předchozích), pravděpodobnost k selhání je nejvýš (1/2)^k = 1/2^k. Už pro k=10 je to méně než 1/1000.

Tomuto triku se říká zesilování pravděpodobnosti (anglicky probability amplification). Zatím jsme ho použili pro stlačení pravděpodobnosti chyby pod libovolně nízkou (ale kladnou) konstantu. Někdy se ovšem hodí umět víc.

Co kdybychom na prvočíselnost testovali N čísel? S původním Rabinovým-Millerovým testem bychom se mýlili v průměrně N/2 případech (pokud by všechna čísla byla složená). Pokud bychom chtěli stlačit průměrný počet chyb pod konstantu (řekněme pod 1), museli bychom pravděpodobnost chyby v jednom testu stlačit pod 1/N. Toho dosáhneme, pokud zvolíme k > log₂ N. Tím jsme algoritmus asymptoticky zpomalili (O(log N)-krát), ale to je poměrně malá cena za tak podstatné snížení chybovosti. Další zvětšování k snižuje chybovost exponenciálně: už pro k=2 log₂ N vyjde pravděpodobnost chyby 1/N².

Pár slov závěrem

Pokud se chcete dozvědět o pravděpodobnosti více, můžeme vřele doporučit skvělé přednášky z Harvardu. Jejich videozáznamy jsou dostupné na YouTube.

Až si někdy budete číst o pravděpodobnosti, nejspíš se setkáte s axiomy pravděpodobnosti zavedenými jinak, než jak jsme je zavedli my. Ty naše kuchařkové jsou intuitivnější, ale bohužel se nedají jednoduše zobecnit na nekonečné množiny. O „plnotučných“ Kolmogorových axiomech pravděpodobnosti se můžete dočíst ve Wikipedii.

Další jednoduché randomizované algoritmy a datové struktury najdete v knížce Průvodce labyrintem algoritmů. Inspirovat vás také může seriál z 16. ročníku KSP.

Pokud by vám i tak něco nebylo jasné, ptejte se na našem fóru.

Martin „Medvěd“ Mareš & Jakub Tětek

Menu