Probability of seeing m nonzero bits in off any d consecutive bits in a circle of n bits

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.

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$.
• 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. Nov 1 '13 at 5:14