There are $10$ empty boxes numbered $1, 2, \dots , 10$ placed sequentially on the circumference of a circle.We perform $100$ independent trials. At each trial, one box is selected with probability $\dfrac{1}{10}$ and one ball is placed in each of the two neighbouring boxes of the selected one.

Define $X_k$ to be the number of balls in the $k$-th box at the end of $100$ trials.

(a) Find $E[X_k]$ for $1 \le k \le 10$.

(b) Find $\text{Cov} (X_k,X_5)$ for $1 \le k \le 10$.

Trial:I think $X_k\sim \text{Bin}(n=100,p=1/5)$ and $E(X_k)=np=20,V(X_k)=npq=16$.Am I right? Lastly how I find $\text{Cov}(X_k,X_5)$.


2 Answers 2


The general situation you have here is described by a multinomial distribution. The Wikipedia article about the multinomial distribution explains:

For n independent trials each of which leads to a success for exactly one of k categories, with each category having a given fixed success probability [...]

In your case, two balls are put in the boxes in each trial. You have already recognized that this leads to a success probability of 1/5 for each of the boxes. So your answer for (a) is correct.

In order to answer question (b), recall the formula for the covariance for $i\neq j$:

$$ Cov[X_{i}, X_{j}] = E[X_{i}\cdot X_{j}] - E[X_{i}]\cdot E[X_{j}] $$

If only one ball was put in a box in each trials, we could set $E[X_{i}\cdot X_{j}]=0$ because $X_{i}$ and $X_{j}$ could not be 1 (i.e. receive a ball) in the same trial. It is easily seen that this assumption is true whenever $j\neq i \pm 1 \text{ mod } 10$. For these cases, the covariance is $-np_{i}p_{j} = -100\cdot (1/5)\cdot (1/5) = -4$.

For the case that $j=i \pm 1 \text{ mod } 10$, the term $E[X_{i}\cdot X_{j}]\neq 0$ because both boxes receive a ball at the same trial. From the Wikipedia article about the binomial distribution we get

$$ Cov[X_{i}, X_{j}] = n\cdot (p_{b}-p_{i}p_{j}) $$

where $p_{b}$ denotes the probability that both boxes receive a ball. In this case, $p_{b}=1/10$. So finally, whenever $j=i \pm 1 \text{ mod } 10$ the covariance is $100\cdot (\frac{1}{10} - \frac{1}{5}\cdot \frac{1}{5})=6$.

  • 1
    $\begingroup$ By "$j = \pm 2i$" do you perhaps mean $j = i \pm 1 \mod 10$? $\endgroup$
    – whuber
    Commented Apr 14, 2013 at 19:05
  • $\begingroup$ Dear whuber. Exactly! I wasn't rigorous enough. Thanks for clarifying. $\endgroup$ Commented Apr 14, 2013 at 21:16

This is my first post on StackExchange, and I hope it is helpful. COOLSerdash gave a very complete answer already which I mostly agree with, but I will try to add a different perspective on the problem.

As you stated, $X_{k} \sim Binomial(n=100,p=\frac{1}{5}) \equiv 100 \times Bernoulli(\frac{1}{5})$

$\text{Cov}(X_5,X_k) = \mathbb{E}[(X_5-\mathbb{E}[X_5])(X_k-\mathbb{E}[X_k])]$

This leads to the expression $\mathbb{E}[X_5X_k]-\mathbb{E}[X_5]\mathbb{E}[X_k] = \mathbb{E}[X_5X_k]-100\times(\mathbb{E}(Bernoulli(\frac{1}{5}))$ $= \mathbb{E}[X_5X_k]-100\times(\frac{1}{25})=\mathbb{E}[X_5X_k]-4$.

Therefore, we have three conditions:

$k = 5 ; Cov(X_5,X_5) = Var(X_5) = Var(X_k) = 16$

$k \neq 3,7; Cov(X_5,X_k) = \mathbb{E}[X_5X_k]-4 = 0$

Consider the events $A := ${box $5$ gets a ball} , $B$ {box $k$ gets a ball} $\neq 3,7$, then $ \mathbb{P}(A,B) = \mathbb{P}(A)\mathbb{P}(B)$ due to independence.

$\therefore \mathbb{E}[X_5X_k]=100\times \mathbb{E}[A]\mathbb{E}[B]=100\times(\frac{1}{5}\times \frac{1}{5}) = 4$

$k = 3,7; Cov(X_5,X_k) = \mathbb{E}[X_5X_k]-4 = 6$ (as COOLSerdash stated)

With the defined events $A$ and $B$ for $k = 3,7$, $ \mathbb{P}(A,B) = \frac{1}{10}$ since the probability $A \cap B$ is the probability that box 4 (if $k=3$) or box 6 (if $k=7$) gets a ball.

Hope this helps!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.