Head or Tail?

20 May, 2024

Let's start from a small poll: I saw Jim getting 10 consecutive heads when tossing a coin, what is the probability that Jim get another head on his 11th toss? I tried this on some of my colleagues and students, most people responses $\frac{1}{2}$ , stating that the 11th toss is independent from the previous ones.

A more cautious response might be: "well, we don't really know if the coin is fair or not, do we?" Given the previous 10 heads, one can hardly say that the coin is fair.

A Biased Coin

Instinctively, we would say that the coin is biased. However, to what extent? To simplify the situation, let's say that there is a possibility of $p$ that Jim's coin has two heads.

From a Bayesian perspective, at the beginning, of course, we would assume that $p ≪ 1$ . But after 10 heads, we need to update that belief.

Let $A$ be the event that Jim's coin is biased, then $P (A) = p$ . Additionally, denote the event that 10 heads are obtained in 10 tosses as $B$ . Obviously,

P (B | A) = 1, P (B | \bar{A}) = \frac{1}{2^{10}} .

Applying Bayesian Theorem:

p^{\ *} = P (A | B) = \frac{p}{P (B | A) p + P (B | \bar{A}) (1 - p)} = \frac{1024 p}{1023 p + 1} .

Therefore, the possibility of getting an eleventh head is

P = p^{\ *} + \frac{1}{2} (1 - p^{\ *}) .

This value is very close to 1 even if $p$ is small. When $p = 1 %$ , an eleventh head would has probability $95.6 %$ .

A Lucky Observer

However, there is another argument: maybe I was just being lucky to see the 10 streak of heads. This argument is pretty valid as nothing's being said about the tosses other than the 10 I witnessed.

A general question would be: "What is the probability of getting $r$ continuous heads in $n$ throws of a coin biased with probability $p$ of getting a head?" This is a study of "runs".

Formally, define a run of length $r$ as $r$ consecutive favorable out comes in a series of trials. Our question can be stated as the probability of $r$ -run in $n$ trials.

If we denote $S_{n}$ the probability of getting at least one $r$ -run in $n$ trials, obviously

S_{n} = \sum_{k = 1}^{n} s_{k},

where $s_{k}$ is the probability that the first $r$ -run occurs at the $k$ th trial. Additionally, we know that $s_{k} = 0$ if $k < r$ and $s_{r} = p^{r}$ where $p$ is the probability of achieving a head.

Comparing to $S_{n}$ , the recursive relationship of $s_{k}$ is much easier to find:

s_{n} = q s_{n - 1} + p q s_{n - 2} + \dots + p^{r - 1} q s_{n - r}, n > r .

Recursive models are best solved using generating function:

s_{n} t^{n} = \frac{q}{p} \sum_{k = 1}^{r} (p t)^{k} s_{n - k} t^{n - k} .

Sum the above up, $n$ running from $r + 1$ to infinity, as $n - k \geq 1$ for all $n$ and $k$ .

g (t) - s_{r} t^{r} = \frac{q}{p} \sum_{k = 1}^{r} (p t)^{k} g (t) .

Notice that $r + 1 - k \leq r$ for all $k$ . As a result, we have

g (t) = \frac{p^{r} t^{r} (1 - p t)}{1 - t + (1 - p) p^{r} t^{r + 1}} .

As $S_{n} = \sum_{k = 1}^{n} s_{k}$ , the generating function of $S_{n}$ has form $G (t) = \frac{g (t)}{1 - t}$ , finally we have

G (t) = \frac{p^{r} t^{r} (1 - p t)}{(1 - t) (1 - t + (1 - p) p^{r} t^{r + 1})} .

The result, I quote from Simpson (1740)¹

S_{n} = \sum_{j = 1} (- 1)^{j + 1} [p + \frac{n - j r + 1}{j} q] (\binom{n - j r}{j - 1}) p^{j r} q^{j - 1} .

For any fixed $r$ , it is obvious that ${lim}_{n \to \infty} S_{n} = 1$ . One might as well argue that Jim's coin may not be biased, I am only selecting the 10 most "heady" tosses. Well, that would require around 1,500 tosses to make sure there is 50% possibility of the existence of a 10-run.

Simpson, T. (1 740). The Nature and Laws of Chance. The Whole after a new, general, and conspicuous Manner, and illustrated with a great Variety of Examples. Cave, London.↩

View original

#hs-maths