Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let's say a series of 10 bits is output randomly. Now lets do that 256 times. I'd like to find out what the expected number of streaks of 1s or 0s are for each of the possible sizes 1-10.

For example, the stream 0111001011 has 3 1-bit streaks, 2 2-bit streaks, and 1 3-bit streak. Note that even though the 3-bit streak has two 2-bit streaks in it, those are not counted, as the 3-bit streak removes them from consideration. Note that the sumproduct of the streak counts and the streak lengths = (3 * 1)+(2 * 2)+(1 * 3) = 10 (the number of bits), and that should always work.

So, given 256 of these random 10-bit streams, how many 1-bit, 2-bit, 3-bit, 4-bit... 10-bit streaks can I expect? Fractional values are fine, as I'm sure the # of 10-bit streaks is less than 1. I'd really appreciate knowing HOW this is done, as my integrals don't seem to be accomplishing it.

Thanks!

share|improve this question
    
I think this kind of problem (usually described as the length of a run of heads or tails in the flipping of a fair coin) can be found in various textbooks - possibly something like this in Grimmett and Stirzaker? –  Yemon Choi Nov 27 '09 at 4:42
    
Well, I know I could brute force this, but I'm looking for true formulae. My integrals don't seem to work. –  The Count Nov 27 '09 at 5:21
add comment

2 Answers

up vote 2 down vote accepted

I'm going to call your "streams" "strings" instead, because "streams" looks too much like "streaks" to me. This becomes a much easier problem if we translate it into an enumeration problem. Since each of the 210 possible bit strings occur with equal probability, it suffices to count the total number of streaks of length k in all these strings (and then as Kristal says just divide by 210 for the expected value per string). Let S(k,n) be the number of k-streaks in all strings of length n. For k = 1 we can make a straightforward recursion:

$S(1,n) = 2S(1,n-1) + 2^{n-1} - 2^{n-2} = 2S(1,n-1) + 2^{n-2}$

since for every n string, we have two copies of every (n-1)-string as a prefix (with their associated 1-streaks), plus half the time we add a new 1-streak at the end (if the bit we add at the end is different from the old last bit). Sometimes, though, we break a 1-streak at the end; this happens if our previous last bit was a 1-stream, so it happens once for each possible n-2 string as a prefix. (Note that this means the recursion requires n > 2!).

This recursion is easy to solve; we have S(1,2) = 4 from which it follows $S(1,n) = (n+2)2^{n-2}$.

Now there's a bijection between (k-1)-streaks in (n-1)-strings and k-streaks in n-strings (just add / remove another bit to the streak), so S(k-1,n-1) = S(k,n). We conclude

$S(k,n) = (n-k+3)2^{n-k-1}$

for k < n, and S(n,n) = 2. For n=10, we have the sequence

3072, 1408, 640, 288, 128, 56, 24, 10, 4, 2

for streaks of length 1, 2, 3, ..., 10 out of the 210 = 1024 possible strings, so dividing through should give the expected number in a random string.

The sequence S(1,n) is not in Sloane, but the total number of streaks in all n-strings $\sum_{k=1}^n S(k,n)$ is - this sequence starts 2, 6, 16, 40, 96, 224,... and has general form $\sum_{k=1}^n (n-k+3)2^{n-k-1} = (n+1)2^{n-1}$.

This sequence A057711 apparently has quite a few combinatorial interpretations.

share|improve this answer
    
I've performed the brute-force with a simple program and determined your numbers are correct for S(k,n)... thanks much! –  The Count Nov 28 '09 at 4:19
    
I was wondering why the numbers didn't seem to add up to anything, but looking again, the sum of k * S(k,n) is 10240, which is the total number of bits tested, which conforms to my problem statement... nice! –  The Count Nov 28 '09 at 4:23
    
Thanks very much for this. If you'd like to see how I used it: discreteideas.com/2009/11/streaking-surprise –  The Count Nov 28 '09 at 4:48
add comment

As for how to do it I think you can get a linear recurrence equal equation for the number of possible coin tosses without 10 heads in a row for n greater than or equal to 11. It is a_{n}=2*(a_{n-1})-2*(a_{n-10}) (if the last 10 tosses are one zero followed by 9 ones or one one followed by nine zeros) you must pick a bit to avoid 10 ones or zeros in a row otherwise the choice is arbitrary). Then it is a matter of solving the characteristic equation finding a general solution and then finding the particular solution that matches the boundary values. Then with an expression for the number of sequences of coin tosses without 10 a row for a particular n it is a matter of dividing by 2^n to get the probability of not having 10 in a row for n tosses.

share|improve this answer
    
-1, please use the , and . keys... –  Reid Barton Nov 27 '09 at 18:55
    
I broke it into smaller sentences. –  Kristal Cantwell Nov 27 '09 at 19:05
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.