Fibonacci and Incoming BitsDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/