Question

. A binary string containing M 0’s and N 1’s (in arbitrary order, where all orderings are equally likely) is sent over a network. What is the probability that the first r bits of the received message contain exactly k 1’s?

Answer 1

Answer:

$P(k) = \frac{\binom{N}{k} \binom{(M+N) - N}{r-k}}{\binom{M+N}{r}}$

Step-by-step explanation:

We can model the string as a hypergeometric distribution, as each bit has two possible values, 1 or 0, and the chance of a 1 or 0 changes with every bit, as there are a finite number M of 0's and N of 1's and every bit takes one of those values.

If M+N (total size of the string) >> r (number of trials), we could model it as a binomial distribution as the probability of a 1 or 0 wouldn't change in a significant amount with every bit, but as we don't know the magnitude of M+N and r, we follow up with hypergeometric distribution.

The distribution has the following formula for probability:

$P(k) = \frac{\binom{K}{k} \binom{N - K}{n-k}}{\binom{N}{n}}$

Where k is the number of sucesses, K is how many total sucess states are in the population, N is the population size and n is the number of draws.

For our case, a 1 would be a sucess, i.e. k the number of 1's we want to know the probability, N our total number of 1's, M+N the length of the string (population size) and we want to analyse what happens in the first r bits (number of draws):

$P(k) = \frac{\binom{N}{k} \binom{(M+N) - N}{r-k}}{\binom{M+N}{r}}$