[viesti Survo-keskustelupalstalla (2001-2013)]
| Kirjoittaja: | Seppo Mustonen |
|---|---|
| Sähköposti: | - |
| Päiväys: | 28.12.2005 11:28 |
Suomi24-keskustelun
http://keskustelu.suomi24.fi
säikeessä Tiede -> Marematiikka -> Soveltava tehtävä
on pohdiskeltu viikon verran seuraavaa ongelmaa:
:Kirppu aloittaa "puolueellisen" satunnaismatkansa pisteestä (0,0)
:äärettömän suuressa kaksiuloitteisessa kokonaislukukoordinaatistossa
:(ts. ei-jatkuva koordinaatisto). puolueellisen siten, että joka
:askeleella kirppu hyppää etelään tai pohjoiseen todennäköisyydellä 1/4,
:itään tn:llä 1/4 + E, ja länteen tn:llä 1/4 - E. Todennäköisyys, että
:kirppu palaa jossain vaiheessa hortoiluaan alkupisteeseen(0,0) on 1/2.
:
:Mikä on E?
Koska toistaiseksi kukaan osallistujista ei ollut jouluaattoon
mennessä mielestänyt kyennyt tai viitsinyt viedä ratkaisua loppuun asti
ja kysytyn suureen E arvoista oli esitetty vain erilaisia arvauksia,
osallistuin keskusteluun nimimerkillä "Satunnainen vierailija" ja
ilmoitin tekemäni pienen simulointikokeen perusteella, että E:n
likiarvo on 0.062.
En lähtenyt siinä vaiheessa esittämään tarkempaa ratkaisutapaa, koska
aikaisemmilla keskustelijoilla oli selvästi käyttökelpoisia ideoita.
Minulle tehtävä on sikäli tuttu, että olen tarkastellut sitä
symmetrisessä erikoistapauksessa E=0 Survon opetussarjassa
(DEMO -> OPETUS -> 7. Matemaattiset toiminnat -> 6. Todennäköisyyksien
laskentaa -> 7. Symmetrinen satunnaiskulku m-ulotteisessa avaruudessa).
Koska em. keskustelussa ei edelleenkään ole esitetty pätevää ratkaisua,
teen sen nyt tässä ja tulen lähettämään Suomi24-keskusteluun vain
eräitä kommentteja sekä linkin tähän viestiin.
Ratkaisu noudattaa samoja linjoja kuin edellä mainitun opetussarja-
esimerkki.
Olkoon P(n,x,y) todennäköisyys, että kirppu siirtyy n askeleella origost
(0,0) pisteeseen (x,y). Se on tällöin multinomitodennäköisyys
n!
P(n,x,y) = SUMMA --------------- *p1^i1*p2^i2*p3^i3*p4^i4,
i1-i2=x i1!*i2!*i3!*i4!
i3-i4=y
i1+i2+i3+i4=n
missä p1=p2=1/4, p3=1/4+E, p4=1/4-E
Silloin todennäköisyys, että kirppu on takaisin origossa 2*n askeleen
päästä (parittomilla askelilla se ei voi palata) on kirjoitettavissa
yksinkertaisena summana
n (2*n)!
u(n) = P(2*n,0,0) = SUMMA ----------------- * (1/16)^i*(1/16-E^2)^(n-i)
i=0 (i!)^2*[(n-i)!]^2
Nämä todennäköisyydet on laskettavissa Survon avulla esim. seuraavasti:
E=0 / symmetrinen tapaus
u(N):=for(i=0)to(N)sum(fact(2*N)/fact(i)^2/fact(N-i)^2*&
(1/16)^i*(1/16-E*E)^(N-i))
u(1)=0.25
u(2)=0.140625
u(3)=0.09765625
u(4)=0.07476806640625
u(5)=0.06056213378906
u(6)=0.05088901519775
Suurilla n-arvoilla (jotta välitulokset pysyisivät liukulukulaskennan
tarkkuuden rajoissa) u(N) on paras kirjoittaa logaritmien kautta
(lfact() on kertoman logaritmi) muodossa
................
E=0
u(N):=for(i=0)to(N)sum(exp(lfact(2*N)-2*lfact(i)-2*lfact(N-i)&
-i*log(16)+(N-i)*log(1/16-E*E)))
jolloin esim. sadan ensimmäisen termin summa
s=for(i=1)to(100)sum(u(i))
on
s=1.5345272637223
Suomi24-keskustelussa muutamat ovat kuvitelleet, että po.
todennäköisyyden voisi laskea näiden u(n)-todennäköisyyksien summana.
Tämähän ei voi pitää paikkaansa, koska jo tuo 100 ensimmäisen termin
summa ylittää ykkösen.
On huomattava, että u(n) ilmoittaa todennäköisyyden, että kirppu on
2*n askeleen kuluttua origossa, mutta se on voinut olla siellä jo
aikaisemmin 1,2,.. ja jopa n-1 kertaa.
Siis näistä u(n)-luvuista ei saada suoraan vaadittavaa todennäköisyyttä,
vaan on laskettava todennäköisyydet
f(n)=P[kirppu palaa ensimmäisen kerran takaisin origoon askeleella 2*n],
jolloin näiden summa
oo
P = SUMMA f(n)
n=1
on varsinaisen kiinnostuksen kohde.
Todennäköisyydet f(n) voidaan kuitenkin laskea u(n)-lukujen avulla.
Koska askeleella 2*n voidaan olla takaisin origossa niin, että
se tapahtuu ensimmäisen kerran jollakin askelmääristä 2,4,...,2*n,
saadaan kokonaistodennäköisyytenä
u(n) = f(1)u(n-1) + f(2)u(n-2) + ... + f(n-1)u(1) + f(n)
eli tästä kääntäen
f(n) = u(n) - f(1)u(n-1) - f(2)u(n-2) - ... - f(n-1)u(1),
joten tässä on kaava, jolla luvut f(n) voi laskea edeltävien u- ja
f-lukujen avulla, kun lähtökohtana on f(1)=u(1).
Lasketaan Survon matriisitulkilla luvut f(n), n=1,2,...,1000, kun
E=0.062 (joka tekemäni simulointikokeen perusteella vaikutti antavan
lähellä arvoa 0.5 vastaavan todennäköisyyden sille, että kirppu edes
kerran matkallaan palaa takaisin origoon).
Aluksi lasketaan ja talletetaan luvut u(n), n=1,2,...,1000 vektoriin U:
................
E=0.062
u(N):=for(i=0)to(N)sum(exp(lfact(2*N)-2*lfact(i)-2*lfact(N-i)&
-i*log(16)+(N-i)*log(1/16-E*E)))
n=1000
MAT U=ZER(n,1)
TIME COUNT START
MAT #TRANSFORM U BY u(I#) / *U~T(U_by_u(I#)) 1000*1
TIME COUNT END 51.219
Koska palautuvien tapahtumien yhteydessä usein tarvitaan äsken johdettua
palautuskaavaa u-luvuista f-lukuihin, olen liittänyt Survon
matriisitulkkiin operaation, joka laskee u-lukujen vektorista U
f-lukujen vektorin F:
MAT #U_TO_F U TO F / *F~U_TO_F(T(U_by_u(I#))) 1000*1
................
1000 ensimmäisen f-luvun summaksi saadaan
MAT S=SUM(F) / *S~SUM(U_TO_F(T(U_by_u(I#)))) D1*1
MAT_S(1,1)=0.4997831026674
Muuttamalla parametrin E arvoa kokeilevasti pari kertaa, lähimmäs
puolikasta tullaan arvolla E=0.0619138 jolloin 1000 f-todennäköisyyden
summaksi tulee 0.50000038949563.
Siis kysytty E-arvo on (noin) 0.06194.
................
Tähän tarkkuusluokkaan päästään hieman pienemmilläkin n-arvolla kuin
1000, mutta termejä tarvitaan joka tapauksessa satoja, sillä f(n)-
jono ei suppene geometrisesti vaan sen termit ovat likipitäen
muotoa a/n^b, missä b on suuruusluokkaa 1.6.
-Seppo
| Vastaukset: |
|---|
Survo-keskustelupalstan (2001-2013) viestit arkistoitiin aika ajoin sukrolla, joka automaattisesti rakensi viesteistä (yli 1600 kpl) HTML-muotoisen sivukokonaisuuden. Vuoden 2013 alusta Survo-keskustelua on jatkettu entistäkin aktiivisemmin osoitteessa forum.survo.fi. Tervetuloa mukaan!