Lampputehtävä, kaikki päälle

Hätiköity vastaus mututuntumalta. Täytyy miettiä.

arvelin.väärin kirjoitti:

Hätiköity vastaus mututuntumalta. Täytyy miettiä.

Joo, se menisi noin, jos joka tilasta pääsisi toiseen. Mutta vain yhtä bittiä voi vaihtaa kerrallaan. Vinkki: kuution kärjet, tai toinen tapa ajatella: ottaa huomioon vain kuinka monta lamppua eli bittiä on päällä (nämä tilat ovat keskenään samassa asemassa ja ovatkin juuri ne "kategoriat", jotka alkuperäisessä vinkissä mainitsin).

Ei, odotusarvon ei tarvitse olla satunnaismuuttujan mahdollinen arvo.

Kyseessähän on satunnaiskävely kuution kärjillä sivuja pitkin ja kysytään odotusarvoa kuinka monta askelta täytyy ottaa, jotta päästään vastakkaiseen nurkkaan.

Kanootti3 kirjoitti:

Ei, odotusarvon ei tarvitse olla satunnaismuuttujan mahdollinen arvo.

Kyseessähän on satunnaiskävely kuution kärjillä sivuja pitkin ja kysytään odotusarvoa kuinka monta askelta täytyy ottaa, jotta päästään vastakkaiseen nurkkaan.

Lue lisää

Taisin sanoa vähän epäselvästi. Siis, ei 10:llä ei pääse vaan täytyy olla juurikin pariton määrä askelia, mutta 10 oli siis odotusarvo, jota kysyttiin.

Kanootti3 kirjoitti:

Ei, odotusarvon ei tarvitse olla satunnaismuuttujan mahdollinen arvo.

Kyseessähän on satunnaiskävely kuution kärjillä sivuja pitkin ja kysytään odotusarvoa kuinka monta askelta täytyy ottaa, jotta päästään vastakkaiseen nurkkaan.

Lue lisää

Okei, mulle on jäänyt epäselväksi mitä odotusarvo tarkoittaa, siitä hämmennykseni. (Aihetta koskevasta Wikipedia-artikkelista minä en ymmärrä mitään.)

fdgsdfghsdfhdf kirjoitti:

Okei, mulle on jäänyt epäselväksi mitä odotusarvo tarkoittaa, siitä hämmennykseni. (Aihetta koskevasta Wikipedia-artikkelista minä en ymmärrä mitään.)

Jos selventää, niin ajattele noppaa. Sen mahdolliset arvothan ovat 1, 2, 3, 4, 5 ja 6, jokaisen tn. 1/6. Odotusarvo on jokainen arvo kerrottuna todennäköisyydellään ja summataan yhteen, eli tässä tapauksessa:

1*1/6 2*1/6 3*1/6 4*1/6 5*1/6 6*1/6 = 3,5.

Jos mahdollisia arvoja on äärettömästi, niin tulee ääretön summa ja jos niitä on jopa "jatkuvasti", (yhden arvon todennäköisyys menee nollaan, mutta arvoja on tiheämmässä ja tiheämmässä), niin joudutaan menemään differentiaalisiin summiin eli integraaliin.

Tässä lampputehtävässähän satunnaismuuttuja, jota tarkastellaan on

X="askelten määrä ennen kuin saavutaan 111:een, kun lähdetään 000:sta (ja liikutaan mainitulla tavalla)".

Todennäköisyydet voidaan laskea siitä kuinka monta reittiä on kulkea 000:sta 111:een, siten että k:nnella askeleella saavutaan ja ei käydä ennen sitä, jaettuna kaikkien mahdollisten määrällä. Nämä saadaan itseasiassa Markovin ketjusta, kun jätetään absorboiva tila 111 pois ja otetaan jäljelle jääneen tilasiirtymämatriisin Q k:s potenssi (tässä on itseasiassa kaikki todennäköisyydet Q:n tiloista Q:n tiloihin). Odotusarvot ennen absorboitumista saadaan summaamalla kaikki potenssit 0,1,2,... (summaa indikaattoreita, että ketju on tilassa j kun on otettu k askelta) ja sehän on

I Q Q^2... = (I-Q)^{-1}

(geometrinen sarja pätee matriiseillekin, kunhan suppenee ja tapauksessa, kun Q:n tilat on transientteja näin käy).

"Voi perhele" tarkoitin, jos ensimmäisellä kerralla ei onnistu niin toisella kerralla onnistuu. Muistakaa käyttää myös maalaisjärkeä. Eihän sitä nyt muuten avaruuslennot Marsiin onnistu.

Tätä voitaisiin testata laskemalla siirtymämatriisin potensseja ja katsoa milloin siellä kysytty alkio on yli puoli.

