1
$\begingroup$

Suppose n bits are arranged circularly with given condition that random k of them are 1 and rest 0, and all possible d consecutive bits (total n possibilities) are looked at, what is the probability to see at least m nonzero bits in at least one of these n possibilities of d consecutive bits.

$\endgroup$

1 Answer 1

2
$\begingroup$

It depends on the range of $k$. The method to handle this is similar to http://arxiv.org/pdf/0707.3888.pdf which in your language treats the case $k$ random and binomial(n,1/2), and in http://arxiv.org/pdf/1204.1149.pdf, which generalizes to binomial(n,p_n) for more general $p_n$.

$\endgroup$
2
  • $\begingroup$ k is not random but given. I mean I intend to get the joint or conditional distribution with k. $\endgroup$
    – Abhijit
    Nov 1, 2013 at 2:22
  • $\begingroup$ As I wrote in my answer: the method is the same as in the papers I quoted, at least if k is a fraction of n or if it goes to zero with n as in the second reference (fluctuations in k will not destroy the method, which uses Chen-Stein). You can also easily de-randomize by starting with the random case, noting the monotonicity in $k$ and using an a-priori estimate on the fluctuations of $k$ when it is random. $\endgroup$ Nov 1, 2013 at 5:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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