2
$\begingroup$

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).

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

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 $$

$\endgroup$
  • $\begingroup$ So the m in your answer should be the number of random number generators (which is n in my question), right? $\endgroup$ – Lipeng Wan Oct 1 '13 at 18:26
  • $\begingroup$ 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. $\endgroup$ – ILikeMath Oct 1 '13 at 18:32
  • $\begingroup$ @LipengWan yes, i swapped n and m by mistake (in the entire answer), I fixed it. $\endgroup$ – Ron Teller Oct 1 '13 at 18:51
  • $\begingroup$ @DiegoHuerfano we're talking about the expected (mean) result, in this context they can be evaluated independently. $\endgroup$ – Ron Teller Oct 1 '13 at 18:54
  • $\begingroup$ @Ron Teller I'm not sure whether your answer is correct or not, but I did some simulation and the result fits your answer well. Any other comments on this answer? $\endgroup$ – Lipeng Wan Oct 1 '13 at 19:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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