How do I calculate the nth-highest die, out of a collection of m identical dice?

155 Views Asked by At

Say we have a die $D$ which is not necessarily fair. When we throw $m$ such dice and drop the $(n - 1)$ highest dice, what is the probability mass function of the highest remaining die?


Here's what I have so far. First the formalism.

$$ D^m_n $$

is the result of the n-th highest die (the highest remaining after dropping the $(n-1)$ highest ones) out of $m$ dice, all with an identical probability-distributions. Then

$$ P(D^m_n = x) $$

is the probability that the n-th highest die rolled the value $x$. My approach is that

$$ P(D^m_n = x) = \binom{m}1 P(D = x) \cdot \binom{m-1}{n-1}P(D \gt x)^{n-1} \cdot \binom{m-n}{m-n} P(D \lt x)^{m-n} $$

but this is missing the cases where multiple dice rolled the value $x$. For example the result $(5, 5, 5, 5)$ of $D^4 $ (all four dice rolled the value $5$) would count for $D^4_1 = 5, D^4_2 = 5, D^4_3 = 5,$ and $D^4_4 = 5$

1

There are 1 best solutions below

2
On BEST ANSWER

You want what’s known as an order statistic.


This assumes $D$ is a 6-sided fair die .

It is easier to compute $P\left(D_n^{m}\geq x\right)$. We get:

$$P(D_{n}^m \geq x)= \frac{1}{6^m}\sum_{k=n}^{m} \binom{m}{k} (x-1)^{m-k}(7-x)^k$$

Here, $k$ is the exact number of dice with results $\geq x.$

This sum is known to not have a nice formula, as it is related to:

$$\sum_{k=n}^m\binom{m}{k} u^{m-k}(1-u)^k$$

which is the right part of the binomial expansion of $(u+(1-u))^m.$

Define $q_{m,k}(y)=y^{m-k}(6-y)^k.$

Then you get:

$$\begin{align}P(D_{n}^m = x)&=P(D_{n}^m \geq x)-P(D_{n}^m \geq x+1)\\&=\frac{1}{6^m}\sum_{k=n}^{m}\binom{m}{k}\left[q_{m,k}(x-1)-q_{m,k}(x)\right] \end{align}$$

I don't think that can be much simplified.

We also get the expected value:

$$E(D_{n}^{m})=\frac{1}{6^m}\sum_{k=n}^{m} \binom{m}{k}\sum_{y=0}^{5} q_{m,k}(y)$$


Or in general, for independent identical dice $D$, you get:

$$P(D_n^m\geq x)=\sum_{k=n}^{m}\binom{m}{k}P(D<x)^{m-k}P(D\geq x)^k.$$

If $u=P(D\ge x)$ this is exactly $\sum_{k=n}^{m}\binom{m}k(1-u)^{m-k}u^k,$ which is the probability of getting at least $n$ heads out of $m$ coins each with a probability of $u$ of getting heads.

Then you get, given that

$$P(D_n^m = x)= P(D_n^m \ge x) - P(D_n^m \ge x+1)$$

and setting $f_{m,k}(x)=(1-x)^{m-k}x^{k}$:

$$P(D_n^m= x)=\sum_{k=n}^m\binom{m}{k}\left(f_{m,k}(P(D\ge x))-f_{m,k}(P(D\ge x+1))\right)$$