# Interesting probability question about islands and bridges

The inhabitants of the beautiful and ancient canal city of Pentapolis live on 5 islands separated from each other by water. Bridges cross from one island to another as shown.

On any day, a bridge can be closed, with probability $p$, for restoration work. Assuming that the 8 bridges are closed independently, find the mean and variance of the number of islands which are completely cut off because of restoration work.

-

By linearity of expectation, it's straightforward to see that the mean is $4p^3+p^4$.

Since the cutoff probabilities are correlated, the variance of their sum can be computed as the sum of all possible covariances. By repeatedly using the formula $\operatorname{Cov}(X,Y)=E[XY]-E[X]E[Y]$, notice that:

1. The variance of the first four islands' cutoffs is $p^3-p^6$.
2. The variance of the middle island's cutoff is $p^4-p^8$.
3. The covariance of the middle island and any outer island is $p^6-p^7$.
4. The covariance of any two adjacent outer islands is $p^5-p^6$.
5. The covariance of any two opposite outer islands is $0$.

If we add up the $25$ possible covariances, we'll get: $4$ of type 1., $1$ of type 2., $8$ of type 3., $8$ of type 4., and $4$ of type $5$. So the total variance is $$4(p^3-p^6)+p^4-p^8+8(p^6-p^7+p^5-p^6)=4p^3+p^4+8p^5-4p^6-8p^7-p^8 \, .$$

-
It's interesting, though, how the events "island $i$ is unreachable" are dependent yet one can still use linearity of expectation. This seems a bit counterintuitive. – user54609 Mar 23 '13 at 22:42
@EricDong: When thinking about the intuition behind linearity of expectation for correlated things, I like to keep in mind the simplest possible situation: two indicator random variables with mean $1/2$. If they're perfectly correlated, their sum is either $2$ or $0$ so its mean is $1$. If they're independent it's $0$ with probability $1/4$, $1$ with probability $1/2$, and $2$ with probability $1/4$, so its mean is $1$. If they're perfectly anticorrelated it's always $1$, so its mean is $1$. In any case, changes in dependence show up as changes in the variance, not the mean. – Micah Mar 23 '13 at 22:50
Also, did you mean "covariance" instead of "variance" in 1 and 2? Also, I didn't quite understand where you get $E(XY)$. – user54609 Mar 23 '13 at 22:57
@EricDong: The variance is the covariance of a thing with itself. In this case, where we're dealing with indicator variables, $E(XY)$ is just $P(X \wedge Y)$. – Micah Mar 23 '13 at 23:14

for mean: define random variables $X_i$ : $X_i \in {1,0}$ and $X_i = 1$ iff the i-th island will be cut off after restoration work. then $X= \sum X_i$ shows the numbers of islands cut off after restoration. use linearity of expectation value to calculate $E(X)$, note that $E(X_i)=P(X_i = 1)=p^d$ where d is the number of bridges ending to i-th island.

-