How to formulate the distribution and conduct a hypothesis test on the following situation?

Question

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.

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...

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)$)