Kolme lamppua rivissä, aluksi kaikki pois päältä. Satunnaisesti (tasajakauma) valitaan lamppu, jonka tila vaihdetaan (eli jos oli pois, niin sytytetään ja jos oli päällä, niin sammutetaan). Näin toimimalla, mikä on odotusarvo sille kuinka monta kertaa täytyy arpoa lamppu ja siis muuttaa lamppujen tilaa, jotta kaikki lamput ovat päällä.
Tämä on kenties helpompi versio tästä ns. lamppuongelmasta (joka itse asiassa on satunnaiskävely kuution kärjillä sivuja pitkin).
Vastaus on 10 ja tässä vinkki: tilat voi luokitella kolmeen kategoriaan, merkitse
m_{ij} = E[siirtojen määrä, jotta päästään tilasta i tilaan j ]
(huom. tällöin kysytty luku on m_{07} (ai, niin mä merkkaan niitä tiloja 000, 001, ..., 111 ja siitä sitten kymmenkantasiks ni lyhkäsempi))
ja muodosta kolme yhtälöä näitten lukujen välille.
Lampputehtävä, kaikki päälle
49
517
Vastaukset
- arvelen.kakdeksan
Kolmella "bitillä" voidaan esittää 8 konfiguraatiota. Jokainen kytkimen painallus tuottaa aina yhden konfiguraation eli jonkun näistä. Suuressa satunnaisesti valittujen konfiguraatioiden joukossa kahden tilan (esim. 0 0 0 ja 1 1 1) esiintymisväli on keskimäärin tuo 8.
- arvelin.väärin
Hätiköity vastaus mututuntumalta. Täytyy miettiä.
- Kanootti3
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).
- fdgsdfghsdfhdf
Siis pitäisikö 10 tilanvaihdolla olla mahdollista saada nuo kaikki lamput päälle? Minusta se menee niin, että millään parillisella määrällä tilanvaihtoja ei voi saada kaikkia kolmea lamppuja päälle.
- Kanootti3
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
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.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.
- fdgsdfghsdfhdf
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.Okei, mulle on jäänyt epäselväksi mitä odotusarvo tarkoittaa, siitä hämmennykseni. (Aihetta koskevasta Wikipedia-artikkelista minä en ymmärrä mitään.)
- Kanootti3
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).
- Karvamies
Yksi kerta riittää.
Tämän kaltaista kysymystähän kysyttiin aikoinaan 1980-luvulla Microsoftin työhaastattelussa.- Karvamies
"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.
- PytnonillaHelppoa
Tuossa Python 2 koodi, jossa oletetaankin lamppujen olevan aluksi päällä. Tulos sama 10.
import random
cs = 0
for i in range(0,1000000):
____a = [True, True, True]
____c = 0
____while a[0] or a[1] or a[2]:
________c = c 1
________r = random.randint(0,2)
________a[r] = not a[r]
____cs = cs c
print(cs) - MitenLie
Entä monellako "arvonnalla" todennäköisyys, että kaikki lamput ovat syttyneet, ylittää 0,5?
- Kanootti3
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. - MitenLie
Tuon 7 sain minäkin toisella tekniikalla.
- PytnonillaHelppoa
Yksinkertaistin ja nopeutin yllä esitettyä Python ohjelmaa korvaamalla listan a yksikertaisesti kokonaisluvulla (2**n) - 1, n on lamppujen määärä. Sitten vaan 1:n satunnaisella vasemmalle shiftillä (<<) ja xor:lla (^) vaihdellaan yhden lampun tilaa kunnes a == 0.
Tulos (hiukan vaihtelee!) lamppujen lukumäärän mukaan:
4. 21,35
5. 42,66
6. 83,3
7. 161,4
8. 312,0
16. 70500
Ei ihan kaksinkertaistu yhden lampun lisäyksellä, mutta melkein.- Kanootti3
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(?) - PytnonillaHidasta
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(?)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.
- Kanootti3
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
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.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. - Kanootti3
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
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/9704539845Satasenkin 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
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?Hyvin lähellä 2^100:aa on: http://www.wolframalpha.com/input/?i=55807888167665633278666064854421112512449568133585740156497427431424/43575234518570298227833630584570189723 / 2^100
- höhöhöhöhöhö
Ootsä iha Urpo. Kakstoist kertaa tietyst.
- PytnonillaHelppoa
Jos tehtävään lisätään hiven älykkyyttä ja kielletään saman lampun kytkimen edestakainen täysin turha heiluttelu, niin lähestytään lamppujen määrän (n) kasvaessa aikaisempaa nopeammin lukua 2^n.
Miten on tarkasti ja hienosti laskien? Vai meneekö vaikeaksi?- Kanootti3
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
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.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?
- PytnonillaHelppoa
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. - PytnonillaHelppoa
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.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. - PythonillaHelppoa
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.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 - PythonillaHelppoa
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.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 - Kanootti3
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/A003149Joo, 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? - PythonillaHelppoa
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
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.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. - Kanootti3
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.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
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?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)!
- Kanootti3
No nyt selvisi:
https://www.sciencedirect.com/science/article/pii/S0166218X10002027
("elegan relation" juuri ennen lausetta 2.4)
Ajatellaan taas ongelmaa kuution kärjillä satunnaiskävelynä. Tuon linkin mukaan odotusarvo siirtymille kun lähdetään solmusta i ja ekan kerran tullaan solmuun j ja sitten takaisin on R_eff * c, missä c=2^n, sillä valitaan yksikköresistanssit joka sivulle ja eli c_i = asklödfjp'ij
ja takaisin matka on symmetrian mukaan sama odotusarvo, joten vasemmalla on sama juttu kaksi kertaa.
Täällä on sama juttu, lause 4.11 (siellä puhutaan "commute time":sta)
https://homes.cs.washington.edu/~shayan/courses/cse599/adv-approx-4.pdf
Täällä taas on 2m, missä m on ilmeisesti solmujen määrä eli 2^n, joten tämä antaa oikean kaavan.- Kanootti3
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?
- PythonillaHelppoa
Lähtötilalla ei näyttäisi olevan paljoakaan merkitystä. Kävin läpi 8...11 lampun kaikki mahdolliset lähtötilat peräkkäin ja laskin niillä saman määrän kierroksia. Saman lampun valinta kielletty kahdesti peräkkäin. Tulos lähestyy 2^n. Millä ihmeen kaavalla?
- Kanootti3
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.
- NäinPeruskoulussaLasketa
Alkuperäinen 3 lampun tehtävä voidaan ratkaista ihan todennäköisyyslaskennan peruskurssin opeillakin summaamalla eri arpomiskertojen painotetut määrät. Aluksi tarvitaan kolme arpomiskertaa (27 vaihtoehtoa) ja onnistumistodennäköisyys on 6/27 = 2/9. Loput 7/9 päätyy 1 lampun palamiseen. Sitten tarvitaan aina kaksi arpomiskertaa lisää ja niistä aina 2/9 onnistuu. Ja sama jatkuu ikuisesti. Piirtämällä puurakenne eri vaihtoehdoista, havaitaan helposti yksinkertainen toistuvuus.
3((2/9) 5(2/9)(7/9) 7(2/9)(7/9)^2 9(2/9)(7/9)^3 .... = 9,99999999...
s = 0
for i in range(0,100): s = s (3 2*i)*(2./9)*(7./9)**i
print(s)- NäinLukiossaLasketaan
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.
- Kanootti3
Sain nyt todistettua kaavan
2^{n-1} /(n-1)! * sum_{j=0}^{n-1} k!(n-1-k)!
ihan "tavallisin" keinoin.
Merkitään h_{a, b} odotusarvoa kuinka monta askelta menee tilasta "a lamppua päällä" tilaan "b lamppua päällä". Lasketaan h_{0, n} summana vierekkäisistä siirtymistä h_{j, j 1}. Näille saadaan rekursio kaavasta
h_{j, j 1} = (n-j)/n j/n * (1 h_{j-1, j} h_{j, j 1}),
joka tulee siitä, että tilassa j voidaan joko siirtyä todennäköisyydellä (n-j)/n suoraan yhdellä siirtymällä seuraavaan, tai sitten mennään taakse päin, josta taas pitää siirtyä takaisin tilaan j ja sitten on taas tämä sama kyseinen odotusarvo siirtyä tilaan j 1.
Lisäksi alkuehto h_{0, 1}=1, sillä nollasta siirrytään tn:llä 1 ykköseen.
No, tämän rekursion ratkaisu on h_{j, j 1} = sum_{k=0}^j binomial(n, k) / binomial(n-1, j).
Sitten summataan ja saadaan tuo kaava, sillä summa bin(n, k):sta j:hin asti on sama kuin 2^n - "loput". Kirjoitetaan koko höskän eteen kerroin 1 = 1/2 1/2 ja toinen puolikas muutetaan tuohon 2^n-"loput" -muotoon. Indeksimuunnoksella (ja binomikertoimien symmetria) huomataan, että siinä on itse asiassa sama termi plussalla ja miinuksella ja näin ollen jää vain 2^n (ja 1/2 kertoimena, joten siitä tulee 2^{n-1}).- PythonillaHelppoa
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?
- qwerwqeqwewqeq
Helvettiäkö sä sen vastauksen samaan viestiin kirjoitit. Mikä järki?
- MontaRatkaisutapaa
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.
- HyviäOngelmiaRiittää
Ongelmasta voi kehittää nopalla pelattavan lautapelin. Kuusi (tai joku muu määrä) ruutua ympyrän kehälle. Aluksi kaikki tyhjiä. Heitetään noppaa ja siirytään aloitusruudusta nopan antama silmäluku eteenpäin. Jos valittu ruutu on tyhjä, lisätään siihen nappula ja jos ruudussa on jo nappula, se poistetaan. Seuraava aloitusruutu on viimeksi valittu ruutu. Tavoittena saada kaikkiin ruutuihin nappula.
Joku vastaava ikivanha matemaatikkojenkin tutkima lautapeli löytyy varmasti. Jos ruutuja on vaikkapa 10 ja käytetään yhtä tavallista (kuutio) noppaa, niin tarvittavan kaavan löytäminen saattaa olla haastava. Ainakin yleisessä tapauksessa.- Kanootti3
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.
- Kanootti3
Mitenkäs varianssi? Sen voi laskea wikipedian mukaan myös fundamentaalimatriisista: https://en.wikipedia.org/wiki/Absorbing_Markov_chain#Variance_on_number_of_steps (onko jollain muuten vinkkiä miten tuo kaava perustellaan).
Tapaukselle n=3 sain 63 ja tämä tulee myös laskemalla tavallisesti, kun ne tn:llehän oli kaava tiedossa: http://www.wolframalpha.com/input/?i=2/9 * \sum_{k=0}^\infty (3 2k-10)^2*(7/9)^k .
n=4: 2944/9
n=5: 13000/9
n=6: 148016/25
n=7: 585844/25
n=8: 335740928/3675
n=9: 434192544/1225
Näissäkin keskihajonnat näyttäsi about tuplaantuvan joka askeleella.
Sitten vielä: Jos mietitään sitä ketjua, jossa on vain lamppujen määrä ja siirtymätodennäköisyydet on (n-j)/n taaksepäin ja j/n eteenpäin. Mites jos siinä laitetaankin nämä potenssiin r (ja jaetaan niiden summalla, jotta ne summautuu ykköseen) eli j^r/(j^r (n-j)^r) ja (n-j)^r/(j^r (n-j)^r)? Millaiset on odotusarvot sitten.
Sellaisia huomioita minä tein, että kun r=2, niin odotusarvo, jos lähdetään viimeisestä tilasta on
2 * binomial(2(n-1), n-1) - 1
ja näin ollen (oletettavasti) myös odotusarvo mistä tahansa tilasta lähenevän suhteellisesti tätä 2 * binomial(2(n-1), n-1).
Lisäksi kaikille r näyttäisi että odotusarvo vierailuille tilassa n-1 on (n-1)^r 1 (tämähän ei riipu mistä tilasta lähdetään, koska tässä toiseksi viimeisessä on joka tapauksessa käytävä ja kun siinä ollaan ensimmäisen kerran, se on sama jos lähdettäisiin siitä (riippuuu tietenkin lasketaanko lähtö vierailuksi vai ei)).- Kanootti3
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.
Ketjusta on poistettu 0 sääntöjenvastaista viestiä.
Luetuimmat keskustelut
- 743500
- 2012932
- 252820
- 492708
- 222614
Kuule rakas...
Kerrohan minulle lempivärisi niin osaan jatkaa yhtä projektia? Arvaan jo melkein kyllä toki. Olethan sinä aina niin tyyl412415Miten hitsissä ulosoton asiakas?
On tää maailma kumma, tässä haisee suuri kusetus ja ennennäkemättömän törkeä *huijaus*! Miten to.monen kieroilu on edez2362011Törmättiin tänään
enkä taaskaan osannut reagoida fiksusti. Menen aina lukkoon. Yksi asia on varma: tunteeni sinua kohtaan ovat edelleen v241847- 421763
Kela valvoo lasten tilejä.
Tämä isoveli Kela kyttää jopa lasten yli 200,- euron rahat jotka on melko varmasti lahjaksi saatu. Se vaikuttaa perheen1591666