World's most popular travel blog for travel bloggers.

# Probability distribution of runs given k bits set in an n-bit circular buffer

, ,
Problem Detail:

Imagine you have a circular buffer holding n bits. You (uniformly) randomly set k of those n bits. (This is without replacement, so you are left with a buffer of n bits of which kbits are set.)

Now you randomly select a location in the buffer. What is the probability distribution of the run of set bits starting at that location? And what is the mean length of said run?

It's trivial that P(k,n,0) = 1 - k/n (that is, the first bit will be set with a probability of k/n, so there's a 1 - k/n chance that it will be unset.).

I think this has something to do with the hyper-geometric distribution, but I am not sure.

###### Answered By : Yuval Filmus

Note first that there is no need to randomly select a location in the buffer – we can fix one as we please. From that location, the probability that a run will be at least $t$ long is the probability that the $k$-set includes the first $t$ locations, which is $$\Pr[R \geq t] = \frac{\binom{n-t}{k-t}}{\binom{n}{k}}.$$ Similarly, the probability that a run will be exactly $t$ long is the probability that the $k$-set includes the first $t$ locations but not the one after it, which is $$\Pr[R = t] = \frac{\binom{n-t-1}{k-t}}{\binom{n}{k}}.$$

The expectation of $R$ is $$\mathbb{E}[R] = \sum_{t \geq 1} \Pr[R \geq t] = \frac{\sum_{t \geq 1} \binom{n-t}{n-k}}{\binom{n}{k}} = \frac{\binom{n}{n-k+1}}{\binom{n}{k}} = \frac{k}{n-k+1},$$ using the formula $\sum_{x=r}^m \binom{x}{r} = \binom{m+1}{r+1}$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/60151

3200 people like this

#### Post a Comment

Let us know your responses and feedback