Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 1 down vote accepted

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 \, . $$

share|cite|improve this answer
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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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