Suppose there are $S$ slots in a cluster and $N$ individuals would pick $K$ slots each randomly from $S$. What's the expectation of the number of conflicts (each slot can only be picked by at most 1 person. e.g. if there are 5 people who pick the same slot, then there are 4 conflicts)?
When $N$ is 2, the formula for the expectation is easy. However, when $N$ gets larger, I feel the formula would be increasingly complicated.
I am wondering whether this is a classic problem in the field of combinatorics or can be reduced to some classic combinatoric problem? And what are some proved properties about the number of conflicts? For example, when $N, S, K$ are linearly scaled, what can we say about the trend of the number of conflicts?
Best Answer
Let $X_i$ be the random variable indicating how many conflicts happen in the $i$th slot. Let $Y_i$ be the random variable indicating how many individuals pick the $i$th slot. Then clearly $X_i=\max\{0,Y_i-1\}$.
Note every individual independently picks the $i$th slot with probability $K/S$, $Y_i$ obeys the binomial distribution, so \begin{align} \mathbb{E}(X_i)&=0\cdot\mathrm{Pr}\{Y_i\le 1\}+\sum_{j=1}^{N-1} j\cdot\mathrm{Pr}\{Y_i=j+1\}\\ &=\sum_{j=1}^{N-1} (j+1)\cdot\mathrm{Pr}\{Y_i=j+1\}-\sum_{j=1}^{N-1}\mathrm{Pr}\{Y_i=j+1\}\\ &=\mathbb{E}(Y_i)-\mathrm{Pr}\{Y_i=1\}-(1-\mathrm{Pr}\{Y_i=1\}-\mathrm{Pr}\{Y_i=0\})\\ &=\frac{NK}{S}-1+\left(1-\frac{K}{S}\right)^N. \end{align}
The expectation of the number of conflicts is equal to $$\mathbb{E}\left(\sum_{i=1}^S X_i\right)=\sum_{i=1}^S\mathbb{E}(X_i)=NK-S+S\left(1-\frac{K}{S}\right)^N.$$