Probabillity - rolling a dice 20 times, probability of a result gets only once

Question

A dice is rolled $20$ times, with the possible results $\left\{1,2,3,4,5,6\right\}$.

Let $X$ be the number of results, out of the possible 6, which were chosen only once during the 20 rolls.

Calculate $P\left\{X\right\}$

I find it hard to identify the kind of variable it is. It isn't bio nominal nor hyper geometric.

I understand I have to choose 4 rolls out of the 20, and the combination between them is $4!$, giving me -

$$ \frac{\binom{20}{4} \times \binom{6}{4} \times 4!}{6^{20}} $$

For the chosen "results", the chosen "rolls' and the inner combination between them. But how about the other "rolls"? Something is missing here.

Answer 1

Observe that since there are $20$ rolls, $P(X=6)=0$. So we need only check the probabilities that $X=1,2,3,4,5$. These can be done on a case by case basis.

For $X=5$, the probability is $$\frac{\binom{6}{5}\cdot\binom{20}{5}\cdot 5!}{6^{20}}$$ since we must choose the the $5$ results which will occur only once, and choose which rolls they occur on in $\binom{20}{5}$ ways, accounting for their orderings.

For $X=4$, the probability is $$\frac{\binom{6}{4}\cdot\binom{20}{4}\cdot 4!\cdot (2^{16}-30)}{6^{20}}$$ since we must choose the $4$ results which will occur only once, choose which rolls they occur on, order these $4$ results (in $4!$ ways), and then fill in the remaining $16$ rolls with the other two results. We must be a bit careful here, since we need each of the other results to occur at least twice, or not at all. Denote the remaining results by $x$ and $y$. Since there are $16$ rolls to fill in with $x'$s and $y$'s, there are $2^{16}$ possible outcomes. $15$ of them consist of $15 x'$s and one $y$, and another $15$ consist of $15 y$'s and one $x$. Discarding these $30$ undesirable outcomes leaves $2^{16}-30$.

The argument is similar for the other cases, but the last bit corresponding to the results that don't appear exactly once gets a bit more complicated. For $X=3$, we have have $17$ rolls that must be filled with, say, $x,y,z$ such that neither $x,y,$ nor $z$ appears exactly once. There are $17\cdot 2^{16}$ ways for $x,y,$ or $z$ to appear once (place it in one of $17$ positions then fill the other $16$ rolls with the other two results). And there are $\binom{17}{2}$ ways for two of them to appear only once. Since these are double-counted above, there are $3(17\cdot 2^{16}-\binom{17}{2})$ undesirable cases to discard.

I'll leave the cases $X=1,2$ up to you to compute. For now I'll just denote by $C_{4},C_{5}$ the number of ways to arrange the remaining results without any of them appearing exactly once. Therefore

$$P(X=3)=\frac{\binom{6}{3}\cdot\binom{20}{3}\cdot 3!\cdot [3(17\cdot 2^{16}-\binom{17}{2})]}{6^{20}}$$

$$P(X=2)=\frac{\binom{6}{2}\cdot\binom{20}{2}\cdot 2!\cdot (4^{18}-C_{4})}{6^{20}}$$ $$P(X=1)=\frac{\binom{6}{1}\cdot\binom{20}{1}\cdot (5^{16}-C_{5})}{6^{20}}$$

For completeness, observe that (clearly) $P(X<1)=P(X>6)=0$.

Answer 2

It isn't bio nominal nor hyper geometric.

Why would it be anything with a nice name?

I understand I have to choose 4 rolls out of the 20

I have no idea where this came from, but it is wrong.

---

To actually answer your question, we'll first find a (reverse) cumulative density function for $P$, then calculate the actual values from that.

So, what's the probability that $X$ is at least $k$ (for $1 \leq k \leq 5$? That means that there are at least $k$ elements of $\{1,2,3,4,5,6\}$ (with $\left(\array{6\\k}\right)$ choices) that don't come up, and $k$ of our rolls take the appropriate values, one at a time ($\left(\array{20\\k}\right)k!$ possibilities), while the other $20-k$ take values the remaining $6 - k$ possible values ($(6-k)^{20-k}$ possibilities).

