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.
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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$.
answered Oct 30, 2013 at 2:54
-
$\begingroup$ k is not random but given. I mean I intend to get the joint or conditional distribution with k. $\endgroup$– AbhijitCommented 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$ Commented Nov 1, 2013 at 5:14