Keskustelu: Yleinen keskustelu: Korttipakkojen todennäköisyyslasku

Hei, minulla tuli vastaan seuraava todennäköisyys lasku:
Oletetaan että korttipakassa on 52 + 2 uniikkia korttia. Otetaan neljän pakan kortit, sekoitetaan ne keskenään, ja poistetaan satunnaisesti yhden korttipakan verran (eli 54) korttia. Jäljelle jää siis 3 x 54 = 162 korttia. Mikä on todennäköisyys että näistä saadaan koottua ainakin yksi kokonainen (54 kortin) pakka?

Tämä on sama todennäköisyys, kuin että kaikista 54 tyypistä jää jäljelle vähintään yksi kappale, eli että poistetuista 54 kortista ei löydy samaa korttia neljästi.

Aluksi estimoin todennäköisyyden simuloimalla, ja sain vastaukseksi 82.04 +/- 0.01 prosenttia. Seuraavaksi yritin muodostaa Markov-ketjun, mutta ekstrapoloinnin perusteella tässä ketjussa on noin 4.5 * 10^5 tilaa!

https://dl.dropbox.com/u/11837728/coding/carddeck/number_of_states.png

Täytynee käyttää dynaamisen ohjelmoinnin lähestymistapaa, ja analysoida tilannetta kun pakassa on 4, 5, 6, ... korttia. Neljän kortin tapaus on helppo (16 kortista poistetaan 4), mutta jo 5 kortilla tuohon syntyy jo muutamia eri tapauksia.

Jos pakassa on 5 korttia, todennäköisyys onnistumiselle pitäisi olla noin 99.485 +/- 0.002 prosenttia, ja 6 kortilla 99.152 +/- 0.003 prosenttia. Haluaisin tietää nämä prosentit n-kortin pakalla ilman simulointia.

Seuraava dynaamisen ohjelmoinnin ratkaisu laskee tarkan tuloksen:

def fact(n):
    if n <= 0:
        return 1
    return n*fact(n-1)

def ncr(a,b):
    return fact(a)/(fact(b)*fact(a-b))

muisti = {}

def d(a,b,c):
    if a < 0 or b < 0:
        return 0
    if a == 0:
        return 1
    if (a,b,c) in muisti:
        return muisti[(a,b,c)]
    tulos = 0
    for i in range(c+1):
        tulos += ncr(4,i)*fact(i)*ncr(a,i)*d(a-i,b-1,c)
    muisti[(a,b,c)] = tulos
    return tulos

print 1.0*d(54,54,3)/d(54,54,4)

Ohjelman tulostus:

0.820296090898

Funktio d(a,b,c) laskee, monellako tavalla voidaan valita a korttia niin, että suurin kortti on b ja sama kortti saa toistua enintään c kertaa.

Vastaavat muistit voi tehdä fact- ja ncr-funktioille, jolloin ylläoleva nopeutuu yli kymmenkertaiseksi.