Tehdään nyt vähän pienempi matriisi ja otetaan tilassa huomioon vain se kuinka monta lamppua on päällä. Siirtymätodennäköisyydet on helppo laskea: jos valitaan lamppu, joka on päällä, pienenee yhdellä, muuten kasvaa. Tila "3 päällä" absorboivaksi.

Wolfram Alpha antaa:

http://www.wolframalpha.com/input/?i=[[0, 1, 0, 0], [1/3, 0, 2/3, 0], [0, 2/3, 0, 1/3], [0,0,0,1]]^7

että seitsemän siirtymän jälkeen todennäköisyys olla tilassa 3 on 1158/2187 = 0.52949...

Tässä myös fundamentaali matriisi, joka antaa ne odotusarvot tiloissa 0, 1 ja 2 vierailuille ennen absorboitumista):

http://www.wolframalpha.com/input/?i=inverse of [[1, -1, 0], [-1/3, 1, -2/3], [0, -2/3, 1]]

Eka rivi summautuu 10:een eli yhteensä on odotettavissa sen verran vierailuja ennen absorboitumista.

Tuon 7 sain minäkin toisella tekniikalla.

Yleistys n:lle lampulle onkin mielenkiintoinen. Onkohan sille löytynyt yleistä kaavaa. Helpohko laskea tuolla matriisimenetelmällä, kun tiloiksi ottaa lamppujen määrät. Mä oon tainnut tätä ennenkin pohtia tuommoista ketjua, jossa siirrytään eteen tai taakse päin ja todennäköisyys riippuu lineaarisesti siitä, kuinka lähellä loppua ollaan.

Tarkat arvot ovat

4: 64/3
5: 128/3
6: 416/5
7: 2416/15
8: 32768/105
16: 70766.36795776001

Pythonilla laskin minäkin: muodostin sen fundamentaalimatriisin ja summasin ekan rivin. Käytin rationaalilukuja ja jo ysille ohjelmani hyytyi :D. Ihme, eihän se ole kuin 9x9-matriisin käänteismatriisin lasku, mutta varmaan johtu niistä rationaaliluvuista (fractions.Fraction) ja inverse-algoritmista, jonka netistä löysin. No, numpy.linalg.inv laski 16:stankin hetkessä, mutta se ei taida osata laskea rationaaliluvuilla(?)

Kanootti3 kirjoitti:

Yleistys n:lle lampulle onkin mielenkiintoinen. Onkohan sille löytynyt yleistä kaavaa. Helpohko laskea tuolla matriisimenetelmällä, kun tiloiksi ottaa lamppujen määrät. Mä oon tainnut tätä ennenkin pohtia tuommoista ketjua, jossa siirrytään eteen tai taakse päin ja todennäköisyys riippuu lineaarisesti siitä, kuinka lähellä loppua ollaan.

Tarkat arvot ovat

4: 64/3
5: 128/3
6: 416/5
7: 2416/15
8: 32768/105
16: 70766.36795776001

Pythonilla laskin minäkin: muodostin sen fundamentaalimatriisin ja summasin ekan rivin. Käytin rationaalilukuja ja jo ysille ohjelmani hyytyi :D. Ihme, eihän se ole kuin 9x9-matriisin käänteismatriisin lasku, mutta varmaan johtu niistä rationaaliluvuista (fractions.Fraction) ja inverse-algoritmista, jonka netistä löysin. No, numpy.linalg.inv laski 16:stankin hetkessä, mutta se ei taida osata laskea rationaaliluvuilla(?)

Lue lisää

Jos lamppujen määrä n on iso, niin lähestytäänkö arvoa 2^n? En ole kokeillut kuin 32:lla. Alkaa olla todella äärimmäisen hidasta satunnaisella kytkimien heiluttelulla.

PytnonillaHidasta kirjoitti:

Jos lamppujen määrä n on iso, niin lähestytäänkö arvoa 2^n? En ole kokeillut kuin 32:lla. Alkaa olla todella äärimmäisen hidasta satunnaisella kytkimien heiluttelulla.

Siltä tosiaan näyttäisi että arvo on suhteellisen lähellä 2^n:ää. Tässä minun Python-koodini, joka kyllä laskee isoillekin n (kun käyttää numpy:ta ja laskee floateilla):

http://tpcg.io/ZyGBsX

Mutta siinä tulee ongelma isoilla n, nimittäin ilmeisesti matriisin kääntäminen ei toimi, vaan tulos on täyttä tuubaa (sinne tulee negatiivisia arvojakin!). Luultavasti kyse on samasta mikä mainittu täällä: https://stackoverflow.com/questions/31188979/is-numpy-linalg-inv-giving-the-correct-matrix-inverse-edit-why-does-inv-gi

Voisi vielä yrittää pohtia, jos tuolle fund.matriisille näkisi jotain yleistä kaavaa ja tämän avulla myös kysytylle odotusarvolle.

Kanootti3 kirjoitti:

