TITLE: Combinatorics: Mean and Variance of an indicator function of items arranged in a circle.
QUESTION [5 upvotes]: I have a problem from a homework which I've been struggling with.
I normally wouldn't post homework here, but I've spent several hours trying to understand the correct way to solve this , to no avail.
I will provide my work, and hopefully someone can point me in the right direction.
The problem:
There are 25 balls (10 blue, 15 red) arranged randomly in a circle.
Let X be a random variable who's value is the number of BLUE balls 
with a RED ball on either side of it.
    A. Find E[X]
    B. Find Var(X)

So here's how I did it so far:
$$
\text{Let 'Xi' be an indicator, such that:}\\
 X_i = \left\{ 
  \begin{array}{1 l}
    1 & \quad \text{if the ith ball is blue, and i-1, i+1 balls are both red}\\
    0 & \quad \text{otherwise}
  \end{array} \right.\\ 
$$
Therefore we get E[X]:
$$
E[X_i] = \frac{15}{25} * \frac{10}{24} * \frac{14}{23} = \frac{7}{46}\\
\\
E[X]  =  \sum_{i=1}^{25} E[X_i] = 25*\frac{7}{46} = 3.804\\
$$
Now for the variance:
$$
Var(X) = \sum_{i=1}^{25} Var(X_i) + 2*\sum_{i<}\sum_{j} Cov(X_i,X_j) \\
Var(X_i) = p*(1-p) = \frac{7}{46}*\frac{39}{46} = \frac{273}{2116} \\
P \lbrace X_i = 1, X_j = 1 \rbrace\left\{  \begin{array}{1 l}
    |i-j|=1 & \quad \text{0 (since 2 blues are adjacent)}\\
    |i-j|=2 & \quad \frac{7}{46}*\frac{9}{22}*\frac{13}{21} = \frac{39}{1012}\\
    |i-j|>2 & \quad \frac{7}{46}*\frac{13}{22}*\frac{9}{21}*\frac{12}{20} = \frac{117}{5060}
  \end{array} \right.\\
\text{and since } \quad Cov(X_i,X_j) = E[X_i X_j] - E[X_i]E[X_j] \\
\\
$$
we get:
$$
Cov(X_i,X_j) = \left\{  \begin{array}{1 l}
    |i-j|=1 & \quad 0 - (\frac{7}{46})^2 = -\frac{49}{2116}\\
    |i-j|=2 & \quad \frac{39}{1012}-(\frac{7}{46})^2 = \frac{179}{11638}\\
    |i-j|>2 & \quad \frac{117}{5060}-(\frac{7}{46})^2 = -\frac{1}{29095}\\
  \end{array} \right.\\
$$
Now, we need the sum of the Covariances. To do this we need to know how many of each case there are- and this is where I'm getting confused. 
I would think we would do as follows:
We have 25c2 different possibilities where i!=j (where they can be placed).
We have 25 where |i-j| = 1, 25 where |i-j|=2 (it's a circle), and 250 where |i-j|>2.
Naively, I get: 
$$
Var(X) = 25*\frac{273}{2116} + 2*(25*(-\frac{49}{2116})+25*\frac{179}{11638}+250*(-\frac{1}{29095})) = 2.8194\\
$$
But it's a circle, so technically we have 25 ways of looking at the circle, meaning I should divide by 25 - 
but, these are not taking into account all the permutations of the 25c10 different possibilities, so I would be discounting possibilities by doing so..
I feel like this is wrong because I'm not taking into account the circle (except by allowing 25 indicators instead of 24 or 23, which is only adding possibilities and not removing them).
Help, please?

REPLY [4 votes]: There are multiple defensible interpretations of the question, depending on how the "random arrangement" is conducted.
As a multinomial problem
The red balls determine $n=15$ spaces ("slots") between them. Suppose they are filled equiprobably and independently by the $k=10$ blue balls.  $X$ counts the number of slots filled with exactly one blue ball.
To find the expectation of $X$, consider a single slot.  Let $X_i$ be the indicator of the event that that slot has exactly one blue ball.  Because the count of blue balls in that slot ($Y_i$) has a Binomial$(k, 1/n)$ distribution, 
$$\mathbb{E}(X_i) = \Pr(X_i = 1) = \Pr(Y_i=1) = \binom{k}{1}\frac{(n-1)^{k-1}}{n^k} = \frac{k}{n}\left(1-\frac{1}{n}\right)^{k-1}.$$
Whence, by linearity of expectation,
$$\mu_1 = \mathbb{E}(X) = \mathbb{E}\left(\sum_iX_i\right) = \sum_i\mathbb{E}(X_i) = n\mathbb{E}(X_i) = k\left(1-\frac{1}{n}\right)^{k-1}.$$
To find the variance we will need to obtain the expectation of
$$X^2 = \left(\sum_i X_i\right)^2 = \sum_i \left(X_i\right)^2 + \sum_{i\ne j}X_iX_j = X + \sum_{i\ne j}X_iX_j.$$
(The last equality follows from $X_i^2 = X_i$.)  All terms in the last sum have identical distributions.  Consider one of them:
$$\mathbb{E}(X_iX_j) = \Pr(X_iX_j=1) = \Pr(Y_i=1,\, Y_j=1).$$
The latter is the event that one ball lands in slot $i$, another in slot $j$, and the remaining $k-2$ balls in the remaining $n-2$ slots.  This is a multinomial probability given by
$$ \Pr(Y_i=1,\, Y_j=1) = \binom{k}{1,1,k-2} \frac{(n-2)^{k-2}}{n^k} = \frac{1}{n^2}k(k-1)\left(1-\frac{2}{n}\right)^{k-2}.$$
Because there are $n(n-1)$ distinct ordered pairs $(i,j)$, we obtain
$$\mu_2 = \mathbb{E}(X^2) = \mathbb{E}(X) + n(n-1)\mathbb{E}(X_iX_j) = \mu_1 + k(k-1)\left(1-\frac{2}{n}\right)^{k-2}\left(1-\frac{1}{n}\right).$$
The variance of $X$ is, as usual,
$$\text{var}(X) = \mu_2 - \mu_1^2.$$
For $k=10, n=15$ compute that $\mathbb{E}(X) = \mu_1 = 5.374412$ and $\text{var}(X) = 3.226079$.
As a permutation problem
Suppose instead that all $(n+k)!$ possible permutations of the balls in the circle are equiprobable.  Let $\mathcal{P}$ be the $n+k$ positions indexed by the integers modulo $n+k$.  As a matter of notation, let $\text{red}(i)$ be the event there is a red ball at position $i$ and $\text{blue}(i)$ be the event there is a blue ball at position $i$.
This time let's make a position-centric analysis rather than one from the point of view of the blue balls: for each $i\in\mathcal{P}$, let $X_i$ be the indicator that a blue ball is at position $i$ and red balls are situated at positions $i-1$ and $i+1$.  The chance that $X_i=1$ is readily found by multiplying a succession of conditional probabilities:
$$\eqalign{
\mathbb{E}(X_i=1) &= \Pr(X_i=1) \\
&= \Pr(\text{red}(i-1))\Pr(\text{blue}(i)|\text{red}(i-1))\Pr(\text{red}(i+1)|\text{blue}(i), \text{red}(i-1)) \\
&= \frac{n}{n+k}\frac{k}{n+k-1}\frac{n-1}{n+k-2} \\
&= \frac{n^{(2)} k^{(1)}}{(n+k)^{(3)}}.
}$$
Here, $a^{(j)}=a(a-1)\cdots(a-j+1)$ denotes the factorial power.
As before, additivity of expectation implies 
$$\mu_1 = \mathbb{E}(X) = (n+k)\mathbb{E}(X_0) = \frac{n^{(2)} k^{(1)}}{(n+k-1)^{(2)}}.$$
To obtain the variance we will need to compute the expected products $\mathbb{E}(X_iX_j)$.  These involve four distinct configurations:

$i=j$.  There are $n+k$ of these, each contributing $\mathbb{E}(X_i^2) = \mathbb{E}(X_i)$ to the second moment.  The total contribution therefore is $\mu_1$.
$|i-j|=1$: that is, $i$ and $j$ are immediate neighbors in the circle.  (The notation $|a|$ refers to the distance around the circle, which can be computed as $\min\{|\pm a + j(n-k)|: j\in\mathbb{Z}\}.$)  In this case it is impossible that $X_i$ and $X_j$ both equal $1$, so the total contribution is zero.
$|i-j|=2$.  These are the configurations of the form red-blue-red-blue-red.  Reasoning as before (with chains of conditional probabilities), each such configuration has an expectation of $n^{(3)} k^{(2)}/(n+k)^{(5)}$.  There are $2(n+k)$ ordered pairs $(i,j)$ with this relationship, whence the contribution is
$$2\frac{n^{(3)} k^{(2)}}{(n+k-1)^{(4)}}.$$
(This value is taken to be zero whenever $n+k\lt 4$, with the same convention holding for all similar expressions below.)
$|i-j|\gt 2$.  These are configurations of the form red-blue-red...red-blue-red.  There are $(n+k)(n+k-5)$ such ordered pairs, giving a contribution
$$\frac{n^{(4)} k^{(2)}}{(n+k-1)^{(4)}}.$$

Consequently the variance is
$$\text{var}(X) = \mu_1 + 2\frac{n^{(3)} k^{(2)}}{(n+k-1)^{(4)}} + \frac{n^{(4)} k^{(2)}}{(n+k-1)^{(4)}} - \mu_1^2.$$
With $n=15$ and $k=10$ we obtain $\mu_1 = 175/46\approx 3.80435$, $\mu_2 = 4375/253$, and the variance is $65625/23276\approx 2.81943.$  These results agree with those presented in the question.

Verification of the results
There are several ways to check these results, including simulation and exhaustive enumeration.  To illustrate simulation, here is a check of the multinomial results. (The platform is R.)
n <- 15        # Slots
k <- 10        # Balls
n.iter <- 10^5 # Simulation length
set.seed(17)
x <- replicate(n.iter, sum(1 == table(sample.int(n, k, replace=TRUE))))
cat("Mean =", round(mean(x), 3), "Var =", round(var(x), 3))

The output is

Mean = 5.367 Var = 3.2

agreeing closely with the multinomial analysis.
Here is a calculation of the full distribution of $X$ in the permutation case.  (The platform is Mathematica.)
neighbors[s_List, n_] := 
 Total[(Boole[Mod[#, n] != 0] & /@ (RotateRight[s] - (s - 1))) 
       (Boole[Mod[#, n] != 0] & /@ (RotateLeft[s] - (s + 1)))];
With[{n = 15, k = 10}, Tally[neighbors[#, n + k] & /@ 
                       Subsets[Range[n + k], {k}]]]


{{0, 40380}, {1, 205100}, {2, 495950}, {3, 709800}, {4, 775775}, {5, 500500}, 
     {6, 375375}, {7, 85800}, {8, 75075}, {10, 5005}}

That is, there is a chance of $40380/\binom{25}{10}$ that $X=0$, a chance of $205100/\binom{25}{10}$ that $X=1$, and so on.
The expectation is $\mu_1=(0\times 40380 + 1\times 205100 + \cdots + 10\times 5005)/\binom{25}{10} = 175/46$ and the second moment, computed similarly, is $\mu_2 = 4375/253$, agreeing with the analysis.
{"set_name": "stack_exchange", "score": 5, "question_id": 850357}