Vangin pasianssin todennäköisyydet

Hmmm.. Itse saan vähän eri tulokset:

P(X=0) = 0.003702
P(X=1) = 0.019696
P(X=2) = 0.057118
P(X=3) = 0.113366
P(X=4) = 0.1673
P(X=5) = 0.192721
P(X=6) = 0.178426
P(X=7) = 0.13303
P(X=8) = 0.078939
P(X=9) = 0.03777
P(X=10) = 0.013507
P(X=11) = 0.00377
P(X=12) = 0.000607
P(X=13) = 0.000048

(Jäikö sinulta yksi pois, kun niitähän pitäisi olla 14?)
Tein simulaation uudestaan kolmella eri kielellä ja koitin aina unohtaa entisen, mutta sehän saattaa olla, että itse minulla tuli sitten kaikissa sama ajatusvirhe. Täältä löytyy tekeleitäni (C ja Python-versiot): https://github.com/minkkilaukku/prisoners-solitaire ja JS on täällä: https://repl.it/@minkkilaukku2/Prisoners-Solitaire

Siellä Python-tiedostossa on myös yritystä laskea tarkasti, laitan ehkä toiseen viestiin niitä pohdelmiani, ettei tästä nyt tule niin pitkä.


Jos tuo tarina, että 5000 kertaa piti vangin koittaa ennen kuin onnistui on totta (tai vaikka olisi keksittykin, mutta luvut laitettu todennäköisiksi), niin tuo minun vastaus 0.0037 on kyllä liian iso, sillä todennäköisyys, että vie vähintään 5000 yritystä on tällöin

(1-0.0037)^5000 = 0.9e-9

eli erittäin pieni.
Arvolla p = 2e-05, se että vie korkeintaan 5000 yritystä olisi

1 - (1-2e-05)^5000 = 0.095

eli vähän järkevämpi.

En tiedä simuloinko väärin. Tässä koodini:

from random import shuffle
tulos = [0]* 13
kertoja = 100000
for kerta in range(kertoja):
x = [i for i in range(52)]
shuffle(x)
y = x[0:13]
z = x[13:26]
A = []
B = []

for i in range(13):
A.append(y[i] % 13)
B.append(z[i] % 13)
yhteiset = set(A) & set(B)
tulos[len(yhteiset)] = 1
for i in range(13):
print(tulos[i]/kertoja)
print(summa)

Anonyymi kirjoitti:

En tiedä simuloinko väärin. Tässä koodini:

from random import shuffle
tulos = [0]* 13
kertoja = 100000
for kerta in range(kertoja):
x = [i for i in range(52)]
shuffle(x)
y = x[0:13]
z = x[13:26]
A = []
B = []

for i in range(13):
A.append(y[i] % 13)
B.append(z[i] % 13)
yhteiset = set(A) & set(B)
tulos[len(yhteiset)] = 1
for i in range(13):
print(tulos[i]/kertoja)
print(summa)

Lue lisää

Hmmm.. Siinä taitaa käydä niin, että kun sä otat nuo yhteiset joukkona, niin se ei huomioi sitä kuinka monta A:sta poistuu (eli pinon kokoa). Minä muutin koodia näin (
ja nyt se antaa samanlaisen tuloksen kuin itselläni)

tulos = [0]* 14
.
.
.
#yhteiset = set(A) & set(B)
..for u in B:
....while u in A: A.remove(u)
..tulos[len(A)] = 1
.
.
Tai miksei jopa kirjoittaisi tuota A:n ja B:n täyttöä suoraan:
A = [u for u in y]
B = [u for u in z]

PS. Tuota että Pythonissa joukot voi &-operaattorilla leikata, ja näköjään myös |-operaattorilla yhdistää) en tiennytkään. Kätevä!

minkkilaukku kirjoitti:

Hmmm.. Siinä taitaa käydä niin, että kun sä otat nuo yhteiset joukkona, niin se ei huomioi sitä kuinka monta A:sta poistuu (eli pinon kokoa). Minä muutin koodia näin (
ja nyt se antaa samanlaisen tuloksen kuin itselläni)