Siltä tosiaan näyttäisi että arvo on suhteellisen lähellä 2^n:ää. Tässä minun Python-koodini, joka kyllä laskee isoillekin n (kun käyttää numpy:ta ja laskee floateilla):

http://tpcg.io/ZyGBsX

Mutta siinä tulee ongelma isoilla n, nimittäin ilmeisesti matriisin kääntäminen ei toimi, vaan tulos on täyttä tuubaa (sinne tulee negatiivisia arvojakin!). Luultavasti kyse on samasta mikä mainittu täällä: https://stackoverflow.com/questions/31188979/is-numpy-linalg-inv-giving-the-correct-matrix-inverse-edit-why-does-inv-gi

Voisi vielä yrittää pohtia, jos tuolle fund.matriisille näkisi jotain yleistä kaavaa ja tämän avulla myös kysytylle odotusarvolle.

Lue lisää

Paitsi tuolla koodissa vika rivi piti olla

print [lampExps[i]/2**(i 1) for i in xrange(len(lampExps))]

sillä indeksissä 0 on odotusarvo n=1:lle, jne.

Sagella onnistuu rationaalimatriisinkin laskeminen: http://sagecell.sagemath.org/

Saadaan vielä tarkkoja arvoja lisää:

9: 21248/35
10: 74752/63
11: 733696/315
12: 5300224/1155
13: 31418368/3465
14: 115552256/6435
15: 106977280/3003
16: 637534208/9009
17: 1267793920/9009
18: 4766040064/17017
19: 85425520640/153153
20: 3234139734016/2909907
21: 1535025086464/692835
22: 5843921666048/1322685
23: 128230272008192/14549535
24: 1961561493078016/111546435
25: 2348839113588736/66927861
26: 9016382767235072/128707425
27: 26000831711019008/185910725
28: 200248742308216832/717084225
29: 2799239198232543232/5019589575
30:10808563553590575104/9704539845

Kanootti3 kirjoitti:

Sagella onnistuu rationaalimatriisinkin laskeminen: http://sagecell.sagemath.org/

Saadaan vielä tarkkoja arvoja lisää:

9: 21248/35
10: 74752/63
11: 733696/315
12: 5300224/1155
13: 31418368/3465
14: 115552256/6435
15: 106977280/3003
16: 637534208/9009
17: 1267793920/9009
18: 4766040064/17017
19: 85425520640/153153
20: 3234139734016/2909907
21: 1535025086464/692835
22: 5843921666048/1322685
23: 128230272008192/14549535
24: 1961561493078016/111546435
25: 2348839113588736/66927861
26: 9016382767235072/128707425
27: 26000831711019008/185910725
28: 200248742308216832/717084225
29: 2799239198232543232/5019589575
30:10808563553590575104/9704539845

Lue lisää

Satasenkin vielä laskee aika nopeasti (siis ihan sekunnissa tai silleen):

100: 55807888167665633278666064854421112512449568133585740156497427431424/43575234518570298227833630584570189723

Tuohan on erittäin harva tuo tilasiirtymämatriisi, josta käänteinen otetaan (tai itseasiassa I-Q:sta, missä Q on se transientti-blokki). Minkäköhänlainen koneisto tuolla sagessa on?

Kanootti3 kirjoitti:

Satasenkin vielä laskee aika nopeasti (siis ihan sekunnissa tai silleen):

100: 55807888167665633278666064854421112512449568133585740156497427431424/43575234518570298227833630584570189723

Tuohan on erittäin harva tuo tilasiirtymämatriisi, josta käänteinen otetaan (tai itseasiassa I-Q:sta, missä Q on se transientti-blokki). Minkäköhänlainen koneisto tuolla sagessa on?

Lue lisää

Hyvin lähellä 2^100:aa on: http://www.wolframalpha.com/input/?i=55807888167665633278666064854421112512449568133585740156497427431424/43575234518570298227833630584570189723 / 2^100

Silloinhan ne siirtymätodennäköisyydet riippuu siitä tultiinko tilaan suuremmasta päin vai pienemmästä päin. Pitää ottaa kaksi riviä niitä tiloja eli 2n kappaletta, tässä kuva ja esimerkit matriisista sekä odotusarvonlaskusta n=3 ja n=4:

https://aijaa.com/oHURvj

Huomaa, että tilaan (n-1)- ei päästä muista tiloista, sillä tila n on absorboiva, mutta se nyt on mukana. Aika sähläämistä oli saada nuo matriisit muodostettua oikein, mutta toivottavasti se nyt meni oikein, tässä koodini:

http://tpcg.io/OBuJ4L

Ja tällaiset odotusarvot se antaa, (kun sagella sitten laskee):

3: 6
4: 44/3
5: 32
6: 992/15
7: 400/3
8: 9312/35
9: 7936/15
10: 331264/315
11: 73216/35
12: 2886656/693
13: 2615296/315
14: 248676352/15015
15: 114546688/3465
16: 84963328/1287
17: 396034048/3003
18: 40358772736/153153
19: 4744675328/9009