Our numbers $N(X=k)$ of possibilities for $X$ to take a value no smaller than each $k$ is therefore given by:

\begin{array}{c|c|c}X&N(X\geq k)&N(X\geq k)\mbox{ simplified}\\\hline \\0&6^{20}&6^{20} \\1&\left(\array{6\\1}\right)1!\left(\array{20\\1}\right)(6-1)^{20-1}&24(5)^{20} \\2&\left(\array{6\\2}\right)2!\left(\array{20\\2}\right)(6-2)^{20-2}&1425(4)^{19} \\3&\left(\array{6\\3}\right)3!\left(\array{20\\3}\right)(6-3)^{20-3}&15200(3)^{19} \\4&\left(\array{6\\4}\right)4!\left(\array{20\\4}\right)(6-4)^{20-4}&218025(2)^{19} \\5&\left(\array{6\\5}\right)5!\left(\array{20\\5}\right)(6-5)^{20-5}&11162880 \\6&0&0\end{array}

The actual counts for each value of $X$ are then given by the differences between these: $N(X = k) = N(X \geq k) - N(X \geq k+1)$:

\begin{array}{c|c|c}X&N(X= k)&N(X=k)\mbox{ evaluated}\\\hline \\0&6^{20}-24(5)^{20}&1367340080687976 \\1&24(5)^{20}-1425(4)^{19}&1897117341979800 \\2&1425(4)^{19}-15200(3)^{19}&374034643096800 \\3&15200(3)^{19}-218025(2)^{19}&17552066407200 \\4&218025(2)^{19}-11162880&114296728320 \\5&11162880&11162880 \\6&0&0\end{array}

And our probabilities are, therefore, given by dividing these by $6^{20}$:

\begin{array}{c|c|c|c}X&P(X= k)&P(X=k)\mbox{ evaluated}&\mbox{approx.}\\\hline \\0&1-24\left(\frac{5}{6}\right)^{20}&\frac{56972503361999}{152339935002624}&0.37398 \\1&24\left(\frac{5}{6}\right)^{20}-1425\left(\frac{2}{3}\right)^{19}&\frac{79046555915825}{152339935002624}&0.51888 \\2&1425\left(\frac{2}{3}\right)^{19}-15200\left(\frac{1}{2}\right)^{19}&\frac{3896194198925}{38084983750656}&0.10230 \\3&15200\left(\frac{1}{2}\right)^{19}-218025\left(\frac{1}{3}\right)^{19}&\frac{20314891675}{4231664861184}&0.0048007 \\4&218025\left(\frac{1}{3}\right)^{19}-\frac{11162880}{6^20}&\frac{5511995}{176319369216}&0.000031261 \\5&\frac{11162880}{6^{20}}&\frac{1615}{528958107648}&0.0000000030532\end{array}

Answer 3

It is not difficult to provide a complete answer to thise question. With a die having $N$ sides and being rolled $M$ times we get the marked combinatorial class

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \textsc{SEQ}_{=N}(\textsc{SET}_{=0}(\mathcal{Z}) +\mathcal{U} \times \textsc{SET}_{=1}(\mathcal{Z}) +\textsc{SET}_{\ge 2}(\mathcal{Z})).$$

We thus get the mixed generating function

$$G(z, u) = (\exp(z)-z + uz)^N = (\exp(z)+(u-1)z)^N.$$

We then get for the probability

$$\mathrm{P}[X=k] = \frac{1}{N^M} \sum_{q=0}^N M! [z^M] [u^k] (\exp(z) + (u-1) z )^N \\ = \frac{M!}{N^M} [z^M] \sum_{q=0}^N {N\choose q} [u^k] (u-1)^q z^q \exp((N-q)z) \\ = \frac{M!}{N^M} \sum_{q=0}^N {N\choose q} {q\choose k} (-1)^{q-k} [z^{M-q}] \exp((N-q)z) \\ = \frac{M!}{N^M} \sum_{q=0}^{\min(N,M)} {N\choose q} {q\choose k} (-1)^{q-k} \frac{(N-q)^{M-q}}{(M-q)!}.$$

