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).
Best Answer
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.
So the expected number of consecutive 0's is calculated as:
$$(m-1) (\frac{m-2} {m})^n $$