January 19th, 2015, 3:34 pm
suigeneris,this might qualify as an analytic solution but might or might not fill the 5%:the fair coin case (p=1/2) is simple, as the probability of any sequence is same: 1/2^N. to count the number of configurations given there are k groups (1<=k<=N), we count how the k-1 group-dividers (between a group of H and a group of T) fit in the N-1 gaps between the flips. this results the binomial distribution:[$]\displaystyle\frac{1}{2^N}2{N-1\choose k-1},[$]where the factor of 2 represents that the sequence can start with H or T. the case of N=10 and k>=6 is simply 0.5 due to the symmetry, while for N=100 and k>=55, one gets 0.5 - [ (99 choose 50) + ... + (99 choose 53) ] / 2^99 ~ 0.5 - 4/sqrt(pi*99) ~ 0.2 (where we have approximated the central binomial coefficient C(n,m)/2^n with m~n/2 by 1/sqrt(pi*n), essentially Stirling's formula).for an unfair coin, we would need to count the finer structures, i.e., when the flips result i heads, N-i tails and in k groups. this is straightforward, as we can only have ceiling(k/2) groups of heads and floor(k/2) groups of tails (or the other way around), then we interlace them. applying the same argument in the fair coin case but to heads and tails separately, we have the following distribution given any k:[$]\displaystyle \sum_{i=j}^{N-j}p^i(1-p)^{N-i}\left[{i-1\choose k-j-1}{N-i-1\choose j-1}+{N-i-1\choose k-j-1}{i-1\choose j-1}\right],[$]where j=floor(k/2), so k-j=ceiling(k/2). this gives the desired probability in a form of finite sum. when N becomes large, one can apply similar asymptotic analysis, but the expression seems quite messy...
Last edited by
wileysw on January 28th, 2015, 11:00 pm, edited 1 time in total.