tulos = [0]* 14
.
.
.
#yhteiset = set(A) & set(B)
..for u in B:
....while u in A: A.remove(u)
..tulos[len(A)] = 1
.
.
Tai miksei jopa kirjoittaisi tuota A:n ja B:n täyttöä suoraan:
A = [u for u in y]
B = [u for u in z]

PS. Tuota että Pythonissa joukot voi &-operaattorilla leikata, ja näköjään myös |-operaattorilla yhdistää) en tiennytkään. Kätevä!

Lue lisää

Prosentit näköjään muuttui joksikin, (taisvat jäähä kiinni u:hun), kokeillaas uudestaan:

A = [u % 13 for u in y]
B = [u % 13 for u in z]

""Tuo ensimmäisen valinnan laskuhan on sama kuin tämäkin, mutta...""

Tai siis, nythän lasketaan eri asiaa: sillä toisen valinnan tyypillä ei ole väliä vaan siinä pitää olla vähintään 1 jokaista jotain kiinitettyä lukua, joten ei se lasku ole sama, mutta jotain saman tyyppistä pohdintaa siinä pitää varmaan harjoittaa(?)

Niin ja tämä on siis vain tuon X=0 tapauksen laskemista kohden tämä jälkimmäisen valinnan lasku. Sehän menee erittäin monimutkaiseksi se, että monta sitten lopulta jää.

