Värisuorien todennäköisyyksistä

Jos tavallisesta 52 kortin korttipakasta nostetaan satunnainen 7 kortin käsi, mikä on todennäköisyys, että käsi sisältää (ainakin) r peräkkäistä saman maan korttia?

Merkitään A_{i, j} = ”käsi sisältää kortit (i, j), (i+1, j), \dots, (i+r-1, j)”, arvoille i=1,2,\dots, 13-r+1 ja j= ♠, ♥, ♣, ♦. Merkitään näiden kaikkien tapahtumien joukkoa \cal{A}:lla. Kysytty todennäköisyys on tällöin

\begin{aligned} \mathbb{P} \left( \bigcup_{A\in\cal{A}} A \right) \end{aligned} .

Inkluusio-eksluusion periaatteen nojalla tämä voidaan laskea

\begin{aligned}   \mathbb{P} \left( \bigcup_{A\in\cal{A}} A \right)    =  \sum_{j=1}^{|\cal{A}|} (-1)^{j+1} \sum_{ \substack{ I\subset \cal{A} \\ |I| = j}} \mathbb{P} \left( \bigcap_{A\in I} A \right)  \end{aligned}

Merkitään tapahtumalle A \in \cal{A} symbolilla \bar {A} niiden korttien joukkoa, jotka siinä vaaditaan kädessä esiintymään. Huomataan, että tämä relaatio on siinä mielessä käänteinen, että kun tapahtumia A leikataan, vastaa tämä joukkojen \bar{A} yhdistettä. (Leikkautapahtuma tapahtuu jos ja vain jos käsi sisältää kaikki vaaditut kortit.)

Todennäköisyys \begin{aligned} \mathbb{P} \left( \bigcap_{A\in I} A \right)  \end{aligned} riippuu vain vaadittujen korttien unionin koosta t = \left(   \bigcup_{A\in I} \bar{A}  \right) sillä siinä vaaditaan leikkauksen korttien esiintyvän kädessä eikä sillä ole väliä mitkä kortit ne ovat. Hypergeometrisen jakauman mukaan tämä todennäköisyys on

p_t := \begin{aligned} \frac{ {{t} \choose {t}}  {{52-t} \choose {7-t}} }{ {{52} \choose {7}} } =  \frac{  {{52-t} \choose {7-t}} }{ {{52} \choose {7}} }  \end{aligned}

Täytyy siis selvittää kuinka monta t:n kokoista unionia \bigcup_{I\subset \cal{A}} \bar{A} tasolla |I|=j on. Merkitään tätä c_{j, t}.

Koska p_t = 0 , kun t>7, niin tarvitaan vain arvot, joissa t\leq 7. Lisäksi, koska tason j unioni koostuu j joukosta ja ensimmäinen tuo r alkiota ja seuraavat jokainen ainakin yhden lisää (joukot \bar{A} ovat pötköjä, jotka menevät maksimissaan r-1:n verran päällekkäin), niin saadaan myös yläraja j\leq 7-r+1.

Lukujen c_{j, t} laskeminen voidaan tehdä brute-forcena. Tapaus r=2 on melko raskahko, sillä siinä täytyy laskea arvoon j=6 asti ja {{4\times 12}\choose{6}} = 12 271 512. Tapaus r=2 on kuitenkin toisella tapaa yksinkertaisempi ja sen voi ratkaista tutkimalla kuinka monella tapaa neljän 13-ketjun graafista voidaan valita aligraafi, joka on kokoelma ketjuja (nämä aliketjujen pituudet vastaavat sitä tyyppiä millainen yhdiste A’ista muodostuu). Tässä joukot A vastaavat graafin sivuja ja se että joukko on yhdisteessä mukana vastaa sitä, että sivu on aligraafissa mukana.

Saadaan seuraavat tulokset:

