Budeme hádzať mincou až pokým nepadne znak dvakrát za sebou. Koľko budeme potrebovať v strednej hodnote (t.j. "v priemere") hodov?
Toto je pomerne prirodzená a častá úloha, ktorej riešenie však nie je úplne triviálne. (Jej ekvivalentná formulácia sa vyskytuje napríklad v tejto Oxfordskej učebnici).
5.8.: Úlohu sme už nielenže vyriešili (pozri komentáre), ale Peťo prišiel s takým postupom, ktorý sa dá použiť na vyriešenie oveľa všeobecnejšej úlohy:
Robíme nezávislé experimenty, pričom každý experiment môže skončiť výsledkom "úspech" (s pravdepodobnosťou p), alebo výsledkom "neúspech" (s pravdepodobnosťou 1-p). Skončíme akonáhle zaznamenáme k úspešných experimentov za sebou. Aká je stredná hodnota všetkých experimentov, ktoré vykonáme?
Výsledok je nasledovný:
S prvou formulkou sa ľahšie počíta ak je k veľké číslo, druhá mi však pripadá krajšia. V špeciálnom prípade, ktorý zodpovedá pôvodnému zadaniu, máme p=1/2 a k=2, čiže výsledok je 6. Ak by sme napríklad hádzali kockou a čakali na padnutie troch šestiek za sebou, tak p=1/6 a k=3, čiže očakávaný počet hodov je 6+62+63=258 :-)
Inak uvažujem, že vypíšem súťaž, ktorú vyhrá ten z Vás, kto nám pošle najzaujímavejšiu matematickú úlohu. Čo Vy na to? Svoje názory, prípadne organizačné pripomienky môžete písať do komentárov k tomuto príspevku a tiež sa môžete vyjadriť v novej miniankete (v pravom stĺpci blogu).
Ak som sa nesekol, riešenie je elegantne jednoriadkové a výsledok je 6.
OdpovedaťOdstrániťK súťaži o naj úlohu: chceš originálne úlohy alebo prevzaté?
OdpovedaťOdstrániťS prevzatými v množstve asi nebude problém, tam by som ja osobne navrhoval každému nasadiť jednu a uviesť zdroj... Takých by som mal desiatky...
Pri originálnych by som na počet podmienku nekládol...
Ešte by sa mohli úlohy radiť do kategórií:
1) "vystačíme si s logikou, resp. elementárnou matikou"
a
2) "úloha vyžaduje viac ako stredoškolskú matiku"
fu :) po piatich hodoch, ale to az ked som si vypisal 32 moznosti :) fakt nie je trivialne.. skusal som v akom zlomku pripadov je to po dvoch, po troch, po styroch, a kedy da ten zlomok jednu polovicu. ale tam som sa dost motal..
OdpovedaťOdstrániťteda, ze po piatich je to uz s p>1/2, cize do styroch hodov je v 1/2 moznozti splnena ta podmienka.
OdpovedaťOdstrániťv stvrtine pripadov po dvoch hodoch (11 zo styroch moznosti). v osmine po troch (011 z osem moznosti). ale v osmine aj po styroch (0011, 1011 zo sestnast moznosti). 1/4+1/8+1/8=1/2
OdpovedaťOdstrániťcize spravna odpoved je podla mna 4
OdpovedaťOdstrániťpeter: 6 sa mi zda strasne vela. Zeby predsa? Nuz prezrad...
OdpovedaťOdstrániťmichal: neberies do uvahy moznosti ovela dlhsich hadzani, ked sa to furt alternuje alebo padaju cisla.
Moje uvahy nedosli do ciela. Budoval som na znamom fakte, ze priemerna dlzka radu pokusov, kym nenastane jav s pravdepodobnostou 1/n je n.
Ked padnu dve rovnake za sebou? Ked prvy hod je lubovolny a potom je uz hadzanie s ocakavanym javom, ze padne v x.tom hode to iste ako v x-1.vom. Ten ma sam o sebe sancu 1/2, takze priemerna dlzka je 2 hody, dohromady teda potrebujem priemerne 3 hody na to, aby padli za sebou dve rovnake veci, bud dva znaky alebo dve cisla.
Ako sa z tejto 3 dostanem az na 6?! Hm...
neberiem do uvahy dlhsie moznosti, lebo som uz polovicu pravdepodobnosti obsiahol v 2, 3 a 4 hodoch :) sucet vsetkych ostatnych pravdepodobnosti musi byt ta druha 1/2, nie?
OdpovedaťOdstrániťMichal, to by potom ale tusim znamenalo, ze si nasiel median a nie strednu hodnotu.
OdpovedaťOdstrániťNech T je uvazovana nahodna premenna [pocet hodov do prveho dvojznaku].
OdpovedaťOdstrániťPotom, ak sa niekde nemylim,
E(T) = sum_{k=1}^{infty} P(T>=k)
= sum_{k=3}^{infty} P(T>=k-2)
= sum_{k=3}^{infty} 8*P(T=k)
= 8*[1-P(T=1)-P(T=2)]
= 8*(3/4) = 6
Ze P(T=k) = P(T>=k-2)/8 pre k>=3 sa da lahko presvedcit.
Tak vidím, že ste sa do tej úlohy pustili s vervou.
OdpovedaťOdstrániťMichal: Ako napísal Ruziklan, Ty si našiel medián, čo je také číslo m, že s pravdepodobnosťou aspoň 1/2 je výsledok menší rovný m a súčasne s pravdepodobnosťou aspoň 1/2 je výsledok väčší rovný m. (Tomuto vyhovujú všetky reálne čísla od 4 do 5). Medián je síce zaujímavá a pomerne často používaná štatistická charakteristika rozdelenia náhodnej premennej, ale medián nie je vždy rovný strednej hodnote. Strednú hodnotu si môžeš neformálne predstaviť ako to číslo, ku ktorému by sa blížil aritmetický priemer výsledkov, ak by si daný experiment opakoval ad infinitum.
Peter: Tvoj výsledok je správny a dôkaz veľmi elegantný! Ale ako jednoriadkové riešenie je to ťažko nazvať :-) Ak by som to mal napríklad vysvetliť študentom, tak by som musel ešte pár riadkov stráviť zdôvodnením tej prvej rovnosti a ešte tej Tvojej kľúčovej rovnosti P(T=k) = P(T>=k-2)/8 pre k>=3; ozaj, ako by si ju čo najstručnejšie zdôvodnil Ty?
Ja osobne som našiel riešenie, v ktorom je základom nasledovné pozorovanie: Pravdepodobnosť, že skončíme po n hodoch (pre n>=2) je rovná F(n-1)/2^n, kde F(k) je k-te Fibonacciho číslo. (To znamená, že pravdepodobnosti, že skončíme po 1,2,3,4,... hodoch sú 0, 1/4, 1/8, 2/16, 3/32, 5/64, 8/128, 13/256, ...)
Potom je už cesta jasná: Výsledok vypočítame pomocou explicitného tvaru k-teho Fibionacciho čísla, klasického vzorca na strednú hodnotu a vzorca na súčet radu s prvkami n*r^n.
aha, rozumiem, priemer, nie median. to tie nahodne vysoke cisla tahaju priemer hore (long tail:)
OdpovedaťOdstrániťMichal: Presne tak. Je to ako so mzdami. Medián mesačných zárobkov ľudí na Slovensku (t.j. také číslo, že polovica ľudí zarába menej a polovica viac) je podstatne menší ako priemer zárobkov. Ten "ťahá nahor" pár percent extrémne vysokých mesačných miezd.
OdpovedaťOdstrániťRado: No dobre, jeden riadok to nie je ;-) Povedzme že dva-tri, ak to teda napíšeme v TeXu a chceme byť veľmi struční :-) Ak to treba vysvetliť povedzme študentom na cviku z pravdepodobnosti, samozrejme máš čistú pravdu, a je potrebné ísť do väčších detailov!
OdpovedaťOdstrániťIdentita P(T=k) = P(T>=k-2)/8 pre k>=3 sa dá pozorovať nasledovne. Ak T=k, teda ak dva znaky padnú za sebou prvý raz v k-1 a k-tom hode, potom v (k-2)-hom hode musel padnúť "antiznak" (ako sa to vlastne volá? poznám rub/líc, head/tails..., že by hlava/znak? Normálne som pomýlený). A v žiadnom z predchádzajúcich k-3 hodov nesmel padnúť znak dvakrát za sebou; teda T>=k-2. Dostávame teda
P(T=k) = P(T>=k-2)*(1/2)*(1/2)*(1/2). Toto sedí pre k>=3.
Peter: OK. Ešte by som k Tvojmu riešeniu pre študentov asi dodal, že udalosť [T je menšie ako k+2] (čiže aj jej komplementárna udalosť [T je väčšie alebo rovné k+2]) závisí len na výsledkoch hodov 1,...,k-3, preto je nezávislá s udalosťou, že v hodoch číslo k+2,k+1 a k padnú postupne hlava, znak a znak. Z toho potom plynie, že príslušné pravdepodobnosti môžeme tak jednoducho násobiť ako si to napísal Ty. Každopádne, našiel si veľmi pekné riešenie!
OdpovedaťOdstrániťK tej súťaži: Súhlasím s Tvojimi poznámkami, nejako tak by som si to predstavoval. Problém je však v tom, že keď súťaž rozdelíme do veľa kategórií, tak v niektorých bude málo príkladov. Pochybujem napríklad, že dostanem spolu viac ako 10 príkladov. No, počkajme si na výsledok ankety. A ešte takáto maličkosť: možno by niekto chcel poslať aj taký príklad, ktorý sa mu zdá zaujímavý, ale nevie ho vyriešiť, čiže sa ani nedá povedať, či je stredoškolskej, alebo vyššej obtiažnosti.
Ruziklan: Tak zdá sa že som sa nesekol a je to tých 6. Inutitívne to neviem dobre zdôvodniť, ale je jasne že to bude viac ako 3 keďže aj malá pravdepodobnosť na veľkom čísle môže mať väčší efekt ako veľká na malom (keďže stredná hodnota je vážený priemer).
OdpovedaťOdstrániťRado: Nezávislosť - máš pravdu, treba to v každom detailnom riešení explicítne napísať.
Čo sa týka príkladov, počkám si na konečné pravidlá a na to ako sa prispievanie bude vyvíjať. Ak sa mi bude zdať, že to bude vhodné, kľudne dám do súťaže aj 5 úloh (nie vlastných) :-)
Ak budeš chcieť vlastné, určite tiež niečim prismejem.
Samozrejme, najviac som zvedavý na tie od ostatných prispievateľov! Očakávam dobrú zábavu :-)
Nuz, ved ani som nevravel, ze sa mylis, lebo som nevedel, akou metodou si to dokazal :-) ... len sa mi to v svetle mojho banalneho vysledku nejako vela... ale ked Tebe a Radovi vyslo zjavne roznymi metodami to iste, tak to asi bude dobre :-)
OdpovedaťOdstrániťPeter: Tvoje riešenie je skutočne super. Napríklad sa dá analogicky vypočítať stredná hodnota počtu hodov aj ak by sme čakali na všeobecne r znakov zasebou! (Vyjde to E(T)=2^(r+1)-2; overil som správnosť aj simulačne.) Pekne...
OdpovedaťOdstrániťMoje riešenie sa síce môže niekomu páčiť preto, lebo používa Fibonacciho čísla, ale takéto zovšeobecnenie by sa s ním robilo len veľmi komplikovane.
Rado: Tak to som rád, že sa s tým riešením dajú veci zovšeobecniť. A ešte radšej, že si sa vôbec nad tým zamyslel a pekne nám to tu napísal. Pekná a podnetná diskusia vždy poteší.
OdpovedaťOdstrániťRuziklan: Ja keď som včera večer okolo jedenástej išiel spať a uvidel Radov nový "post", nedalo mi to sa nad tým aspoň trochu nezamyslieť. Možno práve preto, že som bol unavený a lenivý vymýšľať niečo zdĺhavé, som si našiel skratku. Ale v tej únave som si nebol istý či to mám dobre a už som chcel ísť proste do hajan.
Tak som aspoň opatrne napísal: "Ak som sa nesekol,..." a "zábavu" overiť/zapudiť výsledok som nechal na ostatných.
Je dosť možné, že keby som nemal mozog v "alfa hladine", tak by som našiel niečo menej "elegantné".
No keď už som sa tak rozpísal a mimochodom prezradil že som kedysi dávno naletel Silvovu metódu :-), tak napíšem aj to, že vôbec na mnohé velké veci matematici neraz prišli keď boli chorí a v horúčkach (napr. môj bývalý šéf), prípadne aj v spánku (Ramanujan, ak sa nemýlim)!
Toto je samozrejme "iba" domáca úloha z jednej Radovej knihy, nič veľké a prevratné. To nám ale, a mne určite, neuberie z nevinnej intelektuálnej zábavy :-)
Inak ma (teda "mi", ale aj tak napíšem "ma") práve napadlo, že by sa mali priatelia a čitatelia tohto blogu raz do roka niekde stretnúť na pive/kofole. Možno práve preto, že som sa práve zobudil a z mozogu mi stále uniká "alfa žiarenie" :-)
Rado: no a ešte som chcel povedať, že o vzťahu s Fibonacciho postupnosťou som ani nesníval. Veľmi pekné. V tom je tá matematika taká krásna :-)
OdpovedaťOdstrániťDokonca sa veľmi elegantne dá vyjadriť očakávaný počet hodov kým uvidíme ľubovoľný konkrétny pattern hláv a znakov, a vždy je to celé číslo. Napr. na pattern HZHZZHZ budeme v priemere čakať 132 hodov.
OdpovedaťOdstrániť(Pre algoritmickejšie orientovaných: ide to spočítať v lineárnom čase od dĺžky patternu a súvisí to s týmto.)
misof: To je super; ďakujem za upozornenie na toto zaujímavé zovšeobecnenie nášho problému. Je mi jasné, že ten KMP algoritmus na hľadanie substringov je mimoriadne dôležitý; každý slušný textový editor musí nejaký taký algoritmus používať. Som rád, že sme sa od rekreačnej matematiky dostali až k serióznym aplikáciám.
OdpovedaťOdstrániťNemáš však náhodou aj nejaký link, na ktorom je popísané ako nájsť tú strednú hodnotu počtu hodov do prvého výskytu daného patternu? Možno by som bol schopný to aj odvodiť sám, mám ale taký pocit, že to už nie je až taká malina a svoju serióznu vedeckú kapacitu teraz musím venovať na niečo iné.