Ontola > diskuze
(Upr. 25.01. 23:54) | Nahlásit

Pravděpodobnost vygenerování sudého čísla

Přeji pěkný večer, kolegové,

nedávno jsem se setkal s na první pohled poměrně triviální úlohou na výpočet pravděpodobnosti. Bohužel se okolo postupu řešení rozvířila poměrně divoká názorová bouře. Uvedu zde tedy zadání úlohy, svoje přístupy k řešení a rovněž přístupy svých oponentů. Zajímalo by mě, jak byste k řešení přistupovali vy, a především by mě zajímal váš názor na to, proč tyto dva postupy vedou ke zcela odlišnému výsledku (tj. který přístup je nevalidní a ve kterém kroku).

Zadání zní přibližně následovně:

Uvažujme o potenciálním generátoru náhodných čísel, který náhodně generuje čísla z nekonečné množiny přirozených čísel (zde definováno jako kladná celá čísla). Jaká je pravděpodobnost, že takové náhodně vygenerované přirozené číslo bude sudé?

Dle mého názoru je zadání nedostatečné, protože vůbec nepopisuje, jaké diskrétní rozložení pravděpodobnosti tento generátor simuluje.
Generátor zde můžeme chápat jako náhodnou veličinu X, která nabývá hodnot z nekonečného výběrového prostoru Ω = N \ {0}. Náhodnou veličinu zde musí nutně popisovat diskrétní pravděpodobnostní funkce p: Ω -> <0,1>, kde Σ[i ∈ Ω](p(i)) = 1, tedy suma pravděpodobností všech jevů z výběrového prostoru je 1.
Jelikož zřejmě existuje nekonečné množství různých takových funkcí p, pak předpokládám (a dále nedokazuji), že pro každé x ∈ <0,1> existuje taková pravděpodobnostní funkce p_x, aby platilo Σ[i ∈ Ω](p_x(2*i)) = x, tedy můžeme sestrojit všechny takové náhodné veličiny X, aby pravděpobnost, že tato náhodná veličina nabude sudé hodnoty, byla potenciálně rovna všem hodnotám z intervalu <0,1>.
Tedy ještě jednou a lidsky - odpovědí na úlohu by bylo, že pravděpodobnost vygenerování sudého čísla může být libovolná, tj. jakékoliv číslo z intervalu <0,1>, přičemž záleží na zvoleném rozložení pravděpodobnosti.

Pokud bychom však zadání upravili a dodali, že každé číslo může být vygenerováno se stejnou pravděpodobností, pak dle mého názoru neexistuje žádné řešení, protože taková náhodná veličina nemůže ani teoreticky existovat. Jelikož totiž neexistuje žádná nekonečná řada daná aritmetickou posloupností s nulovou diferencí (tj. geometrickou posloupností s kvocientem 1), která by konvergovala k hodnotě 1, pak není možné sestrojit žádnou takovou pravděpodobnostní funkci, která by tuto náhodnou veličinu popisovala. Úloha by tedy neměla žádné řešení, nemůžeme určit pravděpodobnost, že náhodná veličina nabude sudé hodnoty, protože náhodná veličina splňující zadané podmínky nemůže existovat.

Tolik k mému řešení úlohy, nyní bych popsal alternativní řešení oponentů, které vede k úplně jiným výsledkům. V tuto chvíli předpokládáme, že pravděpodobnost, že náhodná veličina nabude nějaké hodnoty, je pro všechny prvky výběrového prostoru dle zadání stejná.

Toto řešení využívá jiné přístupy. Předpokládáme, že generujeme náhodná čísla z množiny N_a ≜ {n ∈ N \ {0}|n<=a}, tedy z množiny N_a, která obsahuje všechna přirozená čísla menší nebo rovna a. Tato množina tvoří výběrový prostor diskrétní náhodné veličiny X_a, jejíž pravděpodobnostní funkce je definovaná jako p(X_a = x) = 1/a, tedy každé číslo je generováno se stejnou pravděpodobností. Tuto náhodnou veličinu sestrojit můžeme, neboť její výběrový prostor je konečná množina.
Pro sudé a je v takové množině a/2 sudých čísel, zatímco pro liché a taková množina obsahuje (a-1)/2 sudých čísel, obecně tedy obsahuje ⌊a/2⌋ sudých čísel, kde ⌊.⌋: R -> Z je funkce zobrazující reálné číslo na nejbližší nižší (nebo stejné) celé číslo.
Pravděpodobnost, že náhodná veličina X_a nabude sudé hodnoty je tedy (⌊a/2⌋)/a.
Pokud budeme nyní a přibližovat nekonečnu, měli bychom potenciálně konvergovat k hodnotě, jež je rovna řešení úlohy.
lim[a -> ∞]((⌊a/2⌋)/a) = 1/2,
tedy pravděpodobnost, že náhodná veličina X_a pro nekonečný výběrový prostor nabude sudé hodnoty, je 1/2.