r P(väh. r pituinen värisuora) approks
2 686898/1194505 0.575
3 1074209/16723070 0.0642
4 151/30940 0.00488
5 407/1454180 0.000280
6 361/33446140 0.0000108
7 1/4778020 2.093e-7

Javascript-koodi:

function binCoeff(n, k) {
    if (k < 0 || k > n) return 0;
    if (k === 0 || k === n) return 1;
    let ret = 1;
    for (let i=0; i<Math.min(k, n-k); i++){
        ret = ret*(n-i)/(i+1);
    }
    return ret;
}

function* generCombinations(arr, r) {
    const result = [];
    result.length = r;
    function* makeThem(len, start) {
        if(len===0) {
            yield result.slice();
        } else {
            for (var i=start; i<=arr.length-len; i++) {
                result[result.length-len] = arr[i];
                yield* makeThem(len-1, i+1);
            }
        }
    }
    yield* makeThem(r, 0);
}

function linkBruteGeneral(j, k, m, linkLen) {
    let ret = {};
    let runStarts = [];
    for (let i=0; i<k; i++) {
        runStarts = [...runStarts,
...new Array(m-(linkLen-1)).fill(null).map((_,z)=>[z, i])];
    }
    for (let comb of generCombinations(runStarts, j)) {
        let cardSet = new Set();
        for (let card of comb) {
            for (let follow=0; follow<linkLen; follow++) {
                cardSet.add((card[0]+follow)+","+card[1]);
            }
        }
        let key = cardSet.size;
        if (!(key in ret)) ret[key] = 0;
        ret[key] += 1;
    }
    return ret;
}

function calcProb(ds) {
    const calcPart = (j) => {
        let s = 0;
        let d = ds[j];
        for (let k in d) {
            if (k>7) continue;
            s += d[k]*binCoeff(52-k, 7-k);
        }
        return s;
    };
    
    let ret = 0;
    for (let i=1; i<=ds.length; i++) {
        ret += (i%2?1:-1)*calcPart(i);
    }
    return ret;
}

function makeTheFormula(ds) {
    const makePart = (j) => {
        let f = "(";
        let d = ds[j];
        let isFirst = true;
        for (let k in d) {
            if (k>7) continue;
            if (isFirst) {
                isFirst = false;
            } else {
                f += "+";
            }
            f += d[k]+`*binomial(${52-k}, ${7-k})`;
        }
        return f+")";
    };
    
    let ret = "";
    for (let i=1; i<=ds.length; i++) {
        ret += (i===1?'':(i%2?'+':'-')) + makePart(i);
    }
    return ret;
}

let testK = 4;
let testM = 13;
let testR = 3;

let maxNeedJ = 7-testR+1;

let ds = [];
for (let j=0; j<=maxNeedJ; j++) {
    ds.push(linkBruteGeneral(j, testK, testM, testR));
}

console.log(calcProb(ds));
console.log(makeTheFormula(ds));

Koodi toiselle tavalle tapauksessa r=2:

/** list of partitions of n to at most maxPartsN parts that are at most maxSize */
function getPartitions(n, maxPartsN, maxSize) {
    if (n===0) return [[]];
    let canMakeMax = maxPartsN*maxSize;
    if (n>canMakeMax) return [];
    if (n===canMakeMax) return [new Array(maxPartsN).fill(maxSize)];
    let ret = [];
    for (let x=Math.min(n, maxSize); x>=0; x--) {
        let toConcat = getPartitions(n-x, maxPartsN-1, x).map(p=>[x].concat(p));
        ret = ret.concat(toConcat);
    }
    return ret
}

function factorial(n) {
    let ret = 1;
    for (let i=2; i<=n; i++) ret *= i;
    return ret;
}

function binCoeff(n, k) {
    if (k < 0 || k > n) return 0;
    if (k === 0 || k === n) return 1;
    let ret = 1;
    for (let i=0; i<Math.min(k, n-k); i++){
        ret = ret*(n-i)/(i+1);
    }
    return ret;
}

