Nasledovná jednoduchá úloha ma dnes napadla pri čítaní učebnice teórie informácie. (Matematickým základom teórie informácie je teória pravdepodobnosti.)Blšia krajina je tvorená n dedinami rozmiestnenými vo vrcholoch pravidelného n-uholníka a jedným mestom. Keď sa blcha nachádza v dedine, skočí buď do niektorej z dvoch najbližších susedných dedín, alebo do mesta (každú z týchto troch možností si vyberá s pravdepodobnosťou 1/3). Ak je blcha v meste, skočí náhodne do niektorej z dedín (každú si volí s rovnakou pravdepodobnosťou). Predpokladáme, že blcha urobí jeden skok každú minútu a samotný skok trvá zanedbateľný čas. Blcha už takto skáče veľmi dlho. Odhadnite, s akou pravdepodobnosťou sa blcha práve nachádza v meste.
Na obrázku je ilustrovaná blšia krajina s n=6. Túto úlohu vie mechanicky vyriešiť každý, kto absolvoval prednášku z Markovovych reťazcov, ale s malým nápadom sa dá vyriešiť aj bez akejkoľvek vyššej matematiky.
Poznámka 31.7.: Trochu to zadanie upresním. Označme ako pn pravdepodobnosť, že po n skokoch sa bude blcha nachádzať v meste. Dá sa ukázať, že nezávise na tom, kde blcha svoje skoky začala, konverguje postupnosť p1, p2, p3, ... k pevnému číslu. Pýtame sa práve aké je to číslo.
da sa to zjednodusit na dva stavy:
OdpovedaťOdstrániť1-dedina
2-mesto
P(1->1) = 2/3
P(1->2) = 1/3
P(2->1) = 1
P(2->2) = 0
Comu zodpoveda matica:
|2/3 1/3|
|1 0 |
A staci vyriesit diferencnu rovnicu
ktora zodpoveda tejto matici (Lin. Alg. I)
Takze pravdepodobnost, ze bude
v dedine je 3/4, v meste 1/4.
hmm... aj ked to asi nebude
hladane riesenie...
ale mozno by sa dala ta diferencna
rovnica aj nejako pekne zamaskovat... :)
Nech X_t je poloha v case t, moze nadobudat hodnoty M (mesto) alebo D (dedina). Potom:
OdpovedaťOdstrániťP(X_t=M) = P(X_t=M|X_{t-1}=D) * P(X_{t-1}=D) + P(X_t=M|X_{t-1}=M) * P(X_{t-1}=M).
Oznacme si hladanu pravdepodnost P(X_t=M)=p. Podla zadania sa prva podmienena pravdepodobnost rovna 1/3 (prechod z D do M) a druha je nulova ("prechod" z M do M nie je mozny). Kedze hladame pravdepodobnosti v ustalenom stave, P(X_{t-1}=D) = 1-p. Dostavame teda rovnicu
p = (1/3)*(1-p)
a teda p = 1/4.
a co tak toto? :) http://lehuta.blog.sme.sk/clanok.asp?cl=158178
OdpovedaťOdstrániťHah. Veľmi dobre. Oba riešenia sú pekné a všeobecné.
OdpovedaťOdstrániťRiešenie od j má tú výhodu, že sa pomocou neho dá dosť mechanicky odvodiť všeobecný vzorec pre pravdepodobnosť p(n), že po n-tom skoku bude blcha v meste (ja som si to vypočítal: Ak blcha začínala v meste, tak p(n)=1/4+(3/4)*(-1/3)^n), ale treba ovládať nejakú tú techniku. Riešenie od ivana má zasa výhodu v tom, že takto sa to dá vysvetliť bystrému človeku aj bez hlbších matematických znalostí.
Ale ja mám ešte jedno neformálne, ale dosť presvedčivé riešenie:
Keďže blcha vykonáva skok z mesta na vidiek (čo je množina všetkých dedín), alebo z vidieku do mesta s pravdepodobnosťou, ktorá nezávisí na počte dedín n, tak zrejme ani hľadaná pravdepodobnosť nezávisí na n. Ak však uvažujeme špeciálne n=3, tak je každý uzol spojený s každým, preto z dôvodu symetrie musí byť pravdepdobnosť výskytu blchy v meste rovnaká ako pravdepodobnosť jej výskytu v ktorejkoľvek z troch dedín. Teda 1/4. :-))))
michal: zaujímavá úloha; ak budem mať dnes čas, skúsim sa na ňu pozrieť. Alebo ešte lepšie, napíšem nový príspevok a skúsime využiť dosť značnú riešiteľskú kapacitu čitateľov blogu QED :)
OdpovedaťOdstrániťmichal: Už som zistil, že riešenie Tvojej úlohy je 384/(45π), čiže približne 2,7162. Z vlastností strednej hodnoty náhodných premenných plynie, že sa jedná o trojnásobok dĺžky náhodne volenej úsečky v kruhu, čo je známy problém. Ako samostatnú úlohu to však na tento blog nedám, pretože vedie na dosť nechutný integrál.
OdpovedaťOdstrániťdakujem! :)
OdpovedaťOdstrániť