# How to calculate the expected value of number of two consecutive zeros in a randomly-generated binary string?

There is a bitmap which has m bits. Initially, all m bits are zeros. There are n random number generators which can generate random integers between 1 and m uniformly. Usually, n is larger than m.

All these n random number generators are independent. After each generator generates one integer (which means we get n random integers), we set the bits corresponding to these random integers to one (For example, if the random integers are 1, 3, 6, 3..., then we set the 1th, 3rd, 6th... bit to one; it is possible that different random number generators generate same integer, in that case, the corresponding bit will still be one).

My question is how to calculate the expected value of number of two consecutive zeros? For example, the bitmap is 10010100011, then the number of two consecutive zeros is 3 (sub-string “000” contains 2 two consecutive zeros).

• "expected value of number of two consecutive zeros" is confusing. Should it be: "expected length of the longest run of consecutive zeros"? – leonbloy Oct 1 '13 at 17:22
• No, it is right. The answer is $3$ because in $00$ and $000$ there are $3$ "two consecutives zeros". – ILikeMath Oct 1 '13 at 17:23

You can look at any two adjacent bits as an independent Bernoulli experiment, so you have m-1 experiments, the chance of two consecutive bits not being "hit" by a 1 is $\frac{m-2} {m}$ for a single random number, and $(\frac{m-2} {m})^n$ for m random numbers, as they are generated independently. if they are not hit, we can count them as consecutive 0's.
$$(m-1) (\frac{m-2} {m})^n$$
• I think its wrong. The random numbers are independent, good, but the "two consecutive bits" experiment is not. What about $000$? We can not deal te two overlapping experiments like independent. Therefore the Bernoulli distribution does not apply here. – ILikeMath Oct 1 '13 at 18:32