On kolme huonetta A, B ja C. Markku on aluksi huoneessa A ja ilkeä velho siirtelee häntä joka päivä huoneesta toiseen tiettyjen todennäköisyyksien mukaan (nämä säilyvät vakiona: joka kerta kun ollaan huoneessa, niin seuraava valitaan sen huoneen siirtymätn:ien mukaan).
Markku saa valita luvun x, joka tarkoittaa todennäköisyyttä, että huoneesta A siirrytään B:hen. Lopulla todennäköisyydellä, eli tn:llä 1-x pysytään huoneessa A kun ollaan siinä. (A:sta ei siis ole suoraa siirtymää C:hen.). Velho kuitenkin vaatii, että x>=0,1. (Jos x=0, niin pysyttäisiin aina huoneessa A.)
Tämän jälkeen velho asettaa muiden huoneiden siirtymätodennäköisyydet seuraavasti:
B:stä A:han: 1/2 - (x^2)/3
B:stä B:hen: 0
B:stä C:hen: 1/2 (x^2)/3
C:stä A:han: x/6
C:stä B:hen: x/2
C:stä C.hen: 1-2x/3
Velho siirtelee Markkua sata päivää ja jos Markku tämän jälkeen on huoneessa C, joutuu hän velhon pataan. Kuinka Markun tulisi valita luku x ∈ [0,1, 1] minimoidakseen tämän todennäköisyyden?
Markku saa valita luvun x, joka tarkoittaa todennäköisyyttä, että huoneesta A siirrytään B:hen. Lopulla todennäköisyydellä, eli tn:llä 1-x pysytään huoneessa A kun ollaan siinä. (A:sta ei siis ole suoraa siirtymää C:hen.). Velho kuitenkin vaatii, että x>=0,1. (Jos x=0, niin pysyttäisiin aina huoneessa A.)
Tämän jälkeen velho asettaa muiden huoneiden siirtymätodennäköisyydet seuraavasti:
B:stä A:han: 1/2 - (x^2)/3
B:stä B:hen: 0
B:stä C:hen: 1/2 (x^2)/3
C:stä A:han: x/6
C:stä B:hen: x/2
C:stä C.hen: 1-2x/3
Velho siirtelee Markkua sata päivää ja jos Markku tämän jälkeen on huoneessa C, joutuu hän velhon pataan. Kuinka Markun tulisi valita luku x ∈ [0,1, 1] minimoidakseen tämän todennäköisyyden?
Vastaukset 2
Vanhimmat
Tämä on stokastinen prosessi, erityisesti Markov-ketju, jonka siirymämatriisi M on (anteeksi muotoilu):
1-x, x, 0
1/2 - (x^2)/3, 0, 1/2 (x^2)/3
x/6, x/2, 1-2x/3
Korotetaan M sadanteen potensiin. Tällöin oikeanpuoleiselle sarakkeelle kullekin riville tulee lausekkeet, jotka ovat suurella tarkkuudella lähellä toisiaan. Minimoidaan jokin näistä kolmesta x:n suhteen annetulla välillä. Näin saatu x:n arvo sijoitetaan kahteen muuhun lausekkeeseen, jotta nähdään kuinka monen desimaalin tarkkuudella vastaus on oikein. Tehtävä on helppo ratkaista numeerisesti millä tahansa matriisien käsittelyyn soveltuvalla ohjelmalla.
Totta, noinhan sitä saa testattuakin miten paljon on väliä mistä huoneesta aloitetaan.
Tehtävä on myös ihan käsipelissä ratkaistavissa kun ajattelee, että luku 100 on niin suuri, että raja-ratkaisu antaa hyvän approksimaation. Varsinkin kun x on nyt jonkin verran rajoitettu pois nollasta (se ei taida antaa nollalle oikeaa vastausta), minä sain sille lausekkeen
(4x^2 6) / (2x^2 8x 11)
Sen ratkaisun välivaiheessa oli x:llä jakaminen, joten ei sinällään ihme, että x=0 ei toimi.