[vastaus aiempaan viestiin]
| Kirjoittaja: | Seppo Mustonen |
|---|---|
| Sähköposti: | - |
| Päiväys: | 14.3.2008 18:52 |
Joko antamani tehtävä oli kuvittelemaani visaisempi tai sitten
ei opiskelijoilla ollut tarpeeksi motivaatiota tai houkutusta
käydä ongelman kimppuun.
Ainoastaan Antti Liski Tampereen yliopistosta on lähettänyt
kelpo ratkaisun.
Olen vakaasti sitä mieltä, että tehtävä on mielenkiintoinen ja tarjoaa
erilaisia lähestymistapoja. On täysin mahdollista, että samaa tehtävää
on käsitelty jo jossain aikaisemmin varsinkin tapauksessa, jossa
kolikko on harhainen. Tämähän on yleistys von Neumannin
kolikko-ongelmaan, johon on lukuisia viittauksia verkossa.
Hyvä suomenkielinen lähde on Aki Loposen tutkielma
http://www.cs.uta.fi/research/theses/masters/Loponen_Aki.pdf
(sivut 15-20) jossa esitellään mm. Mitzenmacherin parannus tuohon
alkuperäiseen menetelmään.
En ole kuitenkaan nähnyt tähän mennessä sellaista yleistystä, mistä
nyt on kysymys, eli yleistystä harhattomaan arvontaan "yksi n vaihto-
ehdosta".
Esitän nyt omia tehtävään liittyviä pohdiskeluja. Yritän kuvata
ainakin joitain asioita siten, että sellainenkin lukija, joka
ei hallitse todennäköisyyslaskentaa, voi seurata juonta
pääpiirteissään.
Tapaus p=1/2:
=============
Olkoot vaihtoehdot V1,V2,...,Vn ja tarvittavien heittojen lukumäärän
odotusarvo E(n).
Tällöin on E(2)=1 (koska valinta onnistuu aina yhdellä heitolla).
Kun n on parillinen, E(n)=1+E(n/2), koska vaihtoehdot voidaan
jakaa kahteen yhtäsuureen joukkoon ja yhdellä heitolla ratkaista,
kumpi osajoukko, suuruudeltaan n/2, pääsee jatkoon.
Kun n on pariton, on kaksi erilaista menettelyä, jotka kilpailevat
keskenään:
1) Lisätään vaihtoehtoihin yksi "kelvoton" vaihtoehto, jolloin
sen tullessa valituksi aloitetaan alusta. Kelvoton tulee valituksi
todennäköisyydellä r=1/(n+1) ja odotusarvo on tällöin
E1(n)=(1-r)*E(n+1)+r*(1-r)*2*E(n+1)+r^2*(1-r)*3*E(n+1)+...
=(1-r)*E(n+1)*(1+2*r+3*r^2+4*r^3+...)
=(1-r)*E(n+1)/(1-r)^2=E(n+1)/(1-r)=(n+1)/n*E(n+1)
2) Asetetaan vaihtoehdot vastakkain pareittain lukuunottamatta viimeistä
vaihtoehtoa. Heitetään (n+1)/2 kertaa eli kerran kutakin paria kohden
ja lopuksi vielä kerran viimeistä vaihtoehtoa kohden. Kruunat jatkoon.
Tällöin jatkoon pääsee joko (n+1)/2 tai (n-1)/2 vaihtoehtoa, kummatkin
samalla todennäköisyydellä eli
E2(n)=(n+1)/2+1/2*E((n+1)/2)+1/2*E((n-1)/2)
.............
Survossa nämä odotusarvot saadaan kätevimmin seuraavalla
rekursiivisella laskentakaaviolla:
E(n):=if(n=1)then(0)else(Ep(n))
Ep(n):=if(n=2)then(1)else(E0(n))
E0(n):=if(n=2*int(n/2))then(1+E(n/2))else(min(E1(n),E2(n)))
E1(n):=(n+1)/n*(1+E((n+1)/2))
E2(n):=(n+1)/2+1/2*E((n+1)/2)+1/2*E((n-1)/2)
Yksittäiset arvot poimitaan aktivoimalla alla olevat:
E(2)=1
E(3)=2.5
E(4)=2
E(5)=4.2
E(6)=3.5
E(7)=3.4285714285714
E(8)=3
E(9)=5.7777777777778
E(10)=5.2
E(11)=4.9090909090909
E(12)=4.5
E(13)=4.7692307692308
E(14)=4.4285714285714
E(15)=4.2666666666667
E(16)=4
...
Erityisesti tapauksessa n=5
E1(5)=4.2
E2(5)=4.75
ja vastaavasti kun n=3,
E1(3)=2.6666666666667
E2(3)=2.5
Siis kun n=5, käytetään ensin menettelyä 1) eli "korotetaan" kuuteen,
joten odotusarvo on 6/5*E(6)=6/5*(1+E(3)).
Kun n=3, menettely 2) on edullisempi eli näin arvolla n=5 odotusarvo on
6/5*(1+E2(3))=4.2
Antti Liski oli omasssa ratkaisussaan päätynyt menettelyyn, joka
tapauksessa n=5 antaa hivenen suuremman odotusarvon 4.4.
Tarkennus:
==========
Menettelyn 1) kanssa kilpailee parittomilla n-arvoilla, kun n ei ole
alkuluku, seuraava:
Olkoon n=k*m, missä k on luvun n pienin tekijä > 1.
Tällöin jaetaan vaihtoehdot k osajoukkoon ja tehdään ensin valinta
"yksi k vaihtoehdosta", jolloin odotusarvoksi saadaan E(k)+E(m).
Tämä saattaa olla joskus pienempi kuin menettelyn 1) antama odotusarvo.
Ensimmäisenä tämä tapa puree arvolla n=9, koska 9=3*3 ja E(3)+E(3)=5 on
pienempi kuin aikaisempi 5.7777...
Ilmeisesti menettely 2) tulee käyttöön vain, kun n=3.
Seuraava sukro laskee tarkennetut odotusarvot:
*TUTSAVE P_PUOLI
/
/ def WN=W1 Wn=W2 WE1=W3 Wp=W4 WX=W5 Wk=W6 WE2=W7
/
*{R}
*ACCURACY=15 {R}
/
/ Odotusarvot talletetaan vektorina E, jonka aikaisempia
/ alkioita käytetään menettelyn 1) mukaisissa kaavoissa.
*MAT E=ZER({print WN},1) {act}{R}
*E(n):=if(n=2*int(n/2))then(1+MAT_E(n/2))else(E1(n))) {R}
*E1(n):=(n+1)/n*(1+MAT_E((n+1)/2)) {R}
/
*{d}
*{ref}
*{d4}
*MAT E(1,1)=0{R}
*MAT E(2,1)=1{R}
*MAT E(3,1)=2.5{R}
*MAT E(4,1)=2{R}
*MAT E(5,1)=4.2{R}
*MAT E(6,1)=3.5{R}
*MAT E(7,1)=3.428571428571428{R}
*MAT E(8,1)=3{R}
*{u8}{pre}{act}
/ 8 ensimmäistä odotusarvoa annettu valmiina.
/ Wp=0, jos Wn=n on parillinen, muuten Wp=1.
*{Wn=8}{Wp=0}{R}
/
+ A: {ref}{erase}{Wn=Wn+1}{Wp=1-Wp}
/
/ Lasketaan arvoon WN asti, joka annetaan komennon parametrina.
- if Wn > WN then goto E
/
/ WE1 on menettelyn 1) mukainen odotusarvo.
*E({print Wn})={act}{l} {save word WE1}{R}
/ Jos n on parillinen, tarkennusta ei tarvita.
- if Wp = 0 then goto B
/ Pinimmän tekijän etsiminen parittomille n:
*{erase}{print Wn}(10:factors)={act}{l} {}
+ C: {r}{save char Wk}
/ Jos n aon alkuluku, ei voida tarkentaa:
- if Wk '=' {sp} then goto B
/ esim. 9(10:factors)=3^2
/ 105(10:factors)=3*5*7
- if Wk '=' ^ then goto D
- if Wk '<>' * then goto C
/ Pienin tekijä on Wk:
+ D: {l2}{save word Wk}{R}
/ Lasketaan WE2=E(k)+E(m).
*MAT_E({print Wk})+MAT_E({Wk=Wn/Wk}{print Wk})={act}
*{l} {save word WE2}
/ Pienempi luvuista WE1 ja WE2 on E(n)
- if WE2 > WE1 then goto B
*{WE1=WE2}
/ Talletus matriisitiedostoon E.MAT
+ B: {line start}{erase}MAT E({print Wn},1)={print WE1}{act}
*{goto A}
+ E:
*{end}
Komennolla
/P_PUOLI 10000
olen laskenut odotuarvot, kun n=1,2,...,10000.
Odotusarvot, kun n=1,2,...,100:
n E n E n E n E n E
1 0.00000 21 5.92857 41 7.09756 61 6.26230 81 8.12963
2 1.00000 22 5.90909 42 6.92857 62 6.16129 82 8.09756
3 2.50000 23 5.73913 43 7.06977 63 6.09524 83 8.02410
4 2.00000 24 5.50000 44 6.90909 64 6.00000 84 7.92857
5 4.20000 25 6.00000 45 6.76667 65 8.53846 85 8.16471
6 3.50000 26 5.76923 46 6.73913 66 8.40909 86 8.06977
7 3.42857 27 5.62963 47 6.63830 67 8.47761 87 7.94828
8 3.00000 28 5.42857 48 6.50000 68 8.35294 88 7.90909
9 5.00000 29 5.44828 49 6.85714 69 8.23913 89 7.85393
10 5.20000 30 5.26667 50 7.00000 70 8.20000 90 7.76667
11 4.90909 31 5.16129 51 6.90196 71 8.11268 91 7.82418
12 4.50000 32 5.00000 52 6.76923 72 8.00000 92 7.73913
13 4.76923 33 7.40909 53 6.75472 73 8.84932 93 7.66129
14 4.42857 34 7.35294 54 6.62963 74 8.72973 94 7.63830
15 4.26667 35 7.20000 55 6.54545 75 8.50000 95 7.57895
16 4.00000 36 7.00000 56 6.42857 76 8.52632 96 7.50000
17 6.35294 37 7.72973 57 6.56140 77 8.33766 97 7.93814
18 6.00000 38 7.52632 58 6.44828 78 8.26923 98 7.85714
19 6.52632 39 7.26923 59 6.37288 79 8.30380 99 8.08081
20 6.20000 40 7.20000 60 6.26667 80 8.20000 100 8.00000
Seuraavat kaksi kuvaa havainnollistavat odotusarvon käyttäytymistä:
http://www.survo.fi/papers/p_puoli.pdf
Odotusarvo ei siis kasva tasaisesti ja on paikallisesti pienimmillään
kun n on kakkosen potenssi tai jokin sellaisen kerrannainen.
Kasvu on likimain logaritmista.
Tapaus p tuntematon (q=1-p):
============================
Mielestäni hyvä päättelysääntö, kun n>2, on seuraava:
Heitetään kolikkoa kerran kutakin n vaihtoehtoa kohti. Olkoon
kruunien määrä k ja klaavojen n-k. Jos 0<k<=n-k, kruunat jatkavat,
jos 0<n-k<k, klaavat jatkavat. Jos k=0 tai k=n, aloitetaan alusta.
Tapauksessa n=2 (von Neumann) heittoja tarkastellaan pareittain, jolloin
esiintyvät tilanteet (A=Kruuna, B=Klaava ja p kruunan todennäköisyys)
tilanne todennäköisyys
AA p^2
AB p*q
BA q*p
BB q^2
Sovitaan,että AB johtaa vaihtoehdon 1 valintaan ja BA vaihtoehdon 2
valintaan. Tilanteissa AA ja BB aloitetaan alusta ja heitetään kaksi
kertaa. Tätä toistetaan, kunnes saadaan joko AB tai BA. Näin taataan
kummallekin vaihtoehdolle sama todennäköisyys tulla valituksi.
Arvonta päättyy kahdella heitolla todennäköisyydellä 2*p*q
ja jatkuu lisäheitoilla todennäköisyydellä p^2+q^2.
Heittojen lukumäärän odotusarvo E2 on helpointa laskea
ehdollistamispriaatteella yhtälöstä
E2=2*p*q*2+(p^2+q^2)*(E2+2)
eli odotusarvo ehdolla "saatiin AB tai BA" on 2 todennäköisyydellä
2*p*q ja se on E2+2 (2 "hukkaheittoa") todennäköisyydellä p^2+q^2.
Painottamalla nämä ehdolliset odotusarvot omilla todennäköisyyksillään
saadaan summana kysytty odotusarvo E2.
Kehittämällä yhtälön oikeata puolta seuraavasti
E2=(p^2+q^2)*E2+2*[p^2+q^2+2*p*q]=(p^2+q^2)*E2+2=(1-2*p*q)*E2+2
tulee ratkaisuksi E2=1/(p*q).
E2 on pienimmillään eli 4, kun p=q=1/2.
Siitä, ettei lanttia voi olettaa reiluksi, saa maksaa keskimäärin
vähintään nelinkertaisella heittomäärällä.
Odotusarvoa voidaan kyllä pienentää tulkitsemalla esim. heittosarja
AABB vaihtoehdon 1 valinnaksi ja heittosarja BBAA vaihtoehdon 2
valinnaksi, mutta sillä lienee vain pieni vaikutus tulokseen.
Olkoon yleisesti En lopulliseen valintaan tarvittavien heittojen
lukumäärän odotusarvo.
E5 voidaan tällöin esittää ehdollisten odotusarvojen painotettuna
summana seuraavasti:
E5=(p^5+q^5)*(E5+5)
+5*(p^4*q+p*q^4)*5
+10*(p^3*q^2+p^2*q^3)*(E2+5)
=(p^5+q^5)*E5+5*[p^5+q^5+5*(p^4*q+p*q^4)+10*(p^3*q^2+p^2*q^3)
+10*(p^3*q^2+p^2*q^3)*E2
=(p^5+q^5)*E5+5*(p+q)^5+10*(p^2*q^2)*(p+q)*E2
=(p^5+q^5)*E5+5+10*(p*q)^2*(1/(p*q))
=(p^5+q^5)*E5+5+10*p*q
eli tästä tulee ratkaisuksi
E5=5*(1+2*p*q)/(1-p^5-q^5),
joka on pienimmillään eli 8, kun p=q=1/2.
Tällä tavalla arvoilla n=2,3,4,5,6,7 saadaan
E2=1/(p*q)
E3=1/(p*q) eli ehkä yllättäen sama kuin E2,
E4=2*(2+3*p*q)/(1-p^4-q^4)
E5=5*(1+2*p*q)/(1-p^5-q^5)
E6=(15*p*q-10*(p*q)^2+6)/(1-p^6-q^6)
E7=7*(1+3*p*q-4*(p*q)^2)/(1-p^7-q^7)
Lausekkeista tulee ilmeisesti yhä mutkikkaampia, kun n kasvaa.
Tyydyn sen vuoksi numeeriseen tarkasteluun.
Seuraavan rekursiivisen laskentakaavion avulla on mahdollista laskea
näitä odotusarvoja kiinteillä p-arvoilla hyvinkin suurille
vaihtoehtomäärille N:
..............................
E(N)|=if(N=1)then(0)else(if(N=2)then(1/(p*q))else(EE(N)))
EE(N):=if(N=3)then(3/(1-p^3-q^3))else(E0(N))
E0(N):=if(N=2*int(N/2))then(E2(N))else(E1(N))
S2(N):=for(I=2)to(N/2-1)sum(C(N,I)*((p^(N-I)*q^I+p^I*q^(N-I))*E(I)))
E2(N):=(S2(N)+N+C(N,N/2)*(p*q)^(N/2)*E(N/2))/(1-p^N-q^N)
S1(N):=for(I=2)to(int(N/2))sum(C(N,I)*((p^(N-I)*q^I+p^I*q^(N-I))*E(I)))
E1(N):=(S1(N)+N)/(1-p^N-q^N)
ACCURACY=16
p=1/2 q=1-p
E(8)=12.432731517273787
Jos siis kolikko on harhaton, saadaan
E(2)=4
E(3)=4
E(4)=6.2857142857142856 (44/7)
E(5)=8
E(6)=9.4193548387096779 (292/31)
E(7)=10.666666666666666 (32/3)
E(8)=12.440944881889763 (1580/127)
E(9)=14.023529411764706 (1192/85)
E(10)=15.86692759295499 (8108/511)
Suurilla n-arvoilla on kiinnostavaa katsoa, mitä on E(n)/n:
E(100)/100=1.7941574539486447
E(200)/200=1.8442384669667553
E(220)/220=1.8503872429281234
E(300)/300=1.8690212015345935
E(400)/400=1.8840668711812836
E(500)/500=1.8949673586637965
E(600)/600=1.9031751471085019
E(700)/700=1.9095473792081088
E(800)/800=1.9147594931461018
E(900)/900=1.9191792191281052
E(1000)/1000=1.9229882036650083
E(n) kasvaa siis likimain lineaarisesti ja karkeasti arvontaan
"yksi n vaihtoehdosta" tarvitaan keskimäärin lähes kaksinkertainen
heittomäärä vaihtoehtojen lukumäärään verrattuna (kun kolikko
sattuu olemaan harhaton tai lähes sellainen).
Katsotaan seuraavaksi, miltä näyttävät heittolukumäärien
pistetodennäköisyydet
P(n,k)=P{tarvitaan k heittoa}, k=n,n+1,...
Ne käyttäytyvät siinä määrin epäsäännöllisesti, että yleisten
lausekkeiden esittäminen on hankalaa. Numeerisesti, annetulla
p-arvolla pistetodennäköisyyksiä voi laskea esittämällä prosessin
Markovin ketjuna.
Tapauksessa n=5 seuraava siirtymätodennäköisyyksien matriisi
kertoo kaiken olennaisen.
p=1/2 q=1-p
MAT SAVE P
MATRIX P
/// T0 10 01 20 11 02 30 21 12 03 40 31 22 13 04 T2 P Q T1 E
T0 0 p q 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
10 0 0 0 p q 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
01 0 0 0 0 p q 0 0 0 0 0 0 0 0 0 0 0 0 0 0
20 0 0 0 0 0 0 p q 0 0 0 0 0 0 0 0 0 0 0 0
11 0 0 0 0 0 0 0 p q 0 0 0 0 0 0 0 0 0 0 0
02 0 0 0 0 0 0 0 0 p q 0 0 0 0 0 0 0 0 0 0
30 0 0 0 0 0 0 0 0 0 0 p q 0 0 0 0 0 0 0 0
21 0 0 0 0 0 0 0 0 0 0 0 p q 0 0 0 0 0 0 0
12 0 0 0 0 0 0 0 0 0 0 0 0 p q 0 0 0 0 0 0
03 0 0 0 0 0 0 0 0 0 0 0 0 0 p q 0 0 0 0 0
40 p 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 q 0
31 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 q 0 0 p 0
22 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 p 0 0 q 0
04 q 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 p 0
T2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 p q 0 0
P 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 p 0 0 q 0
Q 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 q 0 0 p 0
T1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
E 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
Tämä 20-tilainen ketju esittää heittoprosessin kulkua heitto heitolta.
Matriisin ensimmäinen rivi kertoo, että alkutilasta T0 päästään (yhdellä
heitolla) joko tilaan 10 (eli 1 kruuna, 0 klaavaa) todennäköisyydellä p
tai tilaan 01 (0 kruunaa, 1 klaava) todennäköisyydellä q.
Yleisesti tila ij tarkoittaa tilannetta, jossa on saatu i kruunaa ja
j klaavaa. Näin rivit 10,20,11,02,30,21,12,03 noudattavat samanlaista
rakennetta kuin ensimmäinen.
Vasta rivillä 40 tapahtuu mielenkiintoisempaa.
Tilasta 40 (4 kruunaa, 0 klaavaa) joudutaan takaisin alkutilaan T0
todennäköisyydellä p (koska on saatu viisi peräkkäistä kruunaa), mutta
todennäköisyydellä q peli ratkeaa, koska 5 heitossa on saatu vain 1
klaava ja tullaan suoraan "maalitilaan" T1.
Vastaavalla tavalla toimivat rivit 31,13 ja 04.
Tilasta 22 joudutaan väistämättä (todennäköisyydellä 1) tilaan T2,
jossa mukana on enää kaksi vaihtoehtoa.
Tilasta T2 tullaan joko tilaan P tai Q todennäköisyyksin p ja q.
Tilasta P joudutaan joko kahden vaihtoehdon alkutilaan T2 (saatu
kaksi peräkkäistä kruunaa) tai päästään maaliin T1. Tilasta Q
joudutaan vastaaviin tilanteisiin päivastaisin todennäköisyyksin.
Ketjuun on lisätty vielä ylimääräinen lopputila E, johon joudutaan
aina välittömästi tilasta T1. Sen merkitys ilmenee kohta.
Jos siirtymätodennäköisyyksien matriisi P kerrotaan itsellään eli
lasketaan matriisi P^2, saadaan (kokonaistodennäköisyyden kaavan
mukaisesti) uuden matriisin alkioina luvut, jotka kertovat, millä
todennäköisyydellä siirrytään tilasta x tilaan y kahdella askeleella
ja yleisesti P^k (matriisi P potenssiin k) kertoo k askeleen siirtymä-
todennäköisyydet tilojen välillä.
Kun otetaan mukaan prosessin alkutilaa kuvaava vektori P0 (esitettynä
tässä transponoituna)
T0 10 01 20 11 02 30 21 12 03 40 31 22 13 04 T2 P Q T1 E
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
joka kertoo, että ollaan aluksi tilassa T0, saadaan tieto siitä,
millä todennäköisyydellä peli päättyy (eli yksi vaihtoehto viidestä
tulee valituksi) täsmälleen k heitolla, tulosta
(P^k)'*P0.
Tämä vektori kertoo kokonaisuudessaan, millä todennäköisyydellä
prosessi on kussakin tilassa k heiton jälkeen.
Kun esim. p=q=1/2 ja k=12, saadaan Survon matriisitulkilla
MAT R=(P^12)'*P0
MAT LOAD R
MATRIX R
P^12'*P0
/// 0
T0 0.000000
10 0.000000
01 0.000000
20 0.000977
11 0.001953
02 0.000977
30 0.000000
21 0.000000
12 0.000000
03 0.000000
40 0.000000
31 0.000000
22 0.000000
13 0.000000
04 0.000000
T2 0.019531
P 0.039063
Q 0.039063
T1 0.019531
E 0.878906
Nähdään, että todennäköisyysmassa, kooltaan 1, joka sijaitsi alunperin
huipulla T0 on valunut melkoisesti kohti lopputilaa E. Merkkinä siitä,
että on jouduttu aloittamaan kahdesti alusta (10 heiton jälkeen)
ollaan pienin todennäköisyyksin tiloissa 20,11,02.
Maaliin E on 11 heiton aikana päästy todennäköisyydellä 0.878906
ja juuri nyt 12. heitolla (tila T1) todennäköisyydellä 0.019531.
Näin selittyy, miksi määriteltiin tuo ylimääräinen lopputila E.
Tällöin T1 "väliaikaisena" tilana kertoo aina täsmälleen, millä
todennäköisyydellä arvonta ratkeaa juuri määrätyllä heittomäärällä
eli R(T1) eri arvoilla k antaa heittomäärän jakauman
pistetodennäköisyydet P(n,k).
Seuraava sukro laskee pistetodennäköisyydet edellä kuvatulla tavalla.
Vaikka matriisipotenssit P^2,P^3,...,P^k olisi nopeinta laskea
askeltaen tyyliin P^k=P*P^(k-1), se voi johtaa liiallisiin pyöristys-
virheisiin. Tämän vuoksi käytetään tässä suoraa potenssiinkorotusta
MAT Q=P^k
jolloin esim. arvolla k=18, 18(10:bin)=10010, Survon matriisitulkki
laskee potenssit P2=P^2, P4=P2^2, P8=P4^2, P16=P8^2 ja saa 18.
potenssin tulona P2*P16.
Tarkkuuden säilyttämisen kannalta pistetodennäköisyydet talletetaan
vektoriksi PP käänteisessä järjestyksessä, jolloin jakauman odotusarvoa
ja muita momentteja laskettaessa - niiden ollessa tulosummia -
lähdetään liikkeelle pienimmästä päästä.
*TUTSAVE MARV5
/ def Wn=W1 Wi=W2
*{R}
*MAT PP=ZER({print Wn},1){act}{R}
*{Wi=0}
+ A: {ref}{Wi=Wi+1}
- if Wi > Wn then goto E
*{erase}MAT Q=P^{print Wi}{act}{R}
*{erase}MAT R=Q'*P0{act}{R}
*{erase}MAT PP({print Wn}-{print Wi}+1,1)=R(T1,1){act}{goto A}
+ E: {R}
*{d2}MAT RLABELS "" TO PP{act}{end}
*{end}
Esimerkkinä on tapaus n=5, p=q=1/2:
.......................................
Katsotaan, että 200 ensimmäistä pistetodennäköisyyttä riittää
odotusarvon ja varianssin riittävän tarkkaan laskentaan.
Kun sukro /MARV5 on aktivoitu parametrilla 200, lopputilanne on
seuraava:
/MARV5 200
MAT PP=ZER(200,1)
MAT Q=P^200 / *Q~P^200 20*20
MAT R=Q'*P0 / *R~P^200'*P0 20*1
MAT PP(200-200+1,1)=R(T1,1)
MAT RLABELS "" TO PP
Odotusarvo saadaan PP-matriisin avulla seuraavasti:
MAT C=ZER(200,1)
MAT TRANSFORM C BY 200-I#+1 / arvot käänteisessä järjestyksessä
MAT TRANSFORM C BY PP AND X#*Y# / arvo*pistetodennäköisyys
MAT S=SUM(C) / summa=odotusarvo
MAT_S(1,1)=8
Tulos 8 on luonnollisesti sama kuin mitä pääteltiin aikaisemmin.
.......................................
Heittojen lukumäärän varianssi lasketaan samaan tapaan:
MAT C=ZER(200,1)
MAT TRANSFORM C BY 200-I#+1
MAT TRANSFORM C BY (X#-8)*(X#-8)
MAT TRANSFORM C BY PP AND X#*Y#
MAT S=SUM(C) / *S~SUM(T(C_by_PP_and_X#*Y#)) D1*1
MAT_S(1,1)=10.666666666666666
Varianssin tarkka arvo on mitä ilmeisimmin 32/3.
Varianssit eräillä muillakin p:n arvoilla samaan tapaan laskettuina
ovat seuraavia:
p Varianssi
1/2 32/3 =10.666666666667
1/3 3123/196 =15.933673469388
1/4 38848/1521=25.541091387245
1/5 88175/2352=37.489370748299
eli varianssikin kasvaa reippaasti, kun etäännytään "parhaasta"
arvosta p=1/2.
Palaan vielä uudelleen aiheeseen, jos tulee lisää sanottavaa.
On täysin mahdollista, että tehtävälle löytyy vielä parempia
ratkaisutapoja.
Seppo Mustonen
| 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!