The situation is that we toss a coin N times. We note the outcome of each flip and we find the distribution of how many times the coin flipped the 'same way' n times in a row, for n = 1,2,3 etc (for N throws of ~ 1000 we wouldn't really go further than n = 12). i.e we count how many times the coin flips the same way (heads or tails) just once in a row (..T.. or ..H..), how many times it flips twice in a row (..TT.. or ..HH..), three times etc and then graph the frequency.

This distribution will be an exponential distribution, with a basic graph shown below (I have repeated the full experiement with N = 1000, 10 times and graphed the respective frequency for all 10 runs). This is fairly easy to think about as there should be roughly twice as many instances of (n-1) as n, because for every time we get the same outcome n-1 times in a row there is then a 50% chance of getting the same again.

enter image description here

My first question is, can someone actually analytically derive this distribution, rather than it currently just being my loose intuition?

Secondly, how would you then conduct a hypthesis test, for a sample of size N, in order to guage whether the set of produced heads and tails (or 0s and 1s, obviously doesn't really matter) were produced completely independantly and with a constant probability of 0.5?

It's obviously easy to check the final total number of heads and tails or 0s and 1s in order to hypothesis-test the probability value p (binomial distribution) but I need to figure out a way of hypothesis testing that the distribution of congruent outcomes, of degree n, fits the null hypothesis that all samples/coin flips were completely independant and probability remained constant at p.

Standard Chi square testing shouldn't work, unless I'm mistaken, as if we take the Xn to be the number of runs of degree n (for each value of n) then this is not a normally distributed variable.

Thanks in advance...

  • $\begingroup$ This is called a runs test. Knuth has an extensive discussion in The Art of Computer Programming Vol. II. $\endgroup$
    – whuber
    Commented Sep 10, 2022 at 15:42

1 Answer 1


Your intuition about the limit distribution of the longest consecutive streak of heads is correct.

There is a theorem, proved by Antónia Földes in "The limit distribution of the length of the longest head-run" (1979), that states:

Suppose, $\tau(n)$ is the largest streak of heads among $n$ independent throws of an unbiased coin. Then $\frac{\tau(n)}{2^{n + 1}}$ converges in distribution to $Exp(1)$ (or equivalently $\lim_{n \to \infty} P(\frac{\tau(n)}{2^{n + 1}} < x) = 1 - e^{-x}$ for all $x \in [0; +\infty)$)

  • $\begingroup$ ahhh interesting, that's really helpful, thanks! $\endgroup$
    – Sam White
    Commented Sep 10, 2022 at 16:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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