Bit Strings with Even Numbers; Coin Toss

Date: 12/09/2001 at 14:23:06
From: Erin Enoch
Subject: Basics of counting/Probability

How many bit strings of length n have an even number of 1's?
How many bit strings of length n have 2 consecutive 1's?
Please explain.

A fair coin is tossed until 2 consecutive heads appear. What's the 
probability that this will happen within the first n tosses?

An explanation as to how to solve these will be appreciated.
Thanks.

Date: 12/10/2001 at 14:55:54
From: Doctor Anthony
Subject: Re: Basics of counting/Probability

>How many bit strings of length n have an even number of 1's

Every string has an even or odd number of 1's. There is no reason to 
bias the answer to more odd or more even strings and so there will be 
half all n bit strings having an odd number of 1's and half having an 
even number of 1's.

There are 2^n n-bit strings and so the number having an even number of 
1's is

     (1/2).2^n  =  2^(n-1)

>How many bit strings of length n have 2 consecutive 1's?

It is best to get a solution to the number of strings with no 
consecutive 1's and subtract this from 2^n.

To fix ideas I have considered a string of length 10 but the method is 
applicable to the general case of a string of length n.

I gave this answer earlier to someone whos asked about consecutive 
0's. To save changing all my 0's to 1's and vice versa, I have found 
the number of strings that don't contain consecutive 0's, but the 
reasoning is of course identical.

We need to find the number of strings that don't contain consecutive 
0's. Let u(n) be the number of strings of length n that DO NOT contain 
consecutive 0's. 

Let u(n0) = number of strings that start with 0
    u(n1) = number of strings that start with 1 

Then  u(n) = u(n0) + u(n1)

If the first number in the string is 1 then the string can be 
completed in u(n-1) ways. So u(n1) = u(n-1)

If the first number in the string is 0 then the second number must be 
1.  So u(n0) = u((n-1)1) 
             = u(n-2)

Therefore  u(n) = u(n0) + u(n1)  becomes

           u(n) = u(n-2) + u(n-1)

Note that this is the recurrence relation for the number of strings 
that DO NOT have consecutive 0's.  

This is the familiar recurrence relation for the Fibonacci series. We 
can either solve it as a difference equation or simply apply the 
difference equation up to n = 10. It will be quicker to do the latter 
since n is small.

We have u(1) = 2  (either 0 or 1)

  u(2) = 3 (one of 01, 10, 11)

    Then  u(3) = 2 + 3 = 5
          u(4) = 3 + 5 = 8
          u(5) = 5 + 8 = 13
          u(6) = 8 + 13 = 21
          u(7) = 13 + 21 = 34
          u(8) = 21 + 34 = 55
          u(9) = 34 + 55 = 89
          u(10) = 55 + 89 = 144

(This corresponds to F(12), the 12th Fibonacci number.)

So there are 144 binary strings that do not contain consecutive 0's.

The total number of possible strings = 2^10 = 1024, so the number of 
strings that do contain consective 0's is 

     =   1024 - 144 

     =   880  

In the general case of a string of length n the required number is

     2^n - F(n+2)   where F(n+2) is the (n+2)th Fibonacci number.  


>A fair coin is tossed until 2 consecutive heads appear. What's the 
>probability that this will happen within the first n tosses?

To fix ideas we shall find the probability that the first consecutive 
head occurs at the 10th toss. This means the sequence of 10 ends with 
HH.

In the first 8 tosses we could have 8 tails, 7 tails, ....., 4 tails 
but not fewer than 4 T's otherwise we would have HH somewhere in the 
sequence before the 9th and 10th toss. 

So the problem reduces to finding the number sequences of 8 T's and 
H's that end in a T and have no H's next to each other.

If there are say, 5 T's and 3 H's we place the 5 T's in a row as shown

    T    T    T    T    (T)    (We MUST end with a T)

   |   |    |    |    |        (5 gaps for single H's)

In this case we have to choose 3 gaps from the 5 available and this 
can be done in  C(5,3) = 10 ways.

We must then find the various possibilities with 4 up to 8 tails.  
After a few of these calculations the pattern will become clear.

  4 T's and 4 H's

     T    T    T     (T)     choose 4 gaps from 4 =  C(4,4)
   |    |    |    | 

  5 T's and 3 H's            choose 3 gaps from 5 =  C(5,3)

  6 T's and 2 H's            choose 2 gaps from 6 =  C(6,2)

  7 T's and 1 H              choose 1 gap from  7 =  C(7,1)

  8 T's and 0 H              choose 0 gap from  8 =  C(8,0) 

The total number of possible sequences is 2^10, so the probability of 
the first double H at the 10 toss is

C(4,4) + C(5,3) + C(6,2) + C(7,1) + C(8,0)      1 + 10 + 15 + 7 + 1
------------------------------------------  =  ---------------------
                   2^10                                2^10

                                              34         17
                                          = -------  =  ----
                                             1024       512

With n even, the general pattern is

     C((n-2)/2,(n-2)/2) + C(n/2,(n-4)/2) + ...... + C((n-2),0)
   = ----------------------------------------------------------
                              2^n

To find the pattern with n odd we can consider that the first double H 
occurs at the 9th toss. So 8th and 9th tosses are HH.

We consider what happens in the first 7 tosses. We could have 7 T's, 
6 T's ... 4 T's.

4 T's and 3 H's   

   T     T     T     (T)
 |    |      |     |        choose 3 gaps from 4  = C(4,3)

5 T's and 2 H's             choose 2 gaps from 5  = C(5,2)

6 T's and 1 H               choose 1 gap from  6  = C(6,1)

7 T's and 0 H               choose 0 gap from  7  = C(7,0) 

Required probability is

   C(4,3) + C(5,2) + C(6,1) + C(7,0)      4 + 10 + 6 + 1
 = ---------------------------------  =  ----------------
                 2^9                            2^9

                                          21
                                      = ------
                                         512

With n odd, the general pattern is

  C((n-1)/2,(n-3)/2) + C((n+1)/2,(n-5)/2) + ... + C(n-2,0)
= --------------------------------------------------------
                         2^n  

- Doctor Anthony, The Math Forum
  http://mathforum.org/dr.math/