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?

Eagerly awaiting your reply

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/