About putting $n$ distinct balls into $n$ distinct boxes.

143 Views Asked by At

Let the balls be labelled $1,2,3,..n$ and the boxes be labelled $1,2,3,..,n$.

Now I want to find,

  • What is the expected value of the minimum value of the label among the boxes which are non-empty

  • What is the expected number of boxes with exactly one ball in them?


Whatever way I am thinking of it, I am getting complicated summation form of answers and not any exact closed form!

2

There are 2 best solutions below

4
On

A

To expectation of the minimum used label, $K$, we first measure the probability that all the balls being among the top $n-k$ boxes. That is, that the minimum label will be greater than some value $k$.

In the total space each of $n$ balls has a choice of $n$ boxes ($n^n$). In the restricted space each of $n$ balls has a choice of $n-k$ boxes $(n-k)^n$. So then: $$\begin{align} \Pr(K > k) & = \frac{(n-k)^n}{n^n} \\[1ex] \Pr(K > k-1) & = \frac{(n-k+1)^n}{n^n} \\[1ex] \Pr(K=k) & = \Pr(K>k-1)-\Pr(K>k) \\ & = \frac{(n-k+1)^n-(n-k)^n}{n^n} \\[2ex] E(K) & = \sum_{k=1}^{n} k \Pr(K=k) \\ & = \frac 1 {n^n}\sum_{k=1}^n (k(n-k+1)^n-k(n-k)^n) \\ & = \frac 1 {n^n}\left(\sum_{k=0}^{n-1} (k+1)(n-k)^n-\sum_{k=1}^{n} k(n-k)^n\right) \\ & = \frac 1 {n^n}\left( n^n + \sum_{k=1}^{n-1} (n-k)^n\right) \\ & = \frac 1 {n^n}\left( n^n + \sum_{k=1}^{n-1} k^n\right) \\ & = \mathop{1 + n^{-n}\underbrace{\sum_{k=1}^{n-1} k^n}}_{\text{a generalised Harmonic series?}} \end{align}$$


B

Let $B_i$ be the Bernouli indicator that box $i$ contains exactly one ball. We then use the linearity of expectation to find the expected value of $B:=\sum_{i=1}^n B_i$

$$\begin{align} \forall i\in \{1..n\}:\Pr(B_i=1) & = {n\choose 1}(n-1)^{n-1}/n^n \\[2ex] \mathbb{E}[B] & = \mathbb{E}[\sum_{i=1}^n B_i] \\ & = \sum_{i=1}^n \mathbb{E}[B_i] \\ & = n\times (0\times \Pr(B_\ast=0)+1\times \Pr(B_\ast=1)) \\[1ex]\therefore \mathbb{E}[B] & = \frac{(n-1)^{n-1} }{ n^{n-2}} \end{align}$$

0
On

Here is an approach using labelled species and exponential generating functions.

For the first problem we have the species $$\sum_{q=1}^n \mathcal{U}^q \times \mathfrak{P}_{\ge 1}(\mathcal{Z}) \times \mathfrak{P}(\mathcal{Z})^{n-q}$$ with $\mathcal{U}$ marking the end of the intial segment of empty bins.

This yields the generating function $$\sum_{q=1}^n u^q (\exp(z)-1) \exp(z)^{n-q} = (\exp(z)-1) \exp(z)^n \sum_{q=1}^n u^q \exp(z)^{-q}.$$ Some algebra produces $$(\exp(z)-1) \exp(z)^{n-1} \times u \frac{(u/\exp(z))^n - 1}{u/\exp(z)-1}.$$ which is $$(\exp(z)-1) \frac{u^{n+1} - u \exp(z)^n}{u-\exp(z)}.$$

Differentiate and put $u=1$ to obtain the EGF of the count $$\left.(\exp(z)-1) \left(\frac{(n+1)u^n - \exp(z)^n}{u-\exp(z)} - \frac{u^{n+1} - u \exp(z)^n}{(u-\exp(z))^2} \right)\right|_{u=1} \\= (\exp(z)-1) \left(\frac{(n+1) - \exp(z)^n}{1-\exp(z)} - \frac{1 - \exp(z)^n}{(1-\exp(z))^2} \right) \\ = \frac{1 - \exp(z)^n}{1-\exp(z)} + \exp(z)^n - (n+1) = -(n+1) + \frac{1 - \exp(z)^{n+1}}{1-\exp(z)}.$$

Performing coefficient extraction we obtain for $n\ge 1$ the answer $$\frac{1}{n^n} n! [z^n] \left(-(n+1) + \frac{1 - \exp(z)^{n+1}}{1-\exp(z)}\right) = \frac{1}{n^n} n! [z^n] \left(-(n+1) + \sum_{q=0}^n \exp(z)^q\right) \\ = \frac{1}{n^n} n! \sum_{q=1}^n \frac{q^n}{n!} = \frac{1}{n^n} \sum_{q=1}^n q^n = 1 + \frac{1}{n^n} \sum_{q=1}^{n-1} q^n.$$

For the second problem the species is $$\mathfrak{S}_{=n} \left(\mathcal{U}\mathcal{Z}+\mathfrak{P}_{\ne 1}(\mathcal{Z})\right).$$ with $\mathcal{U}$ marking singletons.

This gives the generating function $$\left(uz + \exp(z) - z\right)^n.$$

For the expected number of singletons differentiate with respect to $u$ and set $u=1$ to obtain

$$\left. n \left(uz + \exp(z) - z\right)^{n-1} \times z\right|_{u=1} = n z \exp(z)^{n-1}.$$

Finally extract coefficients for the expectation which is $$\frac{1}{n^n} n! [z^n] n z \exp(z)^{n-1} = \frac{1}{n^{n-1}} n! [z^{n-1}] \exp(z)^{n-1} = \frac{1}{n^{n-1}} n! \frac{(n-1)^{n-1}}{(n-1)!} \\= \frac{1}{n^{n-1}} n (n-1)^{n-1} = \frac{(n-1)^{n-1}}{n^{n-2}}.$$

These results match the first answer.

Remark. Since $$\frac{(n-1)^{n-1}}{n^{n-2}} = (n-1)\left(1-\frac{1}{n}\right)^{n-2} = (n-1)\left(1-\frac{1}{n}\right)^n \left(1-\frac{1}{n}\right)^{-2} \\ = \frac{n^2}{n-1} \left(1-\frac{1}{n}\right)^n$$ the second expectation is $$\frac{1}{e} \frac{n^2}{n-1}.$$