/** In how many ways  can subchains be fitted into chains.
* Chain length is the number of edges in it.
*/
const linkageMemo = {};
function countLinkages(chains, subchains) {
    //debugger;
    let memoKey = chains.join(",")+";"+subchains.join(",");
    if (memoKey in linkageMemo) return linkageMemo[memoKey];
    if (subchains.length===0) return 1;
    let s = 0;
    let currSub = subchains[0];
    let restSubs = subchains.slice(1);
    for (let cI=0; cI<chains.length; cI++) {
        let cLen = chains[cI];
        let maxInd = cLen-currSub;
        for (let ind=0; ind<=maxInd; ind++) {
            let restChains = chains.slice(0, cI).concat(chains.slice(cI+1));
            if (ind>1) restChains.push(ind-1);
            if (ind<maxInd-1) restChains.push(maxInd-ind-1);
            restChains.sort((a,b)=>b-a);
            s += countLinkages(restChains, restSubs);
        }
    }
    linkageMemo[memoKey] = s;
    return s;
}


function permuFactor(arr) {
    let counts = {};
    for (let x of arr) {
        if (!(x in counts)) counts[x] = 0;
        counts[x] += 1;
    }
    let ret = 1;
    for (let val of Object.values(counts)) ret *= factorial(val);
    return ret;
}

function countAllLinkages(j, k, m) {
    let chains = new Array(k).fill(m-1);
    let linksN = k*(m-1);
    let partis = getPartitions(j, linksN, linksN);
    let ret = {};
    for (let parti of partis) {
        let key = parti.reduce((a,b)=>a+b+1,0);
        if (!(key in ret)) ret[key] = 0;
        ret[key] += countLinkages(chains, parti)/permuFactor(parti);
    }
    return ret;
}


/* Given the amounts of linkages calculate the numerator of probability of having a 2-run
* ds = [
    {
      "0": 1
     },
     {
      "2": 48
     },
     {
      "3": 44,
      "4": 1084
     },
     {
      "4": 40,
      "5": 1944,
      "6": 15312
     }, ...
]
*/
function calcProb(ds) {
    const calcPart = (j) => {
        let s = 0;
        let d = ds[j];
        for (let k in d) {
            if (k>7) continue;
            s += d[k]*binCoeff(52-k, 7-k);
        }
        return s;
    };
    
    let ret = 0;
    for (let i=1; i<=6; i++) {
        ret += (i%2?1:-1)*calcPart(i);
    }
    return ret;
}

function makeTheFormula(ds) {
    const makePart = (j) => {
        let f = "(";
        let d = ds[j];
        let isFirst = true;
        for (let k in d) {
            if (k>7) continue;
            if (isFirst) {
                isFirst = false;
            } else {
                f += "+";
            }
            f += d[k]+`*binomial(${52-k}, ${7-k})`;
        }
        return f+")";
    };
    
    let ret = "";
    for (let i=1; i<=6; i++) {
        ret += (i===1?'':(i%2?'+':'-')) + makePart(i);
    }
    return ret;
}


let testK = 4;
let testM = 13;
let ds = [];
for (let j=0; j<=6; j++) {
    ds.push((countAllLinkages(j, testK, testM)));
}

console.log(makeTheFormula(ds));
console.log(calcProb(ds));

\begin{aligned} \end{aligned}

Vastaa

Täytä tietosi alle tai klikkaa kuvaketta kirjautuaksesi sisään:

WordPress.com-logo

Olet kommentoimassa WordPress.com -tilin nimissä. Log Out /  Muuta )

Google photo

Olet kommentoimassa Google -tilin nimissä. Log Out /  Muuta )

Twitter-kuva

Olet kommentoimassa Twitter -tilin nimissä. Log Out /  Muuta )

Facebook-kuva

Olet kommentoimassa Facebook -tilin nimissä. Log Out /  Muuta )

Muodostetaan yhteyttä palveluun %s