Can You Win The Possession?

Riddler Express

With The Riddler nearing its end here at FiveThirtyEight, I can finally get something off my chest: Starting a competition with the flip of a coin (say, to determine possession of a ball) is so boring!

Instead, let’s give the captain of one team a fair coin and the captain of the other team a fair die. The captain with the coin will flip it at the same time the other captain rolls the die. They continue doing this until the coin is the same (whether heads or tails) for three consecutive flips or the number that comes face-up on the die is the same for two consecutive rolls.

On average, how many coin flips will it take to get three in a row? And how many die rolls will it take to get two in a row?

Extra credit: While the numbers of flips and rolls may often be the same, which team — the team with the coin or the team with the die — is more likely to win the toss/roll? (That is, which is more likely to happen sooner?)

Solution

I. Coin Flips

1. Single Probability

For number of flips $f$, the probability $P_F(f)$ of achieving three consecutive flips at the end is shown in the table below:

$f$ $P_F(f)$ Sequences
1 0 NA
2 0 NA
3 $\dfrac{2}{8}$ $HHH$, $TTT$
4 $\dfrac{2}{16}$ $HTTT$, $THHH$

For $f = 5$, note that:

  1. Appending two consecutive flips opposite of the first flip to the sequences in $f = 3$ yields $TTHHH$ and $HHTTT$.
  2. Appending a flip opposite of the first flip to the sequences in $f = 4$ yields $HTHHH$ and $THTTT$.

This guarantees that before the final sequence of three, all subsequences with a maximum of two heads or two tails in the earlier flips are included.

Thus, for $f \ge 5$,

$$P_F(f) = \dfrac{1}{4}\cdot P_F(f-2) + \dfrac{1}{2}\cdot P_F(f-1)$$


Since this is a Fibonnaci sequence of sorts, it can also be expressed as:

$P_F(f) = \dfrac{2\cdot F(f-2)}{2^f} = \dfrac{F(f-2)}{2^{f-1}}$

where $F(n)$ is the $n^{th}$ Fibonacci number.

2. Cumulative Probability

Looking at some cumulative probability $C_F(f)$ values:

$f$ $P_F(f)$ $C_F(f)$
1 0 0
2 0 0
3 $\dfrac{2}{8}$ $\dfrac{2}{8}$
4 $\dfrac{2}{16}$ $\dfrac{6}{16}$
5 $\dfrac{4}{32}$ $\dfrac{16}{32}$
6 $\dfrac{6}{64}$ $\dfrac{38}{64}$

The numerators, $0,0,2,6,16,38$, seem to be double that of A008466. Induction will confirm that $C_F(f) = 1 - \dfrac{F(f+1)}{2^{n-1}}$.

True for f = 3.

$$C_F(3) = 1 - \dfrac{F(4)}{2^{2}} = 1 - \dfrac{3}{4} = \dfrac{2}{8}$$

Assume for f = k.

$$C_F(k) = 1 - \dfrac{F(k+1)}{2^{k-1}}$$

Evaluation of f = k+1.

$$C_F(k+1) = C_F(k) + P_F(k+1)$$


