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.
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\ll 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,\quad 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{1024p}{1023p+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\%\).
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=qs_{n-1}+pqs_{n-2}+\cdots+p^{r-1}qs_{n-r},\quad n>r. \] Recursive models are best solved using generating function: \[ s_nt^{n}=\frac{q}{p}\sum_{k=1}^r(pt)^ks_{n-k}t^{n-k}. \] Sum the above up, \(n\) running from \(r+1\) to infinity, as \(n-k\ge1\) for all \(n\) and \(k\). \[ g(t)-s_rt^r=\frac{q}{p}\sum_{k=1}^r(pt)^kg(t). \] Notice that \(r+1-k\le r\) for all \(k\). As a result, we have \[ g(t)=\frac{p^rt^r(1-pt)}{1-t+(1-p)p^{r}t^{r+1}}. \] As \(S_n=\sum_{k=1}^ns_k\), the generating function of \(S_n\) has form \(G(t)=\frac{g(t)}{1-t}\), finally we have \[ G(t)=\frac{p^rt^r(1-pt)}{(1-t)(1-t+(1-p)p^{r}t^{r+1})}. \] The result, I quote from Simpson (1740)1 \[ S_n=\sum_{j=1}(-1)^{j+1}\left[p+\frac{n-jr+1}{j}q\right]\binom{n-jr}{j-1}p^{jr}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.↩︎