5
$\begingroup$

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. Basically, I need that same result as above, calculated on paper.

A pattern in the results obviously exists, but I just cant figure out a formula. Anyone, help please?

$\endgroup$
6
  • $\begingroup$ 1/4 1/8 1/16 .... $\endgroup$ Feb 1, 2011 at 2:39
  • $\begingroup$ so... you're saying you don't see any consistent relationship between the amounts at the various lengths? $\endgroup$
    – John
    Feb 1, 2011 at 2:44
  • $\begingroup$ each one is 1/2 of the one before and 1/2 + 1/4 +1/8 ... =1 $\endgroup$ Feb 1, 2011 at 2:45
  • $\begingroup$ 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. $\endgroup$
    – Davor
    Feb 1, 2011 at 3:57
  • $\begingroup$ @Davor, this might give you some ideas. $\endgroup$
    – mpiktas
    Feb 1, 2011 at 8:11

2 Answers 2

4
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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$

$\endgroup$
3
  • $\begingroup$ @user2376, shouldn't $P(Y_i=1)$ be $P(X_{i-1}=0,X_{i}=1,X_{i-1}=0)$? $\endgroup$
    – mpiktas
    Feb 2, 2011 at 13:08
  • $\begingroup$ @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)$) $\endgroup$
    – petem
    Feb 2, 2011 at 15:51
  • $\begingroup$ There must be typos in this answer, because (for instance) when $p=1/3$ the formula gives $E(N)=1/3 + (n-1)(1-1/3)/(1/3) = 2n-5/3,$ which is far too large. $\endgroup$
    – whuber
    Sep 5, 2020 at 16:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.