 suigeneris
Topic Author
Posts: 7
Joined: January 5th, 2015, 8:35 pm

### Coin flip grouping

This was one question in a pre-interview test. I got about 95% of the way to an analytic solution.Flip an unfair coin N = 10 times. p(heads) = 0.6. (p is irrelevant for the 5%.) You might get:HHHTHTHHTHDefine a group as consecutive flips leading to the same side. (HHH)(T)(H)(T)(HH)(T)(H) has N_group = 7.What is the probability that N_group >= 6? What is the probability that N_group >= 55 given N = 100? wileysw
Posts: 593
Joined: December 9th, 2006, 6:13 pm

### Coin flip grouping

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. suigeneris
Topic Author
Posts: 7
Joined: January 5th, 2015, 8:35 pm

### Coin flip grouping

Fantastic, thanks! Your solution does fill the gap. I didn't think about solving the problem by first examining the case of a fair coin; I started by listing all combinations and counting. (As a consequence I did not get the coefficient in brackets.) ExSan
Posts: 4582
Joined: April 12th, 2003, 10:40 am

### Coin flip grouping

more in Coursera: Unpredictable? Randomness, Chance and Free WillThere is plenty explanation on Coin Flip  