Bit Strings with Even Numbers; Coin TossDate: 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/ |
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/