3
$\begingroup$

Consider the following game: $n$ participants have a fair coin each, on a given round, the not already discarded participants flip their coins, those who flip a tail are discarded from the game, the remaining ones continue to play until there are at most $k$ of them left.

The question is: what's the distribution of the number of rounds in this game?

Bonus question: idem, but the $n$ coins are all unfair, with probabilities $p_1$, $p_2$, $\ldots$, $p_n$.


Disclaimer: this is not a homework question, it came up when considering distributed routing protocols with a colleague.

$\endgroup$
6
  • 1
    $\begingroup$ The game may not terminate. It should terminate when there are less than $k$ participants left. $\endgroup$ – Rodrigo de Azevedo May 21 '16 at 15:59
  • $\begingroup$ Indeed, I'll edit to take that into account. Anyway, it may still not terminate (with very small probability). $\endgroup$ – mpr May 21 '16 at 16:02
  • 1
    $\begingroup$ There's no such thing as the distribution of the expected number. Do you want the distribution or the expected number? $\endgroup$ – joriki May 21 '16 at 16:07
  • $\begingroup$ I'm sorry, I'm just waking up. I'd like to know the distribution. Will edit :) $\endgroup$ – mpr May 21 '16 at 16:10
  • $\begingroup$ Is this some collision resolution scheme on a shared channel? $\endgroup$ – Brian Tung Jul 28 '16 at 17:49
0
$\begingroup$

Each coin follows a Geometric Distribution $P(X_i=k)=p_i(1-p_i)^{k-1}$ because it has probability $1-p_i$ of showing a head on each of the $k-1$ tries, and then, it has probability $p_i$ of showing tail on the $k$th try.

Then, we are trying to find the distribution of $\max_iX_i$. We have that: $$P(\max_iX_i \leq k)=P(X_i\leq k \forall i)=\prod_iP(X_i \leq k)=\prod_i \sum_{j=1}^k p_i(1-p_i)^{j-1}=\prod_i p_i\frac{1-(1-p_i)^k}{1-(1-p_i)}=\prod_i (1-(1-p_i)^k)$$

Then, I have no good idea on how to continue that, if someone has one...

EDIT: My bad, I just saw that the game stops when less than $k$ players are left. So this is just for the case $k=1$...

$\endgroup$
0
$\begingroup$

The probability that a particular fair coin has not shown tails by the $m$th round is $\dfrac1{2^m}$

So the probability that $k$ or fewer out of $n$ have not shown tails by the $m$th round is $\displaystyle \sum_{j=0}^k {n \choose j} \dfrac{(2^m-1)^{n-j}}{2^{mj}}$

So the probability that the $m$th round is the first time that only $k$ or fewer out of $n$ have not shown tails is $\displaystyle \sum_{j=0}^k {n \choose j} \dfrac{(2^m-1)^{n-j}}{2^{mj}} - \sum_{j=0}^k {n \choose j} \dfrac{(2^{m-1}-1)^{n-j}}{2^{(m-1)j}}$

This is easy enough to calculate using R using

pbinom(k, n, 1/2^m) - pbinom(k, n, 1/2^(m-1))

and, for example with $n=10$ participants, it would give the following probabilities for varying $m$ and $k$ (so columns sum to $1$, subject to rounding)

     k     0     1     2     3     4     5     6     7     8     9    10
 m                 
 0       0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 1.000
 1       0.001 0.011 0.055 0.172 0.377 0.623 0.828 0.945 0.989 0.999 0.000 
 2       0.055 0.233 0.471 0.604 0.545 0.357 0.168 0.054 0.011 0.001 0.000
 3       0.207 0.395 0.355 0.197 0.074 0.019 0.003 0.000 0.000 0.000 0.000
 4       0.261 0.235 0.098 0.025 0.004 0.000 0.000 0.000 0.000 0.000 0.000
 5       0.204 0.089 0.018 0.002 0.000 0.000 0.000 0.000 0.000 0.000 0.000
 6       0.126 0.027 0.003 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000
 7       0.070 0.007 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000
 8       0.037 0.002 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000
 9       0.019 0.001 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000
10       0.010 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000
11       0.005 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000
12       0.002 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000
13       0.001 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000
14       0.001 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000
15       0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 

This could easily be extended to cases where the coins were consistently biased, but would become more complicated if they each had different biases

$\endgroup$
3
  • $\begingroup$ If I'm reading the table you gave correctly, it would seem to indicate that there's virtually no chance of having, eg, 10 coins and needing 4 flips to get 7 heads, is that right? It's quite surprising... $\endgroup$ – mpr Jul 29 '16 at 2:55
  • $\begingroup$ @mpr: An individual has a probability of $\frac{1}{8}$ of three heads so the probability of having $8$ or more out of $10$ with three heads is ${10 \choose 8}\frac{7^2}{8^{10}} + {10 \choose 9}\frac{7^1}{8^{10}} + {10 \choose 10}\frac{7^0}{8^{10}} \approx 0.0000021$. So yes, the probability that you need four or more rounds to get down to the first time there are $7$ or fewer players left is very small. $\endgroup$ – Henry Jul 29 '16 at 6:58
  • $\begingroup$ @Henry Shouldn't the probability that $k$ or fewer out of $n$ have not shown tails by the $m$th round be $\sum_{j=0}^k \binom{n}{j} \left(\frac{1}{2^m}\right)^{j} \left( 1 - \frac{1}{2^m} \right)^{n - j} = \sum_{j=0}^k \binom{n}{j} \frac{(2^m - 1)^{n -j}}{2^{mn}}$ ? $\endgroup$ – dazedviper Apr 14 '19 at 10:05
0
$\begingroup$

Partial approach. This is not a complete solution. I'm still thinking about it, but perhaps what I write down may suggest a completion for someone else.

We will be satisfied with arriving at a set of $z$-transforms

$$ P_n(z) = \sum_{m=0}^\infty P(\text{$m$ tosses required to get down to $k$ or less} \mid n) z^m $$

With this definition, we observe that for $n \leq k, P_n(z) = 1$, while for $n > k$,

\begin{align} P_n(z) & = \sum_{j=0}^n \binom{n}{j} \left(\frac{1}{2}\right)^n zP_j(z) \\ & = \frac{z}{2^n} \sum_{j=0}^n \binom{n}{j} P_j(z) \\ & = \frac{z}{2^n} \sum_{j=0}^{n-1} \binom{n}{j} P_j(z) + \frac{z}{2^n} P_n(z) \end{align}

Multiplying both sides by $2^n$, then subtracting $zP_n(z)$, we obtain

$$ \left(2^n-z\right)P_n(z) = z\sum_{j=0}^{n-1} \binom{n}{j} P_j(z) $$

or

$$ P_n(z) = \frac{z}{2^n-z} \sum_{j=0}^{n-1} \binom{n}{j} P_j(z) $$

Using our boundary condition, we can "simplify" this to

$$ P_n(z) = \frac{z}{2^n-z} \left[ \sum_{j=0}^k \binom{n}{j} + \sum_{j=k+1}^{n-1} \binom{n}{j} P_j(z) \right] $$

but I'm not sure this is the proper way to proceed.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.