# Expected number of neighbors

Given a row of 16 houses where 10 are red and 6 are blue, what is the expected number of neigbors of a different color?

-
By "neighbors of a different color"... do you mean given any one house what are the chances that the house to the left and the house to the right of that house (if the house is not on the end) are the same color as the given house? –  futurebird Nov 9 '10 at 4:22
You should state the implicitly assumed distribution in the space of all permutations (here: uniform). –  Raphael Nov 10 '10 at 18:12

Let $X$ be the number of neighbors of a different color. Let $X_i$ be 1 if houses $i$ and $i+1$ are different colors and 0 otherwise. Then $X = \sum_{i=1}^{15} X_i.$

So the expected number of neighbors of a different color is $$E\left[\sum_{i=1}^{15} X_i\right] = \sum_{i=1}^{15} E[X_i] = \sum_{i=1}^{15} P(X_i = 1).$$

Now, $$P(X_i = 1) = P(i \text{ is red})P(i+1 \text{ is blue}|i \text{ is red}) + P(i \text{ is blue})P(i+1 \text{ is red}|i \text{ is blue})$$ $$= \frac{10}{16} \frac{6}{15} + \frac{6}{16} \frac{10}{15} = \frac{120}{16(15)} = \frac{1}{2}.$$

Thus $$E[X] = \sum_{i=1}^{15} \frac{1}{2} = 7.5.$$

More generally, using indicator variables is often an effective way to calculate expected values. The linearity of the expectation operator allows you to sidestep all the nasty dependencies you would otherwise be forced to deal with. For lots of interesting examples using this approach, see Section 7.2 of Sheldon Ross's A First Course in Probability.

Given that the answer comes out so nicely I would not be surprised if there is a cleaner argument than mine. If someone comes up with one I would love to see it.

Moron's generalization has inspired me to generalize mine. :)

Suppose you have $m$ red houses and $n$ blue houses. Then the expected number of neighbors of a different color is $$\frac{2mn}{m+n}.$$

Similar to my argument above, $$P(X_i = 1) = P(i \text{ is red})P(i+1 \text{ is blue}|i \text{ is red}) + P(i \text{ is blue})P(i+1 \text{ is red}|i \text{ is blue})$$ $$= \frac{m}{m+n} \frac{n}{m+n-1} + \frac{n}{m+n} \frac{m}{m+n-1} = \frac{2mn}{(m+n)(m+n-1)}.$$

Thus $$E[X] = \sum_{i=1}^{m+n-1} \frac{2mn}{(m+n)(m+n-1)} = \frac{2mn}{m+n}.$$

-
+1 : no need for a cleaner argument. Your answer is quite clean already. –  Djaian Nov 9 '10 at 9:09
Very nice! We get $m+n = (m-n)^2$ (for pbt 1/2 case) which confirms my calculation. I wish I could upvote again. –  Aryabhata Nov 10 '10 at 18:01

The chances of a particular neighbour pair being the same colour is

$$\frac{{14 \choose 8} + {14 \choose 10}}{{16 \choose 6}} = \frac{4004}{8008} = \frac{1}{2}$$

Hence the answer is $\displaystyle 7.5$

This is happening because $\displaystyle {14 \choose 8}, {14 \choose 9}, {14 \choose 10}$ are in arithmetic progession: The number of ways of being same colour is $\displaystyle {14 \choose 8} + {14 \choose 10}$ and the number of ways of being different is $\displaystyle 2{14 \choose 9}$. The probability is $\displaystyle \frac{1}{2}$ if these two are equal.

Interestingly, $\displaystyle {n \choose r}, {n \choose r+1}, {n \choose r+2}$ are in arithmetic progression if and only if $\displaystyle n+2$ is a perfect square and $\displaystyle r$ is given by $\displaystyle r = \frac{n-2 \pm \sqrt{n+2}}{2}$ (see the end of the answer for a proof).

So for instance, the whole bunch of problems:

15 red, 10 blue

21 red, 15 blue

etc give rise to this neat probability of being $\displaystyle \frac{1}{2}$.

Proof that n+2 is a perfect square

$\displaystyle {n \choose r}, {n \choose r+1}, {n \choose r+2}$ are in arithmetic progression iff

$\displaystyle 2{n \choose r+1} = {n \choose r} + {n \choose r+2}$

i.e

$\displaystyle 2 = \frac{r+1}{n-r} + \frac{n-r-1}{r+2}$

Doing some manipulations gives us

$\displaystyle (n-2r-2)^2 = n+2$

Hence

$\displaystyle r = \frac{n-2 \pm \sqrt{n+2}}{2}$

Which has an integer solution iff $\displaystyle n+2$ is a perfect square.

-
+1 for a different perspective (considering the complement) and for helping me see that the $\frac{120}{15(16)}$ expression in my answer is just $\frac{1}{2}$. That simplifies my answer, and I will update it accordingly. Thanks. –  Mike Spivey Nov 9 '10 at 16:15
@Mike: I added some more information to the my answer, which shows that $n+2$ has to be a perfect square for this neat answer(probability 1/2) to hold! The problem turned out to be more interesting than I anticipated :-) –  Aryabhata Nov 9 '10 at 18:03
I'm glad you worked this calculation out. After I realized that probability came out to $\frac{1}{2}$ I was wondering if we could characterize the cases in which that occurred. –  Mike Spivey Nov 10 '10 at 17:54