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}$

Värisuorien todennäköisyyksistä

Saadaan seuraavat tulokset:

Javascript-koodi:

Koodi toiselle tavalle tapauksessa r=2:

Julkaissut membolic

Jätä kommentti Peruuta vastaus

Saadaan seuraavat tulokset:

Javascript-koodi:

Koodi toiselle tavalle tapauksessa r=2:

Jaa:

Aiheeseen liittyy

Julkaissut membolic

Jätä kommentti Peruuta vastaus