Miten on, tukeeko simulaatio näitä, vai teinkö jossain virheen? Idean ( /- -tilat) pitäisi ainakin toimia.

Kanootti3 kirjoitti:

Silloinhan ne siirtymätodennäköisyydet riippuu siitä tultiinko tilaan suuremmasta päin vai pienemmästä päin. Pitää ottaa kaksi riviä niitä tiloja eli 2n kappaletta, tässä kuva ja esimerkit matriisista sekä odotusarvonlaskusta n=3 ja n=4:

https://aijaa.com/oHURvj

Huomaa, että tilaan (n-1)- ei päästä muista tiloista, sillä tila n on absorboiva, mutta se nyt on mukana. Aika sähläämistä oli saada nuo matriisit muodostettua oikein, mutta toivottavasti se nyt meni oikein, tässä koodini:

http://tpcg.io/OBuJ4L

Ja tällaiset odotusarvot se antaa, (kun sagella sitten laskee):

3: 6
4: 44/3
5: 32
6: 992/15
7: 400/3
8: 9312/35
9: 7936/15
10: 331264/315
11: 73216/35
12: 2886656/693
13: 2615296/315
14: 248676352/15015
15: 114546688/3465
16: 84963328/1287
17: 396034048/3003
18: 40358772736/153153
19: 4744675328/9009

Miten on, tukeeko simulaatio näitä, vai teinkö jossain virheen? Idean ( /- -tilat) pitäisi ainakin toimia.

Lue lisää

Tuosta 2^n:n lähestymisestä, nopeammasta tai hitaammasta en kyllä osaa sanoa varmaksi mitään. Miten siihen voisi nähdä jotain asymptoottistakaan kaavaa, josta sen näkisi?

Kanootti3 kirjoitti:

Tuosta 2^n:n lähestymisestä, nopeammasta tai hitaammasta en kyllä osaa sanoa varmaksi mitään. Miten siihen voisi nähdä jotain asymptoottistakaan kaavaa, josta sen näkisi?

Toistin 17 lampulla 20 kertaa 10 000 toiston sarjan. Keskiarvo arviolta hiukan vajaa 132000. (Vaihtelee n. 12900 ja 13300 välillä.) Vastaa täysin tarkkaa tulostasi.

Jos samaa lamppua ei valita koskaan peräkkäin, tulos on varmasti pienempi. Jos tarkka tuloksesi ei ole koskaan alle 2^n, helppo päätellä kumpi lähestyy nopeammin.

Kanootti3 kirjoitti:

Silloinhan ne siirtymätodennäköisyydet riippuu siitä tultiinko tilaan suuremmasta päin vai pienemmästä päin. Pitää ottaa kaksi riviä niitä tiloja eli 2n kappaletta, tässä kuva ja esimerkit matriisista sekä odotusarvonlaskusta n=3 ja n=4:

https://aijaa.com/oHURvj

Huomaa, että tilaan (n-1)- ei päästä muista tiloista, sillä tila n on absorboiva, mutta se nyt on mukana. Aika sähläämistä oli saada nuo matriisit muodostettua oikein, mutta toivottavasti se nyt meni oikein, tässä koodini:

http://tpcg.io/OBuJ4L

Ja tällaiset odotusarvot se antaa, (kun sagella sitten laskee):

3: 6
4: 44/3
5: 32
6: 992/15
7: 400/3
8: 9312/35
9: 7936/15
10: 331264/315
11: 73216/35
12: 2886656/693
13: 2615296/315
14: 248676352/15015
15: 114546688/3465
16: 84963328/1287
17: 396034048/3003
18: 40358772736/153153
19: 4744675328/9009

Miten on, tukeeko simulaatio näitä, vai teinkö jossain virheen? Idean ( /- -tilat) pitäisi ainakin toimia.

Lue lisää

Simuloimalla sain kaikki alkupään (3...8) arvot ainakin neljän numeron tarkkuudella samoiksi.

Absoluuttinen ero (arvo(n) - 2^n) kasvaa koko ajan. Ja myös ero(n 1)/ero(n) alkaa kasvamaan 9 lampun jälkeen.

Purin taulukkosi numerota tekijöihin. Näyttäisi siltä, että arvon laskemiseksi löytyy kaava f(n)*2^(n-1)/(n-1)! Kertoman kaikki parilliset tekijät saa aina supistumaan pois.

f(n) = 1, 3, 11, 48, 248, 1500, 10476, 83328... Kuka keksii, mikä f(n) on?