Now

$${N\choose q} {q\choose k} = \frac{N!}{(N-q)! \times k! \times (q-k)!} = {N\choose k} {N-k\choose N-q}$$

so we finally get for the probability

$$\bbox[5px,border:2px solid #00A000]{ \mathrm{P}[X=k] = \frac{M!}{N^M} {N\choose k} \sum_{q=0}^{\min(N,M)} {N-k\choose N-q} (-1)^{q-k} \frac{(N-q)^{M-q}}{(M-q)!}.}$$

This yields e.g. for a four-sided die and seven rolls the PGF

$${\frac {799}{4096}}+{\frac {1701\,u}{4096}} +{\frac {693\,{u}^{2}}{2048}}+{\frac {105\,{u}^{3}}{2048}}.$$

A regular die with six sides and ten rolls produces

$${\frac {409703}{5038848}}+{\frac {1356025\,u}{5038848}} +{\frac {12275\,{u}^{2}}{34992}}+{\frac {8075\,{u}^{3}}{34992}} \\ +{\frac {2275\,{u}^{4}}{34992}}+{\frac {35\,{u}^{5}}{11664}}.$$

In particular, six sides and twenty rolls will produce

$${\frac {72562042521379}{152339935002624}} +{\frac {2404256592175\,u}{5642219814912}} +{\frac {3535287814775\,{u}^{2}}{38084983750656}} \\ +{\frac {2213124275\,{u}^{3}}{470184984576}} +{\frac {16529525\,{u}^{4}}{528958107648}} +{\frac {1615\,{u}^{5}}{528958107648}}.$$

As a sanity check we get for five values appearing once where the sixth must fill the remaining slots the probability:

$${6\choose 5} {20\choose 5} 5! \times \frac{1}{6^{20}} = \frac{1615}{528958107648}$$

and the check goes through.

We can also compute the expectation, either by differentiating the PGF or alternatively by

$$\frac{1}{N^M} M! [z^M] \left. \frac{\partial}{\partial u} G(z, u) \right|_{u=1} \\ = \frac{1}{N^M} M! [z^M] \left. N (\exp(z)-z+uz)^{N-1} z \right|_{u=1} \\ = \frac{1}{N^{M-1}} M! [z^{M-1}] \exp((N-1)z) = \frac{1}{N^{M-1}} M! \frac{1}{(M-1)!} (N-1)^{M-1}.$$

This is

$$\bbox[5px,border:2px solid #00A000]{ \mathrm{E}[X] = M \times \left(1-\frac{1}{N}\right)^{M-1}.}$$

This also follows by linearity of expectation. We get for the probability of a particular face appearing once

$${M\choose 1} \times \frac{1}{N} \left(1-\frac{1}{N}\right)^{M-1}.$$

Sum over $N$ to get the expectation.

The above results were verified with the following Maple routines.

with(combinat);

ENUMPGFX :=
proc(N, M)
    option remember;
    local res, part, psize, mset, adm;

    res := 0;

    part := firstpart(M);

    while type(part, `list`) do
        psize := nops(part);
        mset := convert(part, `multiset`);

        adm :=
        nops(select(ent -> ent = 1, part));

        res := res + u^adm * binomial(N, psize) *
        M!/mul(p!, p in part) *
        psize!/mul(p[2]!, p in mset);

        part := nextpart(part);
    od;

    res/N^M;
end;

PGF := (N, M) ->
M!/N^M*add(u^k*binomial(N,k)*
           add(binomial(N-k, N-q)*(-1)^(q-k)*
               (N-q)^(M-q)/(M-q)!, q=0..min(N,M)),
           k=0..N);

ENUMEX := (N, M) -> subs(u=1, diff(ENUMPGFX(N, M), u));
PGFEX := (N, M) -> subs(u=1, diff(PGF(N, M), u));

EX := (N, M) -> M*(1-1/N)^(M-1);