Associated Topics || Dr. Math Home || Search Dr. Math

### 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?

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.

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.

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/
```
Associated Topics:
College Probability
High School Probability
High School Sequences, Series

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search