02: 2
03: 2^2*3/2
04: 2^3*11/2*3
05: 2^4*16*3/2*3*4
06: 2^5*8*31/2*3*4*5
07: 2^6*12*125/2*3*4*5*6
08: 2^7*12*9*97/2*3*4*5*6*7
09: 2^8*2^7*3*7*31/2*3*4*5*6*7*8
10: 2^9*647/5*7*9
11: 2^10*2*11*13/5*7
12: 2^11*2819/2*7*9*11
13: 2^12*1277/2*5*7*9
14: 2^13*4*7589/3*5*7*11*13
15: 2^14*55931/2*4*5*7*9*11
16: 2^15*20743/8*9*11*13
17: 2^16*6043/3*7*11*13
18: 2^17*367*839/7*9*11*13*17
19: 2^18*53*683/2*7*9*11*13

Alkuperäisen tehtävän taulukosta saatta löytyä myös jotain vastaavaa.

PytnonillaHelppoa kirjoitti:

Simuloimalla sain kaikki alkupään (3...8) arvot ainakin neljän numeron tarkkuudella samoiksi.

Absoluuttinen ero (arvo(n) - 2^n) kasvaa koko ajan. Ja myös ero(n 1)/ero(n) alkaa kasvamaan 9 lampun jälkeen.

Purin taulukkosi numerota tekijöihin. Näyttäisi siltä, että arvon laskemiseksi löytyy kaava f(n)*2^(n-1)/(n-1)! Kertoman kaikki parilliset tekijät saa aina supistumaan pois.

f(n) = 1, 3, 11, 48, 248, 1500, 10476, 83328... Kuka keksii, mikä f(n) on?

02: 2
03: 2^2*3/2
04: 2^3*11/2*3
05: 2^4*16*3/2*3*4
06: 2^5*8*31/2*3*4*5
07: 2^6*12*125/2*3*4*5*6
08: 2^7*12*9*97/2*3*4*5*6*7
09: 2^8*2^7*3*7*31/2*3*4*5*6*7*8
10: 2^9*647/5*7*9
11: 2^10*2*11*13/5*7
12: 2^11*2819/2*7*9*11
13: 2^12*1277/2*5*7*9
14: 2^13*4*7589/3*5*7*11*13
15: 2^14*55931/2*4*5*7*9*11
16: 2^15*20743/8*9*11*13
17: 2^16*6043/3*7*11*13
18: 2^17*367*839/7*9*11*13*17
19: 2^18*53*683/2*7*9*11*13

Alkuperäisen tehtävän taulukosta saatta löytyä myös jotain vastaavaa.

Lue lisää

Google tunnisti taas tuttuun tapaan heti lukujonon: 1, 3, 11, 48, 248, 1500, 10476, 83328.
Number of strong fixed blocks in all the permutations of [n]:
https://oeis.org/A186374

