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

  • $\begingroup$ 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. $\endgroup$ – ithisa Mar 23 '13 at 22:42
  • $\begingroup$ @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. $\endgroup$ – Micah Mar 23 '13 at 22:50
  • $\begingroup$ Also, did you mean "covariance" instead of "variance" in 1 and 2? Also, I didn't quite understand where you get $E(XY)$. $\endgroup$ – ithisa Mar 23 '13 at 22:57
  • 1
    $\begingroup$ @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)$. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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