Expected length of the longest streak of heads, when the coin is being tossed until $n$ tails

expected valuemaxima-minimaprobability

Suppose we tossed a coin with probability of tails $p$ until we got $n$-th tails. What is the expected length of the longest consecutive string on heads under this condition?

Let’s denote the length of the streak of heads, that is exactly before $i$-th tails as $X_i$. It is not hard to see, that all $X_i$ are i.i.d. and are distributed geometrically with parameter $p$. Thus our question can be reworded in the following way:

Suppose $X_1, … , X_n$ are i.i.d. random variables, geometrically distributed with parameter $p$. What is $E[\max(X_1, … , X_n)]$?

If the exact answer is too complicated, then asymptotic is also OK.

Best Answer

Let's work with the reworded version of your problem and let $Y = \max(X_1, \ldots, X_n).$ For discrete random variables having range $\{0,1,\ldots\}$ we have $\mathbb{E}[Y] = \sum_{y=0}^{\infty} \mathbb{P}(Y>y).$ We have the chain of equalities:

$$ \mathbb{P}(Y>y) = 1- \mathbb{P}(Y \leq y) = 1- \mathbb{P}(X_1\leq y, \ldots, X_n \leq y) = 1 - \mathbb{P}(X_1 \leq y)^n$$

and $\mathbb{P}(X_1 \leq y) = 1 - \mathbb{P}(X_1 > y) = 1 - (1-p)^y,$ so

$$ \mathbb{E}[Y] = \sum_{y=0}^{\infty} \left( 1 - (1-(1-p)^y)^n \right) =\sum_{y=0}^{\infty} \sum_{k=1}^n (-1)^{k+1} \binom{n}{k} (1-p)^{yk} $$ $$= \sum_{k=1}^n (-1)^{k+1} \binom{n}{k} \cdot \frac{1}{1-(1-p)^k}$$

Related Solutions

[Math] Asymptotics for the expected length of the longest streak of heads.

Suppose, $p \in (0; 1)$ is the probability of a single coin rolling heads. Let's call $L_n$ the length of the longest streak of heads in first $n$ rolls, $T_n$ - the number of rolls before the $n$-th tails and $X_i$ the length of the streak of heads just before the $i$-th tails. It is not hard to see, that $X_i$ are i.i.d. geometrically distributed with parameter $(1-p)$, that $T_n$ are almost surely monotonously increasing, and that $T_n = n + \sum_{i = 1}^n X_i \geq n$. We also know that $L_{T_n} = \frac{\ln(n)}{\ln(p^{-1})}+O(1)$. Thus we have:

$$ \begin{align*} \lim_{n \to \infty} \frac{E[L_n]}{\ln(n)}&=\lim_{n \to \infty} E\left[\frac{L_n}{\ln(n)}\right]\\ &= \lim_{n \to \infty} E\left[\frac{L_{T_n}}{\ln(T_n)}\right]\\ &= \lim_{n \to \infty} E\left[\frac{L_{T_n}}{\ln(n + \sum_{i = 1}^n X_i)}\right]\\ &=\lim_{n \to \infty} E\left[\frac{L_{T_n}}{\ln(n) + \ln\bigl(1 + \frac{\sum_{i = 1}^n X_i}{n}\bigr)}\right]\\ &= \lim_{n \to \infty} E\left[\frac{L_{T_n}}{\ln(n) + \ln(1 + E[X_1])}\right]\\ &= \lim_{n \to \infty} \frac{E[L_{T_n}]}{\ln(n) + \ln(1 + p^{-1})}\\ &= \lim_{n \to \infty} \frac{\frac{\ln(n)}{\ln(p^{-1})}+O(1)}{\ln(n) + \ln(1 + p^{-1})}\\ &= \frac{1}{\ln(p^{-1})}. \end{align*} $$

From that we can conclude, that $\forall p \in (0; 1)$, $E[L_n]$ is asymptotically equivalent to $\frac{\ln(n)}{\ln(p^{-1})}$, which seems to be the thing you wanted to prove.

[Math] Assess if coin is fair based on length of longest run

The natural test for a fair coin would be to compare the numbers of Heads and Tails, unless you wanted to include independent identical distributions in the null hypothesis as well (which you might if you did not conduct the test)

But you have said you want to look at the longest run

$6$ is rather short for the longest run in $1000$ tosses of a fair coin which is i.i.d. equally probably heads or tails. Since an i.i.d. unfair coin would tend to give longer runs, the doubt here could be that $6$ might come from a non-i.i.d process, possibly an attempt to fake a random sequence

You might intuitively guess that the longest run could be of the order of $\log_2(n)$ so about $10$ in this case ($10$ is indeed the median and mode here, and slightly below the expectation).

There are explicit expressions but it may be quicker to use a Markov calculation, producing something like the following, which suggests that at over $95\%$ confidence you might reject the null hypothesis when seeing longest runs of $7$ or fewer or of $16$ or more from a sequence of $1000$ results

run     prob
 6      0.0003
 7      0.0180
 8      0.1208
 9      0.2370
10      0.2387
11      0.1699
12      0.1014
13      0.0553
14      0.0289
15      0.0147
16      0.0074
17      0.0037
18      0.0019
19      0.0009
20      0.0005
21      0.0002
22      0.0001

Best Answer

Related Solutions

[Math] Asymptotics for the expected length of the longest streak of heads.

[Math] Assess if coin is fair based on length of longest run

Related Question