Minä aloitan nyt pohdinnan uudesta kulmasta.
Kun se pöydän tyyppi on tullut, niin lähdetään yksi kerrallaan ottamaan pakasta niitä testauskortteja (nythän on helppo laskea tn. siirtyä toiseen tyyppiin ja siihen mitä pakassa on jäljellä (jos tulee tyhjä kortti, niin pöydän tyyppi ei muutu, mutta pakassa on yksi kortti vähemmän, voisiko se olla niin, että se ei riipu mikä kortti sieltä 'tyhjänä' heitetään pois vaikka tyyppi muuttuisikin sitten jatkossa eli siihen tulisi eri edustajat niille tyypin luvuille??
Silloinhan sen saisi melko helposti luultavasti dynaamisella ohjelmoinnilla laskettua. Pitäisi koittaa...

Funktio
calculateProb(suits, vals, handLen, pickN)
näyttäisi toimivan, mutta ne jälkimmäiset luvut lasketaan yhä brute-forcena. Kokeilin pienillä arvoilla ja vertasin simuloituun arvoon.

"Toisten lukujen" laskemiseksi:

Olkoon M = {nj * j} multijoukko (alkiota j nj kappaletta, j=1..m). Sen k-kombinaatioiden lukumäärä saadaan polynomin

(1 z ..z^n1) * ... * (1 z ...z^nm)

termin z^k kertoimesta. Ja sellaisten kombinaatioiden, joissa alkioita j, j=1..p, on ainakin yksi saadaan, kun jätetään ykkönen pois näistä polynomeista tuossa yllä olevassa tulossa. (Tai yleisemmin: otetaan vain ne termit kuhunkin polynomiin mitkä lukumäärät tälle alkiolle kombinaatioon sallitaan).
Muistatteko sen lotto-tehtävän, tämähän on samanlainen! Mutta nyt tuloon tulee monen tyyppisiä termejä, riippuen millainen tyyppi pakasta on otettu pois. Mathematica osaisi varmaan tehokkaasti laskea nuo kertoimet. Löytyisiköhän Python-koodia mistä?

Vastaus siis saadaan, kun otetaan summa jokaisen tyypin yli (niitä oli ne 39) termeistä

P(pöydälle tulee tämä tyyppi t) * P(jäljellä olevasta pakasta (josta siis poistettu tyypin t mukaan) tulee sellainen 13-kombinaatio, että siinä on vähintään 1 jokaista tyypin korttia).

Nämä jälkimmäiset todennäköisyydethän voisi laskea jopa siten, että ajattelee pakkaa multijoukkona {(4-t1)*1, (4-t2)*2, ..., (4-tr)*r, (loput)*(r 1)}, eli emäfunktion viimeinen polynomi olisi (1 z ... z^loput). Osoittajaan kerroin siitä missä ykköset jätetty 1..r:stä pois ja nimittäjään siitä missä ne mukana.

Tein sen noin mutta antoi väärän tuloksen. Mutta nyt taidan ymmärtää mistä se johtuu:
Tuo antaa ne multijoukon kombinaatiot ihan oikein, mutta ongelma on siinä, että näiden todennäköisyydet tulla on erilaisia. Esim jos pakassa on 2 nollaa, 2 ykköstä ja 4 kakkosta, niin kombinaation '0,0,1' saaminen on pienempi kuin '0,0,2':n.
Korjaisikohan asian, jos mietittäisiinkin permutaatioita ja käytettäisiin eksponentiaalisia emäfunktioita?

Ei kyllä näyttäisi ihan suoraan vaan 1/k!:t polynomeihin polkaisemallakaan toimivan.

Koodia optimoitu nyt erittäin merkittävästi: siinä kun lasketaan niitä pakasta toisessa vaiheessa tulevia kelpaavia tyyppejä, että monta kutakin sellaista on, niin voidaan rajoittaa ne niin, että sen vektorin summa on korkeintaan se kuinka monta valitaan toisessa vaiheessa (13 tässä perusversiossa). Ne generoidaan siten, että otetaan kaikki lukujen |t|..pickN ositukset ja permutoidaan nämä. Tähän on funktio generateMultipermus -- muuten 13:n pituisten permutaatioiden kanssa olisi ehkä tulla vähän ongelmia (vaikka eihän siellä ole kuin se yksi 13 pituinen, kaikki ykkösiä ja siitä ei sitten tule itseasiassa kuin 1!

minkkilaukku kirjoitti:

Koodia optimoitu nyt erittäin merkittävästi: siinä kun lasketaan niitä pakasta toisessa vaiheessa tulevia kelpaavia tyyppejä, että monta kutakin sellaista on, niin voidaan rajoittaa ne niin, että sen vektorin summa on korkeintaan se kuinka monta valitaan toisessa vaiheessa (13 tässä perusversiossa). Ne generoidaan siten, että otetaan kaikki lukujen |t|..pickN ositukset ja permutoidaan nämä. Tähän on funktio generateMultipermus -- muuten 13:n pituisten permutaatioiden kanssa olisi ehkä tulla vähän ongelmia (vaikka eihän siellä ole kuin se yksi 13 pituinen, kaikki ykkösiä ja siitä ei sitten tule itseasiassa kuin 1!

Lue lisää

Jos pakassa olisi 16 korttia kutakin 4 maata, niin voitto-tn. olisi
1354983985597413560192/1457082583811094293369085 = 0.000929929436157

Se on kuitenkin nuo partitio-luvut, jotka tyyppien määrät ovat ja kasvavat eksponentiaalisesti, niin ei tällä menetelmällä kovin pitkälle pötkitä, tuokin vei jo taas 14 sekuntia.

minkkilaukku kirjoitti:

Jos pakassa olisi 16 korttia kutakin 4 maata, niin voitto-tn. olisi
1354983985597413560192/1457082583811094293369085 = 0.000929929436157

Se on kuitenkin nuo partitio-luvut, jotka tyyppien määrät ovat ja kasvavat eksponentiaalisesti, niin ei tällä menetelmällä kovin pitkälle pötkitä, tuokin vei jo taas 14 sekuntia.

Lue lisää

Ai niin, ja tuo siis jos lätkittäisiin 16 kolmentoista asemesta myös pöydälle ja sen jälkeen nostettaisiin pakasta, eli 'joka kolmas', niinkuin se alunperin ilmaistiin.

Ne luvuthan (boardN ja pickN) siinä kasvattavat laskentaa. Jos olisi 50*4 korttia, ja boardN = pickN = 13, niin tulos on

1416074149056783184/17785457959223804854010008101 = 7.96197743293e-11

eikä laskenta vie kuin sekunnin.