Taulukon rivin 19: arvo on täsmää, kun käytetään linkin antamaa arvoa 12862666543104000. Jokainen pystyy laskemaan taulukon seuraavat 431 arvoa käyttäen linkin linkistä ( https://oeis.org/A186374/b186374.txt ) saatavia lukuja. Vaatii ääretöntä tarkkuutta, sillä luvut kasvavat monisatanumeroisiksi

PytnonillaHelppoa kirjoitti:

Simuloimalla sain kaikki alkupään (3...8) arvot ainakin neljän numeron tarkkuudella samoiksi.

Absoluuttinen ero (arvo(n) - 2^n) kasvaa koko ajan. Ja myös ero(n 1)/ero(n) alkaa kasvamaan 9 lampun jälkeen.

Purin taulukkosi numerota tekijöihin. Näyttäisi siltä, että arvon laskemiseksi löytyy kaava f(n)*2^(n-1)/(n-1)! Kertoman kaikki parilliset tekijät saa aina supistumaan pois.

f(n) = 1, 3, 11, 48, 248, 1500, 10476, 83328... Kuka keksii, mikä f(n) on?

02: 2
03: 2^2*3/2
04: 2^3*11/2*3
05: 2^4*16*3/2*3*4
06: 2^5*8*31/2*3*4*5
07: 2^6*12*125/2*3*4*5*6
08: 2^7*12*9*97/2*3*4*5*6*7
09: 2^8*2^7*3*7*31/2*3*4*5*6*7*8
10: 2^9*647/5*7*9
11: 2^10*2*11*13/5*7
12: 2^11*2819/2*7*9*11
13: 2^12*1277/2*5*7*9
14: 2^13*4*7589/3*5*7*11*13
15: 2^14*55931/2*4*5*7*9*11
16: 2^15*20743/8*9*11*13
17: 2^16*6043/3*7*11*13
18: 2^17*367*839/7*9*11*13*17
19: 2^18*53*683/2*7*9*11*13

Alkuperäisen tehtävän taulukosta saatta löytyä myös jotain vastaavaa.

Lue lisää

Alkuperäinen tehtävä ratkeaa kaavalla a(n-1)*2^(n-1)/(n-1)!, jossa a(n) = Sum_{k=0..n} k!(n-k)!

https://oeis.org/A003149

PythonillaHelppoa kirjoitti:

Alkuperäinen tehtävä ratkeaa kaavalla a(n-1)*2^(n-1)/(n-1)!, jossa a(n) = Sum_{k=0..n} k!(n-k)!

https://oeis.org/A003149

Lue lisää

Joo, juuri sain tuon itsekin. Taidan muuten tietää mistä se tavallaan tulee.
Jos muutetaan ketjua siten että ei lopetata kun päästään tilaan "kaikki päällä", niin raja-jakauma (stable distribution, mikä nyt onkaan) on w = ((n-1)C(k) / 2^(k-1))_k. Tämä mallihan on itse asiassa tunnettu Ehrenferstin uurna-malli ks. esim. https://en.wikipedia.org/wiki/Ehrenfest_model

Kysytty odotusarvo on "mean first passage time" m_{0n}. Tällä on yhteyksiä tasajakaumaan, esim. jos tutkittaisiinkin "mean recurrent time":a, r_j, eli odotusarvo siirtymille ennen kuin palataan tilaan josta lähdettiin, niin se olisi juuri tuon "equilibrium distribution":in käänteisluku 1/w_j ks. esim. https://www.dartmouth.edu/~chance/teaching_aids/books_articles/probability_book/Chapter11.pdf

Mutta mistä johtuu, että tuo vastaus on mean-recurrent-timien summa 0:sta (n-1):een? En ainakaan löydä tähän mitään yleistä teoriaa. Ergodisille Markovin ketjuillekin (jollainen tuo muokattu on) löytyy fundamentaalimatriisi, jonka avulla voi laskea mean-first-passage-timen (tietäsinpä nää termit suomeks ;D) kaavalla (z_{jj} - z_{ij})/w_j, ja näin se kakkosen potenssi tulee termistä w_0, joka siis on vain 1/2^(n-1), mutta siinä on vielä, tuo z-termi, joka luultavasti menee ykköseen, mutta miten sen näkee, en tiedä.

Mites muuten tuo kaava (vaikkei sitäkään vielä todistettu olla), sehän on (kun (n-1)! viedään summan sisään, niin 2^(n-1) kertaa binomikertoimien käänteislukujen summa, niin miten sitä voisi arvioida?

Kun kaavasta poistaa 2^(n-1), niin jäljelle jäävän osan arvo lähestyy kahta. Ilman lisätarkkuuksia python3:lla:
1000: 2.0020060261510912
2000: 2.001001503259409

Symmetrisestä summalausekkeesta riittää laskea vain puolet. Silloin lähestytään yhtä. (n-1)! :sta
voidaan poistaa ainakin kaikki alkupuolen kertoimet. Nehän löytyvät jokaisesta summalausekkeen osasta. Sieventämistä voi jatkaa osasta summan osatekijöitä erikseen. Sitten vaan laskemaan ylä ja alapuoli erikseen.

PythonillaHelppoa kirjoitti:

Kun kaavasta poistaa 2^(n-1), niin jäljelle jäävän osan arvo lähestyy kahta. Ilman lisätarkkuuksia python3:lla:
1000: 2.0020060261510912
2000: 2.001001503259409

Symmetrisestä summalausekkeesta riittää laskea vain puolet. Silloin lähestytään yhtä. (n-1)! :sta
voidaan poistaa ainakin kaikki alkupuolen kertoimet. Nehän löytyvät jokaisesta summalausekkeen osasta. Sieventämistä voi jatkaa osasta summan osatekijöitä erikseen. Sitten vaan laskemaan ylä ja alapuoli erikseen.

Lue lisää

Koko kaava on 2^(n-1)*2(1 1/(n-1) 2/((n-1)(n-2)) 3!/ ((n-1)(n-2)(n-3)) ... ((n-2)/2)!/((n-1)(n-2)...(n-((n-2)/2))))

Lähestytään erittäin tarkasti arvoa 2^n(1 1/(n-1)), eikä varmasti koskaan aliteta tuota. Arvioon voi tietysti lisätä seuraavankin termin summalausekkeesta, muttei se eikä muut termit yhdessäkään vaikuta juuri mitään. Kokeiltu on. Voi varmasti todistaakin, jos haluaa.

PythonillaHelppoa kirjoitti:

Koko kaava on 2^(n-1)*2(1 1/(n-1) 2/((n-1)(n-2)) 3!/ ((n-1)(n-2)(n-3)) ... ((n-2)/2)!/((n-1)(n-2)...(n-((n-2)/2))))

Lähestytään erittäin tarkasti arvoa 2^n(1 1/(n-1)), eikä varmasti koskaan aliteta tuota. Arvioon voi tietysti lisätä seuraavankin termin summalausekkeesta, muttei se eikä muut termit yhdessäkään vaikuta juuri mitään. Kokeiltu on. Voi varmasti todistaakin, jos haluaa.

Lue lisää

Joo kakkosta lähestyy, sen saa helpohkolla arviolla. Täällä https://math.stackexchange.com/questions/151441/calculate-sums-of-inverses-of-binomial-coefficients löydetty myös toisenlainen kaava: geometrinen suhdeluku 2, mutta termi jaettuna k:lla.

Huomasitko muuten tuolla OEIS:ssa: "The sequence (origin 1) is the resistance between opposite corners of an n-dimensional hypercube of unit resistors, multiplied by n!." eli sitä kautta tulos varmaan tulee. Varmaan on joku yleinen lause olemassa, joka sanoo, että odotusarvo on näiden resistanssien summa (tai ainakin nyt, kun ketjunhan on kuljettava jokaisen tilan läpi, koska se on vain yksi putki).

Muuten, tuo jälkimmäinen versio ( https://oeis.org/A186374 ), siellähän sanotaan

a(n) ~ 2 * (n-1)! * ((1 1/n^2 7/n^3 49/n^4 391/n^5 3601/n^6 37927/n^7 451249/n^8 5995591/n^9 88073041/n^10)).

joten 2^n lähestyy tämäkin versio. Tämä on kyllä aika jännä yhteys, että mistä tuo "fixed block", juttu tulee. Toisaalta siellä sanotaan, että se on ensimmäisen version kahden edellisen erotus, joten tulisiko sitä kautta?

Kanootti3 kirjoitti:

Joo kakkosta lähestyy, sen saa helpohkolla arviolla. Täällä https://math.stackexchange.com/questions/151441/calculate-sums-of-inverses-of-binomial-coefficients löydetty myös toisenlainen kaava: geometrinen suhdeluku 2, mutta termi jaettuna k:lla.

Huomasitko muuten tuolla OEIS:ssa: "The sequence (origin 1) is the resistance between opposite corners of an n-dimensional hypercube of unit resistors, multiplied by n!." eli sitä kautta tulos varmaan tulee. Varmaan on joku yleinen lause olemassa, joka sanoo, että odotusarvo on näiden resistanssien summa (tai ainakin nyt, kun ketjunhan on kuljettava jokaisen tilan läpi, koska se on vain yksi putki).

Muuten, tuo jälkimmäinen versio ( https://oeis.org/A186374 ), siellähän sanotaan

a(n) ~ 2 * (n-1)! * ((1 1/n^2 7/n^3 49/n^4 391/n^5 3601/n^6 37927/n^7 451249/n^8 5995591/n^9 88073041/n^10)).

joten 2^n lähestyy tämäkin versio. Tämä on kyllä aika jännä yhteys, että mistä tuo "fixed block", juttu tulee. Toisaalta siellä sanotaan, että se on ensimmäisen version kahden edellisen erotus, joten tulisiko sitä kautta?

Lue lisää

Niin tietysti, nyt kun ajattelee: se jälkimmäinen versiohan on kaksi edellisen tapaista putkea (ja toinen yhden, toinen kaksi lyhyempi ja toinen menee takaisin päin)!

Täällä https://www.cs.cmu.edu/~avrim/598/chap5only.pdf on vähän selkeämmin ehkä selitetty. Siis se m onkin sivujen määrä, mutta silloinhan 2m = n*2^n, eli sinne tulee ylimääräinen n, no nyt kun sitä tarkemmin miettii, niin niinhän se taisi tulla tuossa ekassakin, sillä jokaisesta solmusta lähtee n sivua ja sillähän se pitää jakaa, että saadaan todennäköisyyksiä.

Mutta meneekö tuo n siihen kertomaan mukaan vai mitä sille tapahtuu?

Odotusarvo siirtymille, kun lähdetään tilasta "n-1 lamppua päällä" on

h_{n-1, n} = 2^{n} - 1

(tämähän nähdään myös siitä, että se on r_{n} - 1, missä r_{n} on odotusarvo siirtymille, että palataan tilaan n (ja koska tn:llä 1 siirrytään tilaan n-1). Nämä palaamisen odotusarvot saadaan tasapainotilan komponenttien käänteislukuina. Tasapainotila on binomikertoimet, joiden summa on 2^n, jolla täytyy siis jakaa, jotta vektori summautuu ykköseen. Viimeinen binomikerroin binomial(n,n)=1, joten saadaan tuo tulos.)

Voisikohan sitä intuitiivisesti ajatella jotenkin näin: Koska suurille n suurella todennäköisyydellä lähdetään seilaamaan sinne keskivaiheille, niin se on oikeastaan melko sama mistä kohdin ketjua lähdetään. Tässä ajattelussa on toki se vaara, että ne suurusluokat ei toimikaan sillä tavoin yhteen, mutta nythän se on laskemalla todistettu.

Tämä oli siis alkuperäiselle versiolle, jossa saman valintaa peräkkäin ei kielletä. Varmaan senkin voisi samalla tavalla ratkaista, mutta sitä voisi tosiaan jo miettiä tuolla sähköverkko ja effektiivinen resistiivisyys -tavalla.

Onpa muuten hyvä, että nostettiin vielä tämä vanha tehtävä ja sinä keksit sen kaavan (lukujen hajotelmista!), tämähän johti ihan uusiin ideoihin.

Puurakenteesa riittää tarkastella vain palavien lamppujen määrien lukumääriä. Niiden järjestyksellähän ei ole mitään merkitystä. Kaikki mahdollisuudet:

0 kertaa:. 1(0) (kaikki lamput sammuneena)
1 kerta_: 3(1) (kaikissa kolmessa tapauksessa 1 lamppu palaa)
2 kertaa: 3(0) 6(2)
3 kertaa: 9(1) 12(1) 6(3) = 21(1) 6(3)
4. jatkuu samanlaisena

Myös 4 lampun tehtävä voidaan laskea samalla tavalla, mutta siinä muodostuu aina kaksi haraa ja todennäköisyydet muuttuvat koko ajan ja niitä pitää päivittää koko ajan. 15 riviä koodia. Suppenee äärimmäisen hitaasti. Viiden numeron tarkkuus vaati n. 200 toistoa. Luvut kasvavat mielettömän suuriksi, ellei niitä supistele koko ajan.

Lyhyt Python ohjelma, joka simuloi tuota janalla liikkumista edestakaisin 5 lampun (n) tapauksessa. Palavien lamppujen määrä (tai edetty matka) on a.

from random import randint
n = 5
c = 0
for i in range(0,10**6):
____a = 0
____while a != n:
________if a < randint(1,n): a = a 1
________else: a = a - 1
________c = c 1
print(n, c)

Riittää todellakin tarkastella aina vain palavien lamppujen määriä (edettyä matkaa). Ei voine enää paljoa yksinkertaistaa. Kukahan on ratkaissut kaavan ensimmäisenä, missä yhteydessä ja millä vuosisadalla?

Tehtävä on sen verran "helppo", että se voidaan ratkaista toinen toistaan helpommila tavoilla. Täällä on esitetty vasta neljä tai viisi tapaa. Kerro oma yksinkertainen ratkaisutapasi. Niitä riittää! Oikea vastaus karsii täysin väärät ratkaisuehdotukset. Ihan normaalia matematiikassa.

Tästäkinhän saisi hyvän uhkapelin: Joka kerta kun tullaan tyhjälle ruudulle, siihen täytyy laittaa euro. Jos tullaan täydelle ruudulle, niin siinä olevan menettää. Kun kaikki ruudut tulee täyteen, voittaa kaiken laudalla olevan w-kertaisena.
Jos on 5 ruutua ja nopassa 6 tahkoa ja w=4,5 (eli potti on 22,5 euroa), niin kannattaako pelata?

Tätä versiota hankaloittaa se, että tn:t ruudulle, jolle laskeudutaan riippuu ruudusta, jolla ollaan. Jos nopassa on yhtä monta tahkoa kuin ruutuja laudalla, niin silloinhan tämä palautuu alkuperäiseen lampputehtävään, sillä jokainen ruutu on yhtä mahdollinen.

Tästäkin voi kyllä tehdä Markovin ketjun, mutta en ainakaan keksi muuta tapaa, kuin ottaa tiloiksi kaikki 2^n konfiguraatiota ruuduille (kun luetaan sykli lähtien siitä missä ruudussa pelaaja on).

Tässä Python-koodi, jolla generoin matriisin
http://tpcg.io/yVFZ8k

Lieköhän tässäkin 2^n asymptoottinen kaava odotusarvolle E["heittojen määrä ennen kuin lauta on täynnä"]?

Voisiko sitä ajatella näin (myös alkuperäisessä tapauksessa): koska suurilla n se kuitenkin vie monta (välttämättäkin ainakin n) askelta ja siinä samalla todennäköisyysjakauma sille missä tilassa ollaan lähestyy raja-jakaumaa, joka on tasajakauma, niin näin ollen myös odotusarvo lähenee sen avulla laskettua eli 2^n:ää (joka itse asiassa oli ensimmäin tähän viestiketjuun tullut vastaus, mutta se hylättiin tuossa n=3 tapauksessa, kun haluttiin tarkka vastaus :D)?

PS. Tai siis se tn. missä tilassa ollaan vuorottelee ketjun periodisuudesta johtuen (parillisen vs. parittoman päässä olevat tilat), mutta suhde minkä verran on kussakin tilassa oltu lähenee raja-jakaumaa.

Tuo viimeinen huomio on kyllä melko triviaali, sillä tietenkin joka kerta tilassa n-1 valinta on vain mennäänkö loppuun vai ei (jolloin tulee olemaan uusi vierailu), joten sen vierailut on geom(1/((n-1)^r 1)) jakautunut.