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?
Mikä on E?
Vastaukset 27
Vanhimmat
Mielestäni ongelman tekee varsin hankalaksi se, että ei tiedetä milla todennäköisyydellä kirppu hyppää etelään ja millä pohjoiseen. Tiedetään vain todennäköisyys, että etelään tai pohjoiseen hypätään todennäköisyydellä 1/4.
Toinen ongelma on hyppyjen pituuksien jakauma. Onko kaikki hypyt yhtä pitkiä?
Oletko bertie. jo yrittänyt..?
Vain sen verran todetakseni että en voi olla avuksi.
Olettaisin että tehtävä kuuluu tilastomatematiikan piiriin , josta pitäisi löytyä valmiit työkalut ongelman hallitsemiseksi.
Kyseessä taitaa olla kenttä, jonka sattumatiheys pienenee keskeltä ulospäin siirryttäessä tietyn jakauman mukaan ja E. n arvolla haetaan pistettä jossa P = 1/2 ( E =1/4 = kentän reuna).
Tietysti jos harrastusta riittää, niin voi laskeskella todennäköisyyksiä hyppymäärän mukaan ja muodostaa niistä joukon sarjoja, erottaa tekijäksi (1/4-E)*(1/4 E), yrittää ratkaista E kun P=1/2 mutta nähdäkseni työmäärä on aivan toivoton.
Nämä siis vain arvailuja.
Muuten
- Hyvää Joulua sinullekin -
Niin, löysin tämän tehtävän englanninkielisenä ja käänsin sen vapaasti kun näytti kiinnostavalta.
Kyseessä oli kilpailu, missä oli kymmenen tehtävää, tämä yhtenä niistä. Palkintona sata dollaria tyyliin eniten oikein kymmenestä.
Vastaustaulukossa oli E ~ 0,6 muistaakseni.
kiitos paljon
Jos jatketaan kenttähahmotelmaa ja oletetaan tiheysjakauman olevan normaalijakauma, siis noudattaa Gaussin käyrää, niin kentän reunalla jossa E = 1/4, kirppu ei voi hypätä itä-länsi- suunnassa ja palata lähtöruutuun (todennäköisyys toiseen suuntaan on 0 ), joten todennäköisyys paluulle on vain pohjois-eteläsuuntien hypyt, joka on joltisellakin vaivalla laskettavissa.
Ts, jos E =1/4, niin sain todennäköisyyden n. 0.135
Kun haet Gaussin käyrän jostain ja skaalaat sen niin että maksimi on 1 niin P = 1/2 on kohdassa 1.2 ja em. reunan todennäköisyys (P = 0.135) kohdassa n. 2.0
Siis tarkoittaa että lähtöpistettä pitäisi muuttaa 0.6 kertaa naksimimatkan (1/4) ja E olisi silloin 0.15.
Ja edelleen voit suhtautua tähän "arvailuun" varauksella.
Ps E=0.6 johtaisi negatiiviseen todennäköisyyteen, joka ei tunnu tutulta.
Oikea E:n arvo on likimain 0.062 saatuna
pelkällä simulointikokeella.
Jos viitsit näin jouluna niin kiinnöstaisi tietää minkä P- arvon saat kun E =0.25 ja kun E =0 ?
Olet siis jo päässyt tuloksiin? Totta, likimain 0,062 se olikin kun tarkistin..
Kiinnostaa vain, missä meni noin pahasti metsään ?
Selviää varmaan jos löytyis tuo P (E=0)
Kun E=0.25, paluutodennäköisyys on noin 0.134.
Kun E=0, palataan todennäköisyydellä 1.
Jälkimmäinen tulos löytyy todistettuna mm. William Fellerin
erinomaisesta kirjasta
An Introduction to Probability Theory and Its Applications, Vol.I.
On mielenkiintoista, että symmetrisessä (E=0) satunnaiskulussa yksi- ja
kaksiulotteisessa avaruudessa palataan lähtökohtaan todennäköisyydellä 1,
mutta esim. kolmiulotteisessa satunnaiskulussa todennäköisyydellä, joka
on vain noin 0.34. "Avaruuskävely on siis olennaisesti vaarallisempaa
kuin harhailu tasossa."
Kaikissa dimensioissa tosin paluun odotusaika on ääretön.
Symmetrisestä satunnaiskävelystä eri ulottuvuuksissa löytyy
havainnollistuksia esim. Survo-ohjelmiston suomenkielisestä
opetussarjasta.
Survon supistetun version (Lite) voi ladata ilmaiseksi osoitteesta
www.survo.fi
Tätä aihetta kuvaavaan demoon pääsee pitkin reittiä
DEMO -> OPETUS -> 7. Matemaattiset toiminnot
-> 6. Todennäköisyyksien laskentaa
-> 7. Symmetrinen satunnaiskulku m-ulotteisessa avaruudessa.
No samoista lukemistahan sitä lähdettiin, mutta mieleen hiipi epäilys kun ei meinannut sopia tulokseen.
Huomasin sitten typerän mokani, olin näet katsonut
Gaussin käyrästä suoraan arvon 0.5 kohdalta, kun todennäköisyys kuuluu tietysti hakea kertymäkäyrästä, jolloin likimääräinen tuloskin on jotakuinkin sama.
Hyvää joulua edelleen, ja kiitokset vaivannäöstä.
Täsmennyksenä edelliseen viestiin:
Kun sanoin
"Kaikissa dimensioissa tosin paluun odotusaika on ääretön."
tarkoitin tällä sitä, että keskimääräinen askelmäärä, jonka kirppu
tarvitsee palatakseen lähtökohtaansa, on ääretön symmetrisessäkin (E=0)
satunnaiskävelyssä.
Paluuajan jakauman luonnetta kuvaa sekin, että kaksiulotteisessa
tapauksessa palataan kyllä alkuun jo 100 ensimmäisen askeleen aikana
ainakin kerran todennäköisyydellä 0.58 (likiarvo), mutta
todennäköisyydellä 0.19 (likiarvo) ei ole palattu kertaakaan miljoonan
askeleen aikana.
Vaikka bertie sanoo saaneensa kenttähahmotelmansa kautta oikeat
tulokset, en ole vakuuttunut tuon lähestymistavan pätevyydestä.
Esim. viestissään 24.12 hän toteaa:
> Jos jatketaan kenttähahmotelmaa ja oletetaan tiheysjakauman olevan
> normaalijakauma, siis noudattaa Gaussin käyrää, niin kentän reunalla
> jossa E = 1/4, kirppu ei voi hypätä itä-länsi- suunnassa ja palata
> lähtöruutuun (todennäköisyys toiseen suuntaan on 0 ), joten
> todennäköisyys paluulle on vain pohjois-eteläsuuntien hypyt, joka on
> joltisellakin vaivalla laskettavissa.
>
> Ts, jos E =1/4, niin sain todennäköisyyden n. 0.135
Jos siis riittäisi tarkastella vain pohjois-eteläsuuntien hyppyjä,
tehtävä palautuu yksiulotteiseen satunnaiskulkuun, jossa yleisillä
siirtymätodennäköisyyksillä p,q (p q=1) todennäköisyys palata
lähtökohtaan on (kts. esim. Feller) 1-|p-q|.
Koska prosessi pohjois-eteläsuunnassa on symmetrinen eli p=q=1/2,
niin paluutodennäköisyys olisi 1 eikä 0.135.
En tunne Fellerin teoriaa mutta käsittääkseni tässä ei ole kysymys yksiulotteisesta tapauksesta koska kirpullahan on joka hypyllä 50% mahdollisuus hypätä sivusuunnassa josta ei ole paluuta, joten p+q ei ole 1 eikä kumpikaan ole 1/2.
Myöskään P=1 kun E=0.25 ei näin ollen ole mahdollinen.
> En tunne Fellerin teoriaa mutta käsittääkseni tässä ei ole kysymys
> yksiulotteisesta tapauksesta koska kirpullahan on joka hypyllä 50%
> mahdollisuus hypätä sivusuunnassa josta ei ole paluuta, joten p+q ei
> ole 1 eikä kumpikaan ole 1/2. Myöskään P=1 kun E=0.25 ei näin ollen
> ole mahdollinen.
Voitko siinä tapauksessa ilmoittaa täsmällisen matemaattisen
lausekkeen po. todennäköisyydelle?
On vain tyydyttävä likiarvoon
Kirpun reitin todennäköisyys lienee aika helppo laskea hyppymäärän mukaan ja sarjaa voi jatkaa halunsa mukaan tai siksi kunnes katsoo tarkkuuden riittävän.
Sarja on suppeneva ja kahden peräkkäisen termin suhde lähenee kai arvoa 1/4 (vain parilliset hypyt palaavat lähtöruutuun ja jokaisella hypyllä on vältettävä se 50% sivuhyppy), joten kovin kauaksi ei merkitseviä numeroita edes tarvitse laskea.
bertie kirjoitti 27.12:
> On vain tyydyttävä likiarvoon
Käytännössä kylläkin, mutta on olemassa algoritmisia ratkaisuja, joilla
saavutetaan haluttu tarkkuus.
> Kirpun reitin todennäköisyys lienee aika helppo laskea hyppymäärän
> mukaan ja sarjaa voi jatkaa halunsa mukaan tai siksi kunnes katsoo
> tarkkuuden riittävän.
Jos näin helppoa on, miksi et ole laskenut sitä. Aikaisemmin puhuit
jostain kenttähahmotelmasta, joka lienee jotain muuta kuin sarjan
laskemista.
> Sarja on suppeneva ja kahden peräkkäisen termin suhde lähenee kai arvo
> 1/4 (vain parilliset hypyt palaavat lähtöruutuun ja jokaisella hypyllä
> on vältettävä se 50% sivuhyppy), joten kovin kauaksi ei merkitseviä
> numeroita edes tarvitse laskea.
Se sarja, jolla tulos saadaan, ei suppene niin nopeasti kuin arvelet
enkä ymmärrä mitä tarkoitat "sivuhypyn välttämisellä".
Termejä joudutaan laskemaan satoja.
En halua venyttää kommenttiani tässä pitemmäksi vaan viittaan
uuteen viestiin, jonka olen juuri lähettänyt Survo-ohjelmiston
käyttäjien keskusteluun (www.survo.fi -> Keskustelu -> Random Walk -
ongelma). Toivon, että asiasta kiinnostuneet tutustuvat siihen.
Tuossa viestissä esitän yksityiskohtaisesti, miten tehtävä ratkaistaan
ns. palautuvien tapahtumien teorian avulla. Ratkaisun ymmärtäminen
ei edellytä muuta kuin todennäköisyyslaskennan perustietojen hallintaa.
Ratkaisu (kirpun 2000 ensimmäistä hyppäystä tarkastelemalla) antaa
kysytylle parametrille E likiarvon 0.06194.
Aloitetaan nyt vaikka siitä todennäköisyyden laskemisesta kun E= 0.25.
Hyppyjen lukumäärän mukaan voi laskea yksinkertaiset todennäköisyydet paluulle, esim 2 hypyllä se on 1/4*1/4 ja tämä tiertysti molempiin suuntiin joten se on 2/16, 4 hypyllä 2/16^2 6 hypyllä 4/16^3 8 hypyllä 10/16^4 jne.
Kun edelleen jatketaan sarjaa, niin pelkkä tieto että se suppenee ja peräkkäisten termien suhde on korkeintaan 1/4 antaa kyllä riittävän tarkkuuden.
Jos jatketaan vaikka tuosta viimeisestä termistä ja oletetaan se suhde 1/4 niin sen vaikutus voi olla vain pari yksikköä neljänteen desimaaliin jolla tuskin on suurta merkitystä.
Tähdennän vielä että tässä lasketaan todennäköisyyttä tilanteessa jossa E=0.25 se tarkoittaa että itä-länsi suunnassa hyppyjen todennäköisyys on 0 / 50 % ja tällä haetaan vain todennäköisyyttä tässä nimenomaisessa pisteessä eikä se vaadi todellakaan kovin montaa laskutoimitusta sadoista puhumattakaan.
Koko kenttähahmotelman tarkoitus oli vain selvittää menettelytapaa, jolla tällaisia tehtäviä voi ratkaista, eli oletetaan tiheysjakauma normaalijakauman mukaiseksi ja sen hallintaan tarvitaan ainakin yksi väliarvo ja kyseinen todennäköisyys oli kai ainoa järjellisellä työmäärällä ratkaistavissa..
Jos katsot viestiketjua tarkemmin niin toteat että todennäköisyyden laskeminen tavanomaisin keinoin on toivotonta ja yritin vain esittää erilaisen lähestymistavan ongelmaan.
Lisäksi oletin että kysyjän tarkoituksena ei ollut kysyä vastausta, vaan tapaa jolla vastauksia voi löytää ja olen kyllä tietoinen että tällaisten ongelmien käsittelyyn on kehitetty lukuisia teorioita ja valmiita laskentaohjelmia mutta niitä tässä tuskin haettiin.
Mitä tulee antamaasi tarkkuuteen, ne ovat pelkkiä numeroita, joilla ei ole käyttöä.
Ongelman ratkaisuun riittää mainiosti käyristä piirtämällä tulevat lukemat jotain 0.05...0.085 välille, ovat paljon antoisampia kuin enterillä painamalla tulostuvat 6 desimaalia.
Aiheetta enempään.
>Aloitetaan nyt vaikka siitä todennäköisyyden laskemisesta kun E= 0.25.
>
>Hyppyjen lukumäärän mukaan voi laskea yksinkertaiset todennäköisyydet
>paluulle, esim 2 hypyllä se on 1/4*1/4 ja tämä tiertysti molempiin
>suuntiin joten se on 2/16, 4 hypyllä 2/16^2 6 hypyllä 4/16^3 8 hypyllä
>10/16^4 jne.
Tarkasteltavat todennäköisyydet käyttäytyvät eri tavoin riippuen
parametrin E arvosta.
Ei ole mitään tarvetta tarkastella erikoistapausta E=0.25, koska se
on kaukana siitä kysymyksestä, johon etsittiin vastausta eli millä
arvolla E paluutodennäköisyys on 1/2.
Tällöin oikeat arvot ovat suuruusluokkaa E=0.062 ja todennäköisyydet
ensimmäiselle paluulle lähtökohtaan 2n askeleen jälkeen ovat
seuraavassa taulukoituna (edellisen viestini linkissä olevien
laskelmien mukaan) kun n=1,2,...,20 arvolla E=0.0619138
n_ f(n)____ f(n 1)/f(n)
01 0.242333 -
02 0.073363 0.30274
03 0.039104 0.53302
04 0.025245 0.64557
05 0.017984 0.71238
06 0.013604 0.75645
07 0.010717 0.78778
08 0.008692 0.81105
09 0.007207 0.82915
10 0.006080 0.84362
11 0.005200 0.85526
12 0.004498 0.86500
13 0.003928 0.87328
14 0.003457 0.88009
15 0.003064 0.88632
16 0.002732 0.89164
17 0.002449 0.89641
18 0.002205 0.90037
19 0.001994 0.90431
20 0.001810 0.90772
summa 0.475666
20 ensimmäisen todennäköisyyden summa 0.475666 poikkeaa vielä paljon
lopullisesta arvosta 0.5. Kun peräkkäisten arvojen suhde kasvaa koko
ajan lähestyen ykköstä, ollaan kaukana minkään geometrisen sarjan
käyttäytymisestä. Suppeneminen on hidasta. Tarvitaan siis satoja termejä.
Esim. 200 ensimmäisen termin summa on 0.499991.
>Jos katsot viestiketjua tarkemmin niin toteat että todennäköisyyden
>laskeminen tavanomaisin keinoin on toivotonta ja yritin vain esittää
>erilaisen lähestymistavan ongelmaan.
Esittämäni keinot ovat aivan tavanomaisia todennäköisyyslaskennan
perustiedot kunnolla osaavalle eikä tuloksen saaminen ole ollut
mitenkään toivotonta. Haluaisin edelleen nähdä tarkan kuvauksen siitä,
miten tuolla erilaisella lähestymistavalla selvitetään alkuperäinen
ongelma.
Satunnainen vierailija kirjoitti:
"En halua venyttää kommenttiani tässä pitemmäksi vaan viittaan
uuteen viestiin, jonka olen juuri lähettänyt Survo-ohjelmiston
käyttäjien keskusteluun (www.survo.fi -> Keskustelu -> Random Walk -
ongelma). Toivon, että asiasta kiinnostuneet tutustuvat siihen."
Tutustuin ratkaisuun alustavasti.
http://www.survo.fi/cgi/board/board.cgi?&read=000915-000000.msg&area=keskustelua_survosta
Alunperäisessä kilpailussa haettiin vastausta kymmenen numeron tarkkuudella. Jos 1000 askelta siihen riittää, niin 0.0619139544739996 tai jotain saadaan iteroimalla käyttäen tuota survo-algoritmia. Riittääköhän tuhat askelta?
Laskin f-todennäköisyydet
f(n)=P[Kirppu palaa askeleella 2*n ensimmäisen kerran origoon],
arvoilla n=1,2,...,4000 käyttäen arvoa
E=0.0619139544739914, joka antaa mm. tulokset
n___ f(n)_________________ Paluutodennäköisyys
1000 6.5373031287399e-019 0.4999999999999999
2000 6.6847481061807e-033 0.4999999999999999
4000 1.5927069384152e-060 0.4999999999999999
Huom. Paluutodennäköisyydet on laskettu f(n)-summina käänteisessä
järjestyksessä pienimmästä suurimpaan, jolloin liukulukulaskennassa
tulee vähemmän pyöristystä.
Näin on ilmeistä, että 1000 askelta riittää 10 merkitsevän numeron
tarkkuuteen ja jopa hieman enempään.
.................................................
Tässä yksinkertainen havainnollistus summeerausjärjestyksen
vaikutuksesta tarkkuuteen tehtynä Survon matriisitulkilla
(ote suoraan Survon toimituskentästä):
Summan 1 p p^2 ... p^n, kun p=0.98 ja n=4000,
arvo laskettuna kaksoistarkkuuden liukulukuaritmetiikalla on
(1-p^(n 1))/(1-p)=49.999999999999957 ACCURACY=16
Sama summeerattuna termeittäin alkuperäisessä järjestyksessä:
MAT A=ZER(n,1)
MAT TRANSFORM A BY p^(I#-1)
MAT S=SUM(A)
MAT_S(1,1)=49.999999999999815
Sama termeittäin käänteisessä järjestyksessä:
MAT P=ZER(n,1)
MAT TRANSFORM P BY n 1-I#
MAT A2=PERM(A,P)
MAT S2=SUM(A2)
MAT_S2(1,1)=49.999999999999957
....................
Summan tarkempi arvo paremmalla laskutarkkuudella:
ACCURACY=40 p=0.98 n=4000
(1-p^(n 1))/(1-p)=49.99999999999999999999999999999999960690
10/100 on siis ratkaistu :) Loput löytyy täältä
http://www.siam.org/siamnews/01-02/challenge.pdf
Rahaa ei tosin enää saa, 100/100 oikein vastauksia tuli kai useita.
"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..."
http://www.survo.fi/cgi/board/board.cgi?&read=000915-000000.msg&area=keskustelua_survosta
Onko tämä varmasti näin vai voisiko tässä
käyttää aiemmin esitettyä kenttähahmotelmaa?
Perustelut lisätty Survo-keskusteluun:
http://www.survo.fi/cgi/board/board.cgi?&read=000921-000920.msg&area=keskustelua_survosta
tödnäk ei voi olla 1/2 millään E:n arvolla. se on 0 kun E=1/4 ja muulloin 1.
E = 1/4. Tällöin itään siirtymisen tn = 1/2 ja länteen siirtymisen tn = 0. Siis, jos kirppu hyppää itään, niin paluuta alkupisteeseen ei ole. Lähtökohtatilanteessa on kaksi vaihtoehtoa;
A. Kirppu siirtyy itään todennäköisyydella 1/2, jolloin alkupisteeseen ei ole paluuta.
B. Kirppu siirtyy joko pohjoiseen tai etelään, minkä tn = 1/4 1/4 = 1/2. Tässä pohjois-eteläsuuntaisessa liikkeessä todennäköisyys päätyä alkupisteeseen on 1, jos aika on ääretön.
B vaihtoehdosta poikkeamisen tn on siis 1/2 eli itään suuntautuva liike. Niinpä alkupisteeseen palaamisen tn on 1/2, koska joko A tai B vaihtoehto toteutuu, jos kirppu yleensä liikkuu.