Jak tedy vidíte, byly použity dva postupy, které jsou na první pohled oba korektní (nebo tedy alespoň já prostě nevidím ani na jednom z nich žádný nedostatek). Velice by mě tedy zajímalo, jaký problém zde objevíte vy. Byl bych rád, kdybyste se zaměřili na to, v jakém kroku se které řešení rozpadá, a proč není možné jej použít. Jedno z nich totiž zřejmě závadné být musí, když každé vede k jinému výsledku. Děkuji předem za odpovědi a přeji příjemný zbytek večera.
Témata: Nezařazené

5 reakcí

| Nahlásit
Nerozumím řeči tvého kmene. :-) Tj., zkusím se na to podívat selským rozumem.

Generátor náhodných čísel je hod mincí, hrací kostkou a pod. I Schrödingerova kočka https://cs.wikipedia.org/wiki/Schr%C3%B6dingerova_ko%C4%8Dka může být užita jako generátor náhodných čísel.
Kdežto RNG v PC programu je "jen" generátor pseudonáhodných čísel. Řídí se programem, nikoli náhodou. Pokud by tohle bylo podstatou úlohy, tak by musel být uveden vzorec algoritmu RNG.

Dostát úloze můžeme tím, že budene házet tou mincí, libovolněkrát na jedno číslo od nejvyššího řádu čísla k nejnižšímu a tepve poslední hod určí, zda je číslo sudé nebo liché. Při řazení opačným směrem, od nejnižšího řádu k nejvyššímu to víme hned prvním hodem.
Úlohu tedy můžeme zjednodušit na jednu hodnotu, jeden hod mincí. Jaká je pravděpodobnost, že padne rub nebo líc. Pominame-li že může padnout na hranu. :-)

Pak tam máme v zadání "reálná čísla". A co nula? Nula je prý matematicky sudé číslo. Tedy ani v tom není problém.
https://forum.matematika.cz/viewtopic.php?pid=566621#p566621

I tady by měla platit Occamova břitva:
Latinská definice tohoto principu zní:

Pluralitas non est ponenda sine necessitate.
tj. Nemá se postulovat množství (důvodů či příčin), není-li to nezbytné.

nebo v pozdější formulaci

Entia non sunt multiplicanda praeter necessitatem.
tj. Entity se nemají zmnožovat více, než je nutné.

To se dá interpretovat dvěma mírně odlišnými způsoby. První lze popsat takto:

Pokud pro nějaký jev existuje vícero vysvětlení, je lépe upřednostňovat to nejméně komplikované.

Přesnější (užší) chápání Occamovy břitvy se týká části jedné teorie:

Pokud nějaká část teorie není pro dosažení výsledků nezbytná, do teorie nepatří.

https://cs.wikipedia.org/wiki/Occamova_b%C5%99itva
| Nahlásit
Řekl bych, že tohodle si je Wydygiz vědom. Jsem zvědav, jestli se tu najde někdo, kdo by se k tomu mohl fundovaně vyjádřit. Myslím, že sem pár takoých lidí chodí, ale obávám se, že tu nejsou denními návštěvníky.
(Upr. 26.01. 12:04) | Nahlásit
Přeji pěkné dopoledne, Anonyme Tifewaci,

ano, vím, že softwarové generátory náhodných čísel (např. kongruentní generátor, Mersenne twister a podobně) jsou typicky jen generátory pseudonáhodných čísel, neboť jejich náhodnost je jen zdánlivá. Chovají se při každém spuštění programu jinak kvůli rychlým změnám počátečního semínka (často jde o unixový čas, tj. počet sekund od 1. ledna 1970, který se příhodně mění každou sekundu). To je ale trochu na jinou debatu.
Takové generátory náhodných čísel, které dobře známe z počítačů, ale v tomto konkrétním příkladu selhávají, neboť každý datový typ má v počítači maximální velikost, tj. pokud bychom neustále přičítali jedničku k nějakému číslu, od určitého okamžiku bude číslo natolik velké, že nebude možné jej zobrazit, ono takzvaně přeteče do nejnižší možné hodnoty datového typu. Jelikož tedy nelze v počítači počítat s libovolně velkým číslem, pak všechny tyto generátory náhodných čísel mají nutně nějaký maximální možný modul, neboli něco jako horní hranici generátoru, tedy číslo, pro které platí, že žádné vyšší číslo už generátor vygenerovat nemůže. Jenže existuje samozřejmě nekonečné množství přirozených čísel vyšších než tento modul, tedy tento generátor nemůže přesně posloužit uvednému příkladu kvůli konečnosti jeho výběrového prostoru, což znamená, že množina vygenerovatelných čísel je konečná.
Abych uvedl příklad, datový typ uint32_t může uložit všechna celá čísla od 0 do 2^32-1, na žádné vyšší číslo už mu nestačí bity :).
Tedy kvůli této drobnosti nelze počítačové generátory náhodných čísel použít pro tento příklad. U nich je totiž vždy díky konečnosti výběrového prostoru možné vytvořit takový generátor, aby pravděpodobnost vygenerování každého čísla byla úplně stejná.

