Expected number of runs of length n in coin toss

Question

I'm writing a program for an assignment for my Probability and Statistics course. This program performs several millions of simulated coin tosses, and then analyses various properties of the generated sequence.

One of the things it does is count how many runs does the generated sequence contain, and their lengths. One result for 10.000.000 tosses is:

Number of runs of length 1 is: 2500986
Number of runs of length 2 is: 1246647
Number of runs of length 3 is: 625656
Number of runs of length 4 is: 311689
Number of runs of length 5 is: 156673
Number of runs of length 6 is: 78464
Number of runs of length 7 is: 39253
Number of runs of length 8 is: 19547
Number of runs of length 9 is: 9866
Number of runs of length 10 or more is: 9818

Now, my problem is following: I need to compare the result acquired by simulation to theoretical expectation of sorts (my English ain't that good, I hope you understand what I mean). Basically, i need that same result as above, calculated on paper. I've spent over a week trying to figure this out, and I'm getting desperate, as my deadline is approaching, and I have no idea how to solve this.

Pattern in the results obviously exists, but I just cant figure out a formula. Anyone, help please? :D

Answer 1

You can simply use the geometric distribution, which gives you the probability of a given number of Bernouilli trials before a success or in these case before the series is broken. The distribution is given as follow :

P = (1-p)^(k) * p

with p = .5 for a fair coin and k = 1 : 9

The idea is to compute the joint probability of k consecutive head/tail and one tail/head :

P{tail, tail,..., head} = P{tail}^k * P{head}.

Then you multiply this probability by 10^7 the number of trials in your simulation.

The results are the following :

1. 2,500,000
2. 1,250,000
3. 625,000
4. 312,500
5. 156,250
6. etc.

which are quite close of your simulated results...

For the case of a run of length 10 or more, you have to do 1-(others prob, including k=0) which gives 9765.625.

You can compute these probabilities easily in R with P <- dgeom(1:9, prob=.5) and for P(10) : P <- 1- sum(dgeom(0:9, prob=.5))

Answer 2

You have n independent Bernoulli rv, $X_1, X_2, ..., X_n$ with $P(X_i=1)=P(X_i=0)=p=1/2$. You generate n bits $b_1, b_2, ..., b_n$, as observations on this sequence. Let N be the rv giving the number of runs of one, for example, in the simulated sequence of bits. $N=\sum_{i=1}^n Y_i$, where $Y_i$ is the random variable that takes 1 as value if $b_i$ is the starting bit of a run of ones and 0 otherwise. $E(Y_1)=P(Y_1=1)=p$ while for $i=2,...,n$ $P(Y_i=1)=P(X_{i-1}=0, X_i=1)=(1-p)p.$ Hence the expected value of N, is $E(N)=p+(n-1)(1-p)/p$