Given $n$ slots and $k$ objects to fill the slots, what is the probability of a given slot to be filled.

combinatoricsintuition

Problem

Given:

  1. $n$ slots, numbered from $1\ldots n$
  2. $k$ objects
  3. a slot can be filled by one object

what is the probability that a slot at some position $i$ to be filled?

Some Notation

For a visual representation we can denote slot at position $i$ with:

  1. $\square_i$ if it is empty or
  2. $\blacksquare_i$ if it is filled

A sample configuration can be:

$$
(\blacksquare_1, \blacksquare_2, \square_3, \ldots, \square_n)
$$
where slots $1$ and $2$ are filled, and other $k-2$ slots somewhere between $4$ and $n-1$.

A special configuration is:

$$
(\blacksquare_1, \blacksquare_2, \ldots, \blacksquare_k, \square_{k+1}\ldots, \square_n)
$$

where slots from $1$ to $k$ are filled, and the following are empty.
.

Therefore we are interested in the value of $\Pr(\blacksquare_i)$

A possible approach

We can count all the possible configurations by with combinations, by thinking how can we pick $k$ numbers from $(1, 2, \ldots, n)$ irregardles of the order, the picked number is the filled slot:

$$
\texttt{total} = \frac{n!}{k!(n-k)!}
$$

How would we count the ones that are match the $\blacksquare_i$?

By just removing the $i$ slot and ending up with $n-1$ slots and $k-1$ fills, and doing the same calculation as above, only on a smaller set $(1, 2, \ldots, i-1, i+1, \ldots, n)$:

$$
\texttt{remaining} = \frac{(n-1)!}{(k-1)!(n-1-k+1)!}
$$

If we divide them we get our result.

$$
\frac{\texttt{remaining}}{\texttt{total}} = \ldots = \frac{k}{n}
$$

Discussion

I am having a hard time understanding intuitively the final result:

$$
\Pr(\blacksquare_i) = \frac{k}{n}
$$

  1. is this the most intuitive way of explaining that the position is not relevant? (maybe by counting the probabilities of each position?)

  2. is there some math concept we can use here?

  3. how can this problem be reducible to:

What is the probability of a random slot to be filled

or, if we like to think of balls in a bag, that come in 2 colors, white, $\square$, and black, $\blacksquare$ the question would be:

What is the probability of the extracted ball to be black

Thanks!

Best Answer

The intuition is such: you have $k$ balls and $n-k$ voids, and you need to pick what to put at slot $i$. You have $k$ objects that will make it full, so the probability is indeed $\tfrac{k}{n}$. Due to symmetry, the answer is independent of $i$.

Choosing the slots are random will not change this result, as they are all symmetric and their names don't matter.

Related Question