[vastaus aiempaan viestiin]
| Kirjoittaja: | Seppo Mustonen |
|---|---|
| Sähköposti: | - |
| Päiväys: | 2.4.2008 14:06 |
Kuvatessani eilen (1.4.2008) tilastollisen tietojenkäsittelyn
seminaarissa tämän tehtävän ratkaisutapoja, huomasin, että tapauksessa
p=1/2 olin jäänyt puolitiehen tilanteissa, joissa arvotaan yksi
n vaihtoehdosta, kun n on pariton.
Tässä on parannettu kuvaus:
Olkoot vaihtoehdot V(1),V(2),...,V(n) 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)
Huomattakoon, että summan S=1+2*r+3*r^2+4*r^3+... arvo 1/(1-r)^2
(kun 0<=r<1) on helpoiten todettavissa näin:
S=1+2*r+3*r^2+4*r^3+...=(1+r+r^2+r^3+...) + r*(1+2*r+3*r^2+4*r^3+...)
=1/(1-r)+r*S
eli (1-r)*S=1/(1-r) eli s=1/(1-r)^2.
2) Ei aseteta vaihtoehtoja vastakkain pareittain, kuten aiemmassa
ratkaisussani tein, vaan valitaan ensimmäisellä heitolla puolet
vaihtoehdoista V_1,V_2,...,V_n-1 ja ratkaistaan toisella heitolla,
pääseekö viimeinen vaihtoehto V_n mukaan "toiselle kierrokselle".
Jatkoon pääsee siis joko (n-1)/2 tai (n-1)/2+1=(n+1)/2 vaihtoehtoa
samoin todennäköisyyksin ja näin tällä menettelyllä odotusarvoksi tulee
E2(n)=2+1/2*E((n-1)/2)+1/2*E((n+1)/2)
mikä on olennaisesti pienempi kuin aiemmassa ratkaisussa esitetty
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):=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 E1(3)=2.6666666666667 E2(3)=2.5
E(4)=2
E(5)=3.75 E1(5)=4.2 E2(5)=3.75
E(6)=3.5
E(7)=3.4285714285714 E1(7)=3.4285714285714 E2(7)=4.25
E(8)=3
E(9)=4.875 E1(9)=5.2777777777778 E2(9)=4.875
E(10)=4.75
E(11)=4.9090909090909 E1(11)=4.9090909090909 E2(11)=5.625
E(12)=4.5
E(13)=4.7692307692308 E1(13)=4.7692307692308 E2(13)=5.4642857142857
E(14)=4.4285714285714
E(15)=4.2666666666667 E1(15)=4.2666666666667 E2(15)=5.2142857142857
E(16)=4
...
Erityisesti tapauksessa n=5
E1(5)=4.2
E2(5)=3.75
ja vastaavasti kun n=3,
E1(3)=2.6666666666667
E2(3)=2.5
Siis kun n=5, käytetään menettelyä 2) eli E(5)=2+1/2*E(2)+1/2*E(3)
eli E(5)=3.75, mikä on siis pienempi kuin aikaisemmin saamani 4.2.
Menettelyjen 1) ja 2) paremmuus vaihtelee. Esim. arvoilla n=7,11,13,15
1) on parempi ja arvoilla n=3,5,9 taas 2) johtaa pienempään
odotusarvoon.
Tarkennus:
==========
Menettelyjen 1) ja 2) 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 menettelyjen 1) ja 2) yhdistelmän
antama odotusarvo.
Ensimmäisenä tämä tapa puree arvolla n=21, koska 21=3*7 ja
E(3)+E(7)=5.9285714285714 on pienempi kuin E1(21)=6.1904761904762
ja E2(21)=6.8295454545455
Seuraava sukro laskee tällä tapaa parannetut 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(min(E1(n),E2(n))) {R}
*E1(n):=(n+1)/n*(1+MAT_E((n+1)/2)) {R}
*E2(n):=2+1/2*MAT_E((n-1)/2)+1/2*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}
*{u3}{pre}{act}
/ 3 ensimmäistä odotusarvoa annettu valmiina.
/ Wp=0, jos Wn=n on parillinen, muuten Wp=1.
*{Wn=3}{Wp=1}{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. 21(10:factors)=3*7
/ 125(10:factors)=5^3
- 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 3.75000 25 6.00000 45 6.76667 65 7.98438 85 8.16471
6 3.50000 26 5.76923 46 6.73913 66 7.96875 86 8.06977
7 3.42857 27 5.62963 47 6.63830 67 8.05597 87 7.94828
8 3.00000 28 5.42857 48 6.50000 68 7.93750 88 7.90909
9 4.87500 29 5.44828 49 6.85714 69 8.18841 89 7.85393
10 4.75000 30 5.26667 50 7.00000 70 8.07143 90 7.76667
11 4.90909 31 5.16129 51 6.90196 71 7.98592 91 7.82418
12 4.50000 32 5.00000 52 6.76923 72 7.87500 92 7.73913
13 4.76923 33 6.96875 53 6.75472 73 8.35616 93 7.66129
14 4.42857 34 6.93750 54 6.62963 74 8.24324 94 7.63830
15 4.26667 35 7.07143 55 6.54545 75 8.16000 95 7.57895
16 4.00000 36 6.87500 56 6.42857 76 8.05263 96 7.50000
17 5.93750 37 7.24324 57 6.56140 77 8.02597 97 7.93814
18 5.87500 38 7.05263 58 6.44828 78 7.92308 98 7.85714
19 6.05263 39 6.92308 59 6.37288 79 7.84810 99 8.08081
20 5.75000 40 6.75000 60 6.26667 80 7.75000 100 8.00000
Nämä tulokset eroavat aikaisemmista vain siten, että väleillä
(2^n+1,2^n+2^(n-2)), n=1,2,3,... siis esim. (5,5), (9,10), (17,20),
(33,40), (65,80), ..., (2049,2560), ... odotusarvot ovat pienemmät.
Seuraavat kaksi kuvaa havainnollistavat odotusarvon käyttäytymistä:
http://www.survo.fi/papers/p_puoli2.pdf
Odotusarvo ei siis kasva tasaisesti ja on paikallisesti pienimmillään,
kun n on kakkosen potenssi tai jokin sellaisen kerrannainen.
Kasvu on likimain logaritmista.
En edelleenkään ole varma siitä, että nyt esitetty menettely johtaisi
kauttaaltaan pienimpiin odotusarvoihin. On siis mielenkiintoista nähdä,
löytyykö vielä parannettavaa.
| 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!