Question

3. You have N boxes (labeled 1,2,... , N), and you have k balls. You drop the balls into the boxes, independently of each other. For each ball the probability that it will land in a particular box is 1/N. Let Xi be the number of balls in box 1 and XN the number of balls in box N. Calculate Corr(X,XN)

Answer 1

There are N boxes and the k balls. The probability that a ball lands in box i is $p_i=\frac{1}{N}$ , where i=1,..,N

Let $X_i$ be the number of balls landed in box i.

Then the random vector $X_1,...,X_N$ has a multinomial distribution with k trials and cell probabilities $p_1=...=p_N=\frac{1}{N}$

The joint pmf of $(X_1,...,X_N)$ is given by

$\begin{align*} p(x_1,...,x_N)&=\frac{k!}{x_1!\times ...\times x_N!}p_1^{x_1}...p_N^{x_N}\\ &=\frac{k!}{x_1!\times ...\times x_N!}(1/N)^{x_1}..(1/N)^{x_N}\\ &=\frac{k!}{x_1!\times ...\times x_N!}\left(\frac{1}{N} \right )^{\sum_{i=1}^Nx_i}\\ &=\frac{k!}{x_1!\times ...\times x_N!}\left(\frac{1}{N} \right )^{k}\quad \text{as }\sum_{i=1}^Nx_i=k\\ \end{align*}$

We know that if $(X_1,...,X_N)$ have multinomial distribution with k trials, then the covariance of $\begin{align*} X_i,X_j \end{align*}$ is given by

$\begin{align*} Cov(X_i,X_j)=-kp_ip_j \end{align*}$

Hence the Covariance of $\begin{align*} X_1,X_N \end{align*}$ is

$\begin{align*} Cov(X_1,X_N)=-kp_1p_N=-\frac{k}{N^2} \end{align*}$

If we consider the number of balls in a single box $\begin{align*} X_i \end{align*}$ , this has a Binomial distribution with number of trails k and probability of success $\begin{align*} p_i=\frac{1}{N}\end{align*}$

The pmf of $\begin{align*} X_i \end{align*}$ is

$\begin{align*} P(X_i=x_i)&=\binom{k}{x_i}p_i^{x_i}(1-p_i)^{k-x_i}\\ &=\binom{k}{x_i}(1/N)^{x_i}(1-(1/N))^{k-x_i}\\ \end{align*}$

The variance of such a Binomial variable is

$\begin{align*} Var(X_i)=kp_i(1-p_i)=k\frac{1}{N}\left(1-\frac{1}{N} \right )=\frac{k(N-1)}{N^2}\end{align*}$

Now back to the correlation of $\begin{align*} X_1,X_N \end{align*}$ , which is

$\begin{align*} Corr(X_1,X_N)&=\frac{Cov(X_1,X_n)}{\sqrt{Var(X_1)Var(X_N)}}\\ &=\frac{-\frac{k}{N^2}}{\sqrt{\frac{k(N-1)}{N^2}\times \frac{k(N-1)}{N^2}}} \\ &=\frac{-\frac{k}{N^2}}{\frac{k(N-1)}{N^2}} \\ &=-\frac{1}{N-1} \end{align*}$