Re: Random Walk - ongelma

[vastaus aiempaan viestiin]

Nimim. "Richard" on 16.1 Suomi24-keskustelussa esittänyt kysymyksen

> "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..."
> 
> Onko tämä varmasti näin vai voisiko tässä
> käyttää aiemmin esitettyä kenttähahmotelmaa?

Hän lainaa Survo-keskustelussa esittämääni varsinaista ongelman
ratkaisun antavaa viestiäni, mutta hieman puutteellisesti, sillä
juuri ennen tuota lainausta esitän pienen laskelman 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

Käsittelen siinä symmetristä satunnaiskulkua, jossa E=0, enkä
alkuperäisen kysymyksen mukaista tilannetta, jolloin E=0.0619...
Halusin siis vain näyttää tämän erikoistapauksen avulla, ettei
u(n)-todennäköisyyksien summaa voi pitää kirpun paluutodennäköisyytenä.
Itse ratkaisuun ei noilla huomioilla ollut mitään merkitystä.

On kuitenkin paikallaan selventää todennäköisyyksien

u(n)=P[kirppu on origossa 2*n hypyn jälkeen], n=0,1,2,...

ja

f(n)=P[kirppu palaa origoon ensimmäisen kerran 2*n hypyn jälkeen],

välisiä suhteita. Ne tulevat parhaiten ilmi, kun otetaan käyttöön
lukujonojen {u(n)} ja {f(n)} generoivat funktiot U(s) ja F(s)

  U(s)=u(0)+u(1)*s+u(2)*s^2+...+u(n)*s^n+...
  F(s)=f(0)+f(1)*s+f(2)*s^2+...fu(n)*s^n+...

Sarjat suppenevat esim. muuttujan s arvoilla 0<s<1 ja jälkimmäinen
aina myös arvolla s=1.
Seuraavan tarkastelussa on luonnollista asettaa u(0)=1, f(0)=0.
Tällöin F(1) on todennäköisyys sille, että kirppu ainakin kerran
matkallaan palaa takaisin origoon.
Käyttäen hyväksi (ensimmäisessä viestissäni esittämääni) yhtälöä

   u(n) = f(1)u(n-1) + f(2)u(n-2) + ... + f(n-1)u(1) + f(n)u(0)

on helppo näyttää (kertomalla molemmat puolet potenssilla s^n ja
laskemalla yhteen arvoilla n=1,2,...),
että generoivia funktioita sitoo yhtälö U(s)-1=F(s)*U(s) eli

   F(s) = 1 - 1/U(s).

Paluutodennäköisyys on siis

   F(1) = 1 - 1/U(1),

missä U(1) on u(n)-todennäköisyyksien summa. Jos sarja
u(0)+u(1)+u(2)+... hajantuu, palataan origoon todennäköisyydellä
F(1)=1 ja näin tapahtuu kirppuesimerkissä ilmeisesti vain kun E=0.

Alkuperäisessä tehtävässä etsittiin sitä E-arvoa, jolla F(1)=0.5.
Edelläolevan perusteella tehtävä voidaan siis ratkaista myös
etsimällä E:tä, jolla U(1)=u(0)+u(1)+u(2)+...=2 eli (koska u(0)=1)
u(1)+u(2)+...=1. (Tällöin jäävät tosin f(n)-todennäköisyydet
delvittämättä.)
Seuraava laskennallinen koe vahvistaa tuloksen:
..........
Aikaisemmalla menettelyllä (ilman generoivia funktioita) saatiin
E=0.0619139544739914

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     ACCURACY=16
MAT U=ZER(n,1)
MAT #TRANSFORM U BY u(I#)
MAT S=SUM(U)
MAT_S(1,1)=0.9999999999999993

-Seppo

Luettelo keskustelunaiheista

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!