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!



Chances of streaks in small bit-streams
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](http://www.research.att.com/~njas/sequences/A057711) apparently has quite a few combinatorial interpretations.