Problém s dalšími uvedenými příklady je v tom, že selský rozum naprosto selhává při čachrech se spočetným nekonečnem. Běžně se pravděpodobnost počítá jako podíl kardinality množiny jevů příznivých a kardinality množiny základového prostoru, pokud je pravděpodobnost každého z jevů stejná. Zde ale narazíme na problém, že mohutnost množiny přirozených čísel a mohutnost množiny sudých čísel je stejná (spočetně nekonečná), takže tento postup by nás vedl na neurčitý výraz nekonečno/nekonečno, který nedává žádný smysl.
Z tohoto důvodu jsem se chtěl trochu vyhnout úvahám typu "každé druhé číslo je sudé" nebo právě redukci každého čísla jen na jeho poslední cifru. Tím podle mě potíráme ty neintuitivní vlatnosti spočetného nekonečna a můžeme výsledek zkreslit.

Co se týče té sudosti nuly, to vůbec nevyvracím. Množinu přirozených čísel jsem raději explicitně definoval jen proto, že se dle typu úlohy někdy používá s nulou, někdy bez ní, proto je vždy lepší ji nejprve zadefinovat. Předpokládám, že její přítomnost v množině přirozených čísel by nic nezměnila, jen by se musel upravit postup druhého typu výpočtu uvedeného v prvním příspěvku.

Na závěr jen dodám, že přes to všechno je teoreticky možné zkonstruovat generátor náhodných čísel, který generuje čísla z celé nekonečné množiny přirozených čísel.
Představme si člověka, který má poctivou minci a schopnost pamatovat si libovolně velké přirozené číslo. Na počátku náhodného pokusu si pamatuje číslo 1. Hodí mincí. Pokud padne hlava, výsledkem je číslo, které si člověk myslí. Pokud padne orel, člověk přičte k číslu, které si pamatuje, jedničku a opět se přesouvá k fázi házení. Celé to opakuje tak dlouho, dokud nepadne hlava. Tehdy je výsledkem pokusu číslo, které si dotyčný pamatuje.
(Má to dva drobné praktické nedostatky:
- pravděpodobnost výskytu čísla není pro všechna přirozená čísla stejná, naše pravděpodobnostní funkce vypadá takto: p(X = a) = (2^-a) pro a ze základového prostoru přirozených čísel
- asi narázíme i na nějaké biologické limity lidské paměti, ale o tom nevím zhola nic)
Zde můžeme pohodlně provést součet nekonečné řady Σ[i ∈ N \ {0}](2^-(2i)) = (2^-2)/(1 - 2^-2) = 1/3, tedy odpověď by pro takový generátor byla zřejmá, pravděpodobnost vygenerování sudého čísla by byla 1/3.
Každopádně pokud se pokusíme pokus pozměnit tak, aby pravděpodobnost vygenerování každého přirozeného čísla byla stejná, zřejmě se nám vůbec nikdy nepovede takový pokus vymyslet, protože ani teoreticky neexistuje taková pravděpodobnostní funkce.
To je ale jen tak pro představu, neschopnost vymyslet praktický pokus samozřejmě nedokazuje, že v teoretické rovině nelze odpověď na původní úlohu najít.
| Nahlásit
„Matematika je jediný skutečně zaručený způsob, jak se zbláznit.“ — Albert Einstein
| Nahlásit
Přeji pěkný večer,

jen dodám, že srozumitelně bylo zodpovězeno na jiném fóru:

https://mathematicator.com/matematicke-forum/pravdepodobnost-vyberu-sudeho-cisla
 Anonym
Odpovídat lze i bez registrace. Dodržujte pravidla Ontoly
Vložit: Obrázek