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

### Fibonacci and Incoming Bits

```
Date: 09/08/99 at 00:28:27
From: Suja
Subject: Probability

Consider a transmitter sending 100 bits of random data over an ideal
communication channel. I need to look for three consecutive ones. What
is the probability that I will get the pattern at least once?

I Got: There are 98 possible combinations of getting three consecutive
ones. Therefore the probability of getting three consecutive ones at
least once is (1-(1-p)^98)) where p = 1/8.

What is the probability of getting either three consecutive ones or
three consecutive zeros in those 100 bits?

Thank you,
Vsuja
```

```
Date: 09/08/99 at 06:26:55
From: Doctor Pat
Subject: Re: Probability

Vsuja,

What a beautiful problem! Thank you for sending it. I had no idea what
the solution might be when I first read your problem (although I
figured your answer was wrong, as it assumes that each set of three is
independent of the others, and of course they are not. But I surely
never expected to find our old friend Fibonacci hiding in the
woodshed, so to speak...

Let's take the second problem first, "What is the probability of
getting either three consecutive ones or three consecutive zeros in
those 100 bits?" Here is one way to find the solution.

Imagine as you are watching the data that you are keeping track of how
close to three in a row you are. You can be in only one of three
possible states. If three in a row has never happened, then this bit
is either different from the last (you now have one in a row) or the
same as the last (you now have two in a row.) If this one is like the
two previous, you are in state three, and stop the game (if it has
happened once it doesn't matter if there is another three in a row
later).

Now when the first bit comes in it puts you in state 1 (1 in a row).
When bit 2 comes in there is a .5 chance it will put you in state 2,
and a .5 chance you will be back in state 1. When bit 3 comes in, the
probability that you move to state 3 is .5 times the probability you
are in state 2 (.5), so after three bits the probability is 1/4 that
you have found one.

On any incoming bit then, the probability we will move to state 3 on
the turn n is .5 times the probability that we were in state 2 on the
turn (n-1). The probability you are in state 2 after that bit is
.5*(1 - probability you were in state 1 the previous turn).

If this is hard to see, it is because in each turn, the probability
that you go back to state 1 is .5 times the probability you were in
state 1 already + .5 times the probability you were in state 2 and
didn't get a third similar bit. 1-P(state 3) = P(state 1) +
P(state 2).

Here is a chart of the probabilities that you are in different places
after the first few bits. Notice that in state 3 you add the
probability you have been there already plus the probability of
getting there on that turn. It is called the absorbing state.

bit #     P(state 1)     P(state 2)     P(state 3)
1            1              0              0
2           1/2            1/2             0
3           1/2            1/4            1/4
4           3/8            1/4            3/8
5           5/16           3/16           1/2
6           1/4            5/32          19/32

Let's call Px(y) the probability of being in state x after bit y (so
P1(6) = 1/4)

From the above we see that:

P3(n) = (1/2)*P2(n-1) + P3(n-1)
P1(n) = (1/2)*(1 - P3(n-1))
P2(n) = 1 - P3(n) - P1(n)

and substituting we get:

P3(n) = 1/4 + (1/4)*P3(n-2) + (1/2)*P3(n-1)

and the probability of being in state 3 depends on the probability you
were there in the last two moves. Streamlining our notation, the
probability of being in state 3 after n moves, P(n) is given by the
relation:

P(1) = 0;  P(2) = 0;  and P(n) = 1/4 + (1/4)*P(n-2) + (1/2)*P(n-1)

And for a real treat, examine the value of 1 - P(n) for each value by
writing the numerator over 2^(n-1); you get

1/1, 2/2, 3/4, 5/8, 8/16, 13/32, ...

the sequence in the numerator is 1, 2, 3, 5, 8, 13, ...

We can use similar logic to solve the initial problem, "What is the
probability that I will get three consecutive ones at least once?",
but it will be a bit more difficult. After each bit, you can be in one
of 4 states (instead of just 3.) You can have no 1's in a row, one 1
in a row, two 1's in a row or three 1's in a row. If this bit makes
three in a row, you stop the game.

Now when the first bit comes in, there is a .5 chance that it puts you
in state 0 (no ones in a row), and a .5 chance it puts you in state 1
(1 in a row.)

When bit 2 comes in, the probability that you move to state 2 is .5
times the probability you are in state 1 (.5), so after 2 bits the
probability is 1/4 that you are in state 2. Similarly, the probability
that you move to state 1 is .5 times the probability you are in state
0 (.5), so after 2 bits the probability is 1/4 that you are in state
1. If the incoming bit is a zero, you will be in state 0, so after 2
bits the probability is 1/2 that you are in state 0.

When bit 3 comes in, the probability that you move to state 3 is .5
times the probability you are in state 1 (1/4), so after 3 bits the
probability is 1/8 that you are in state 3. The probability that you
move to state 2 is .5 times the probability you are in state 1 (1/2),
so after 3 bits the probability is 1/4 that you are in state 2.
Similarly, the probability that you move to state 1 is .5 times the
probability you are in state 0 (1/2), so after 3 bits the probability
is 1/4 that you are in state 1. If the incoming bit is a zero, you
will be in state 0, so after two bits the probability is 1/2 that you
are in state 0.

On any incoming bit then, the probability we will move to state 3 on
the turn n is .5 times the probability that we were in state 2 on turn
(n-1). The probability you are in state 2 after that bit is .5 times
the probability that we were in state 1 on turn (n-1). And the
probability you are in state 1 after that bit is .5 times the
probability that we were in state 0 on turn (n-1). And the probability
you are in state 0 after that bit is 1 - P(3) - (P2) - P(1). Here is a
chart of the probabilities that you are in different places after the
first few bits. Notice that in state 3 you add the probability you
have been there already plus the probability of getting there on that
turn.

bit #     P(state 0)     P(state 1)     P(state 2)     P(state 3)
1           1/2            1/2             0              0
2           2/4            1/4            1/4             0
3           4/8            2/8            1/8            1/8
4           7/16           4/16           2/16           3/16
5          13/32           7/32           4/32           8/32
6          24/64          13/64           7/64          20/64

Let's call Px(y) the probability of being in state x after bit y (so
P1(6) = 13/64)

From the above we see that:

P1(n) = (1/2)*P0(n-1)   .....................................[1]
P2(n) = (1/2)*P1(n-1)   .....................................[2]
P3(n) = P3(n-1) + (1/2)*P2(n-1)   ...........................[3]
P0(n) = 1 - P3(n) - P2(n) - P1(n)   .........................[4]

Solving P3(n) in terms of P3(n-1), P3(n-2) and P3(n-1) is not so
straightforward. First, we'll substitute equation [2] into equation
[3], then equation [1] into the resulting equation, and equation [4]
into that:

P3(n) = P3(n-1) + (1/2)*P2(n-1)

= P3(n-1) + (1/2)*[(1/2)*P1(n-2)]

= P3(n-1) + (1/4)*P1(n-2)

= P3(n-1) + (1/4)*[(1/2)*P0(n-3)]

= P3(n-1) + (1/8)*P0(n-3)

= P3(n-1) + (1/8)*[1 - P3(n-3) - P2(n-3) - P1(n-3)]

= P3(n-1) + 1/8 - (1/8)*P3(n-3) - (1/8)*P2(n-3)
- (1/8)*P1(n-3)   ...[5]

Next, we'll need to solve equation [3] for P2(n-1) and equation [2]
for P1(n-1):

P3(n) = P3(n-1) + (1/2)*P2(n-1), so
P2(n-1) = 2*P3(n) - 2*P3(n-1)   .............................[6]

P2(n) = (1/2)*P1(n-1), so
P1(n-1) = 2*P2(n)   .........................................[7]

Then substituting these into equation [5] we get:

P3(n) = P3(n-1) + 1/8 - (1/8)*P3(n-3) - (1/8)*P2(n-3)
- (1/8)*P1(n-3)

= P3(n-1) + 1/8 - (1/8)*P3(n-3)
- (1/8)*[2*P3(n-2) - 2*P3(n-3)] - (1/8)*[2*P2(n-2)]

= P3(n-1) + 1/8 - (1/8)*P3(n-3) - (1/4)*P3(n-2)
+ (1/4)*P3(n-3) - (1/4)*P2(n-2)

= P3(n-1) + 1/8 + (1/8)*P3(n-3) - (1/4)*P3(n-2)
- (1/4)*P2(n-2)

= P3(n-1) + 1/8 + (1/8)*P3(n-3) - (1/4)*P3(n-2)
- (1/4)*[2*P3(n-1) - 2*P3(n-2)]

= P3(n-1) + 1/8 + (1/8)*P3(n-3) - (1/4)*P3(n-2)
- (1/2)*P3(n-1) + (1/2)*P3(n-2)

= 1/8 + (1/8)*P3(n-3) + (1/4)*P3(n-2) + (1/2)*P3(n-1)

and the probability of being in state 3 depends on the probability you
were there in the last three moves. Streamlining our notation, the
probability of being in state 3 after n moves, P(n) is given by the
relation:

P(0) = 0, P(1) = 0, P(2) = 0, and
P(n) = 1/8 + (1/8)*P(n-3) + (1/4)*P(n-2) + (1/2)*P(n-1)

If we examine the value of 1-P(n) for each value by writing the
numerator over 2^(n-1), we get

1/1, 2/2, 4/4, 7/8, 13/16, 24/32, ...

the sequence in the numerator is

1, 2, 4, 7, 13, 24, ...

these are also the numerators of the fractions for P0(n), P1(n) and
P2(n) in the generating table. This sequence is related to the
Fibonacci sequence, but here, every element is the sum of the previous
THREE elements. AWESOME!

I hope all that is clear. Good luck.

- Doctors Pat and TWE, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
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