Opica stotisíckrát náhodne udrie do klávesnice s 26 základnými písmenami, pričom pri každom údere zasiahne každé z písmen s pravdepodobnosťou 1/26. Čo má vo výslednom reťazci väčšiu strednú hodnotu: počet výskytov podreťazca "aaaa", alebo počet výskytov podreťazca "abcd"?
Odpovede na anticipované otázky: Ak sa v reťazci vyskytnú viac ako 4 a-čka za sebou, započítavame každý výskyt štvorice a-čiek ako rôzny podreťazec "aaaa". Čiže napríklad reťazec "xaaaaaaaay" obsahuje až 5 podreťazcov "aaaa", nie dva, zatiaľ čo reťazec "xabcdabcdy" obsahuje samozrejme len dva podreťazce "abcd". Túto úlohu mám od môjho kolegu Jana Somorčíka
intuicia mi hovori abcd - ale v tomto momente odo mna nechcite vediet preco :)
OdpovedaťOdstrániťnuz mne hovori intuicia ze castejsie bude aaaa lebo napr v aaaaa sa to nachadza 2x a pre abcd sa take neda najst.
OdpovedaťOdstrániťDá sa zodpovedať aj v istom zmysle opačná otázka: keď mám daný reťazec písmen, aký je očakávaný počet stlačení kláves, kým ho opica prvýkrát napíše?
OdpovedaťOdstrániťA ešte väčšia psina (s prudko neintuitívnym výsledkom) je, keď sa z toho spraví hra dvoch hráčov: Ty si povedz reťazec, ja si poviem iný rovnako dlhý, a potom pustíme opicu ku klávesnici a vyhráva ten, koho reťazec opica napíše skôr.
k intuicii - ked si clovek zoberie iba 5 pismenne slovo tak abcd je vo vsetkych moznostiach 52x a aaaa 51x (dufam, ze som dobre pocital :) )
OdpovedaťOdstrániťa pre 6 to pre aaaa je presne moj rok narodenia :) 1976 a pre abcd je to 2028 :)
OdpovedaťOdstrániťono co mi hovori intuicia, ze tie ktore sa mozu prekryvat (aaaaa moznost je jedna ale obsahuje 2x aaaa)
Wow. Intuícia ma zase oklamala.
OdpovedaťOdstrániťnejak mi tu nieje jasne ako to pocitame. zjednodusme si to na 5 znakov a 4 pismena {a,b,c,d}
OdpovedaťOdstrániť(abcd) mame 8x
abcda, abcdb, abcdc, abcdd, aabcd, babcd, cabcd, dabcd
(aaaa) mame 8x
aaaaa (2 vyskyty), aaaab, aaaac, aaaad, baaaa, caaaa, daaaa
co by znamenalo rovnako, alebo ak neberieme aaaaa ako 2 tak potom menej
ale uz upustam od "intuitivnej" predstavy, ze aaaa je castejsie
Braňo: aaaaa počítame ako dva rôzne výskyty reťazca aaaa. Snažil som sa na to upozorniť v poznámke pod zadaním úlohy.
OdpovedaťOdstrániťaha - tak tu poznamku som nejak prehliadol :) potom vysledky budu ine a potom sa ja asi zacnem priklanat k aaaa :)
OdpovedaťOdstrániť:) Braňovi najprv hovorila intuícia, že častejšie bude aaaa, no už od tej predstavy upúšťa a Rorimu najprv hovorila intuícia, že častejšie bude abcd, no teraz sa skôr prikláňa k aaaa.
OdpovedaťOdstrániťNaozaj nie je jednoduché intuitívne odhadnúť správny výsledok, hoci existuje veľmi jednoduché riešenie (určitým trikom). Úlohy of misofa sú o dosť ťažšie.
bohuzial ja v tychto dnoch mozem dat iba na intuiciu - niet casu na ine veci :(
OdpovedaťOdstrániťTrosku som nad tym rozmyslal kym som zaspal a tak si myslim, ze sanca bude rovnaka (co ja viem - nieco v tom zmysle, ze nahodne zvolim i - index do pola znakov a je rovnaka sanca ze tam bude aaaa alebo abcd)
OdpovedaťOdstrániťJa si myslim, ze ich bude v strednej hodnote presne rovnako. Mam ale velmi jednoduchu a nematematicku uvahu :)
OdpovedaťOdstrániťAsi sa zhodneme na 2 veciach :
1) retazec aaaa ma vyhodu v tom, ze sa mu "duplikuju" vyskyty, napr. aaaaa je za 2
2) retazec aaaa ma nevyhodu v tom, ze sa vybera z pismen, ktorych je tam v strednej hodnote 100000 / 26, retazec abcd sa vybera z 4x tolko pismeniek
Teraz teda je otazka, ci je "vyhoda" aaaa sposobena duplikovanim viac alebo menej ako 4-nasobna.
Tak sa nato pozrime uplne sedliackym rozumom, kolko tam je moznosti v idealnom pripade pre obidva retazce:
#znakov; max#aaaa; max#abcd
5; 2; 1
6; 3; 1
7; 4; 1
8; 5; 2 ....
1000; 997; 250
Jednuducho abcd v optimalnom pripade pribude dalsi vyskyt s kazdym 4-tym pismenom, pricom aaaa s kazdym.
Takze tie "vyhody" a "nevyhody" sa podla mna vykompenzuju a bude to v strednej hodnote presne rovnako.
Ja by som povedal, ze "aaaa" bude mat vyssiu strednu hodnotu.
OdpovedaťOdstrániťNech n je pocet vyskytov retazca "aaaa", resp. "abcd". Uvazujme, ze n je fixovana vonkajsia premenna naseho systemu (celeho textu), ktora ho obmedzuje, cize pre kazdu volbu n existuje nejaky priestor stavov, v ktorych sa system moze nachadzat. Cim vacsi je tento priestor, tym vierohodnejsie je, ze vonkajsia premenna n ma prave zvolenu hodnotu.
Najprv zvolme n = 0, cize v texte sa retazec nenachadza. Stavovy pristor je velkosti S(0). Teraz zvolme n = 1 a zistime, ako sa zmenila velkost stavoveho pristoru. Vyzadujeme, aby sa retazec nachadzal v texte prave raz a mozeme ho umiestnit kdekolvek. Takych moznosti je takmer 100000. Na mieste, kde ho umiestnime sa pred tym mohlo nachadzat 26^4 ~ 460000 roznych retazcov, teraz vsak uz len jeden. Cize velkost stavoveho priestoru sa zmensi na 100000/46000 ~ 1/5 povodnej velkosti.
Teraz zvysme n na n = 2. Tu je uz rozdiel, ze sa jedna o retazec "abcd" alebo "aaaa". Nie je mozne, aby sa druhy retazec "abcd" nejako prekryval s prvym retazcom "abcd", zatialco "aaaa" sa s prvym retazcom "aaaa" moze prekryvat niekolkymi sposobmi. U "abcd" bude faktor, o ktory sa zmensi stavovy pristor, vacsi.
V pripade "abcd":
S(1) = (100000-4)/26^4*S(0)
S(2) = (100000-4-7)/26^4*S(1) ~ 0.2*S(1) -- Ak prve "abcd" nie je pri okrajoch
V pripade "aaaa":
S(1) = (100000-4)/26^4*S(0)
S(2) = [(100000-4-7)/26^4*S(1) + 2/26^3 + 2/26^2 + 2/26]*S(1) ~ 0.3*S(1)-- Ak prve "aaaa" nie je pri okrajoch
(2/26^3, 2/26^2, 2/26 su prekryvy o 1-3 pismena zlava a zprava)
Vidime, ze velkost stavoveho priestoru v pripade "aaaa" klesa pomalsie ako pri "abcd". n = 0 je najvierohodnejsi pripad, n = 1,2,... postupne menej vierohodne. Velkosti stavoveho priestoru S(n) su vahami pri vypocte priemeru n. U "aaaa" v porovnani s "abcd" bude hodnotam n > 0 prisluchat vacsia vaha (graf S(n) bude "roztahanejsi" k vacsim n), cize aj priemer n (stredna hodnota pocetu vyskytov) bude vacsi.
(Uvaha je trochu analogicka k systemom v termodynamike: system - objekt, n - energia, S - entropia, dS/dn - teplota)
Mozno to nie je spravne riesenie, ale snad aspon zaujimave (-;
Ta stredna hodnota poctu vyskytov nejakeho 4-pismenoveho podretazca v stotisicznakovom retazci sa vypocita ako suma (cez vsetky mozne stotisicznakove retazce) zo sucinov ((pravdepodobnost vytukania opicou daneho stiticznakoveho retazca) krat (pocet vyskytov nasho 4-pismenoveho podretazca v danom stotisicznakovom retazci)). Kazde pismeno ma rovnaku pravdepodobnost, teda aj kazdy mozny vysledny retazec sa moze objavit s rovnakou pravdepodobnostou. Tuto pravdepodobnost mozem vynat pred sumu. Jedine, co ma teraz zaujima, je celkovy pocet vyskytov nasho 4-pismenoveho podretazca vo vsetkych moznych stotisicznakovych retazcoch.
OdpovedaťOdstrániťA teraz pride drobna finta: mna vlastne nezaujima aky je presny pocet vyskytov podretazcov aaaa a abcd, ja mam len porovnat pocet ich vyskytov. Napr. ak chcem dokazat, ze ich je rovnako vela, najdem medzi nimi bijekciu (ku kazdemu vyskytu retazca aaaa najdem prave jeden vyskyt retazca abcd, a naopak, ku kazdemu vyskytu abcd najdem prave jedno aaaa).
To sa da spravit celkom jednoducho: ku kazdemu aaaa viem priradit prave jedno abcd - take, ktore sa nachadza presne na tom istom mieste v stotisicznakovom retazci (ako bolo to vybrane aaaa), a zvysok retazca je presne rovnaky (okrem toho miesta, kde bolo vybrane aaaa, resp. abcd). Toto funguje aj naopak - kazdemu abcd je priradene prave jedno aaaa.
Tato uvaha sa da aplikovat pre akekolvek podretazce s akoukolvek dlzkou (samozrejme rovnakou), a pre akokolvek dlhy vysledny retazec.
Ďakujem za komentáre!
OdpovedaťOdstrániťUvediem veľmi jednoduché riešenie, ktoré je založené na vysokoškolskej teórii pravdepodobnosti.
Pre každé i=1,...,99997 nech náhodná premenná U_i nadobúda hodnotu 1 v prípade, že podreťazec od i-teho po (i+3)-tí znak bude "aaaa", a hodnotu 0 inak. Všimnime si, že všetky náhodné premenné U_i majú strednú hodnotu
E(U_i)=P[U_i=1]=1/(26^4).
Náhodná premenná N, ktorá zodpovedá počtu podreťazcov "aaaa" sa dá zapísať v tvare súčtu
N=U_1+...+U_99997.
Stredná hodnota má vlastnosť linearity, preto
E(N)=E(U_1)+...+E(U_99997)=99997/(26^4).
Tento výpočet by bol rovnaký (čiže by sme sa dopracovali k rovnakému číselnému výsledku) keby sme uvažovali akýkoľvek podreťazec dĺžky 4, čiže aj "abcd".