$$ = 1 - \dfrac{F(k+1)}{2^{k-1}} + \dfrac{F((k+1)-2)}{2^{(k+1)-1}}$$
$$ = 1 - \dfrac{2\cdot F(k+1)}{2^k} + \dfrac{F(k-1)}{2^k}$$
$$ = 1 - \dfrac{1}{2^k}\cdot\big(F(k+1) + F(k+1) - F(k-1)\big)$$
$$ = 1 - \dfrac{1}{2^k}\cdot\bigg(F(k+1) + \big(F(k) + F(k-1)\big) - F(k-1)\bigg)$$
$$ = 1 - \dfrac{1}{2^k}\cdot(F(k+1) + (F(k))$$
$$ = 1 - \dfrac{F(k+2)}{2^k} = 1 - \dfrac{F((k+1)+1)}{2^{(k+1)-1}}$$
Therefore,

$C_F(f) = 1 - \dfrac{F(f+1)}{2^{n-1}}$

3. Average Number of Flips

The following Markov Chain represents achieving a coin being the same for three consecutive flips.


The average number of flips to get three consecutive can be calculated as:
$$EV_F = 1\cdot\dfrac{1}{2}\cdot\dfrac{1}{2}\cdot 3 + \dfrac{1}{2}\cdot(1 + EV_F) + \dfrac{1}{4}\cdot(2 + EV_F)$$
$$EV_F = \dfrac{3}{4} + \dfrac{1}{2}+ \dfrac{1}{2}EV_F + \dfrac{1}{2} + \dfrac{1}{4}EV_F$$
$$\dfrac{1}{4}EV_F = \dfrac{7}{4}$$

$EV_F = 7$

II. Dice Rolls

1. Single Probability

The first roll can be any number. The last roll must match the roll before it. If there are any rolls between the first and last roll, they must be different than the previous roll.
$$\dfrac{6}{6} \cdot \left(\dfrac{5}{6}\right)^{r-2} \cdot \dfrac{1}{6} = \dfrac{5^{r-2}}{6^{r-1}}$$
For number of rolls $r$, the probability $P_R(r)$ can be represented as:

$P_R(r) = \Biggr[ \begin{array}{c} \hspace{0.4cm}0\hspace{0.4cm}, \hspace{0.2cm}r = 0 \\ \hspace{0.4cm}0\hspace{0.4cm}, \hspace{0.2cm}r = 1 \\ \dfrac{5^{r-2}}{6^{r-1}}, \hspace{0.2cm}r \ge 2 \end{array}$

2. Cumulative Probability

$$0 + 0 + \dfrac{1}{6} + \dfrac{5}{36} + \cdots + \dfrac{5^{r-2}}{6^r}$$


$$= \sum_{k = 0}^{r-2} \dfrac{5^k}{6^{k+1}}$$
$$= \dfrac{1}{6}\cdot\sum_{k = 0}^{r-2} \left(\dfrac{5}{6}\right)^k$$
Using the sum of a geometric sequence,
$$=\dfrac{1}{6}\cdot\dfrac{1 - \left(\dfrac{5}{6}\right)^{r-1}}{1 - \dfrac{5}{6}}$$
$$=1 - \left(\dfrac{5}{6}\right)^{r-1}$$
For number of rolls $r$, the cumulative probability $C_R(r)$ can be represented as:

$C_R(r) = \Biggr[ \begin{array}{c} \hspace{1.1cm} 0 \hspace{1cm}, \hspace{0.2cm}r = 0 \\ 1 - \left(\dfrac{5}{6}\right)^{r-1}, \hspace{0.2cm}r \ge 1 \end{array}$

3. Average Number of Rolls

The average number of rolls to get two is:
$$EV_R = 1\cdot0 + 2\cdot0 + 3\cdot\dfrac{1}{6} + 4\cdot\dfrac{5}{36} + \cdots$$
$$ = \dfrac{1}{6}\cdot\left(3 \cdot \sum_{k = 0}^{\infty} \left(\dfrac{5}{6}\right)^k + \sum_{k = 1}^{\infty} \left(\dfrac{5}{6}\right)^k + \sum_{k = 2}^{\infty} \left(\dfrac{5}{6}\right)^k + \cdots \right)$$
$$ = \dfrac{1}{6}\cdot\left(3 \cdot \dfrac{1}{1-\dfrac{5}{6}} + \dfrac{\dfrac{5}{6}}{1-\dfrac{5}{6}} + \dfrac{\dfrac{25}{36}}{1-\dfrac{5}{6}} + \cdots \right)$$
$$ = 1 + 1 + 1 + \dfrac{5}{6} + \dfrac{25}{36} + \cdots$$
$$ = 1 + 1 + \sum_{k = 0}^{\infty} \left(\dfrac{5}{6}\right)^k$$
$$ = 2 + \dfrac{1}{1-\dfrac{5}{6}} = 2+6$$

$EV_R = 8$

Answer

On average, it will take 7 coin flips to get three in a row and 8 dice rolls to get two in a row.

Extra Credit.

I interpreted this in two ways, hence I calculated individual and cumulative probabilities for both above.

For individual :

  1. Coin Tosses have a higher probability for $3 \le$ rolls/flips $\le 10$.
  2. Dice Rolls have a higher probability for rolls/flips $= 2$ or rolls/flips $\ge 11$.

For cumulative :

  1. Coin Tosses have a higher probability for $6 \le$ rolls/flips.
  2. Dice Rolls have a higher probability for $1 \le$ rolls/flips $\le 5$.

Rohan Lewis

2023.06.19

Code can be found here.