Expected number of runs of length n in coin toss

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

-
 1/4 1/8 1/16 .... – dave fournier Feb 1 '11 at 2:39 so... you're saying you don't see any consistent relationship between the amounts at the various lengths? – John Feb 1 '11 at 2:44 each one is 1/2 of the one before and 1/2 + 1/4 +1/8 ... =1 – dave fournier Feb 1 '11 at 2:45 Well yes, that is why I said that the pattern is obvious. But I need a formula, preferably with an explanation as to WHY each one is 1/2 of the one before, and how do I get the first value. I need to calculate this independently of the simulation, and then compare these two results. Don't get me wrong, I'm not looking for someone to solve my homework for me, I just don't know what to do anymore. – Davor Feb 1 '11 at 3:57 @Davor, this might give you some ideas. – mpiktas Feb 1 '11 at 8:11
show 1 more comment

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 :

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

-

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$

-
 @user2376, shouldn't $P(Y_i=1)$ be $P(X_{i-1}=0,X_{i}=1,X_{i-1}=0)$? – mpiktas Feb 2 '11 at 13:08 @mpiktas If $b_i$ is the first bit in a run of ones, why should be $b_{i+1}=0$? ( I think you intended to write $(Y_i=1)=(X_{i-1}=0, X_i=1, X_{i+1}=0)$) – mathinpython Feb 2 '11 at 15:51