# Probability Bridges and Islands

3)CitiesA,B,...,Z are connected in a loop by 26 two-way roads: AtoB, BtoC, ...,Y toZ, and Z to A. Each road can be destroyed by rain with probability p independently of the others.

a) Find the probability that, after the rain, there are two cities that are not reachable from each other.

b) Find the probability that, after the rain, it is possible to get from A to Z.

No clue how to do this. I know that you can still access all islands if a single bridge goes down though.

• ...So the going down of a single bridge is not enough, right? Isn't that a clou on its own? – drhab Feb 21 '18 at 15:55
• Yes, so that insinuates that if two bridges are destroyed then there is a definitive chance that access to two cities have been destroyed. I am primarily unsure of how to notate this particular occurence. – Lucky12456 Feb 21 '18 at 15:59

$a.)$ Probability there exist two cities that are not reachable from each other is equivalent to the probability that $2$ roads or more were destroyed.

Let $X(n) = \text{{$n$roads destroyed}}$ and $N = 26$,

$$P(X > 1)=1 - P(X=1)-P(X=0)$$

$P(X=0) = (1-p)^N$,

$P(X=1) = \binom{N}{1}p(1-p)^{N-1} = Np(1-p)^{N-1}$

Because there are $N$ ways $1$ road can be destroyed.

Putting everything together:

$$P(X > 1) =1 - Np(1-p)^{N-1}-(1-p)^N$$

$b.)$ It's possible to get from $A$ to $Z$ when at least one road between $A$ and $Z$ exists. There are $2$ paths between them:

$1.$ $A\to Z$ the short way.

$2.$ $A\to B \to C \to \dots \to Z$ the long way.

In order for $Z$ to not be reachable from $A$, the road in path $1$ AND at least a road in path $2$ must be destroyed.

Let $E_1$ be the event the road in path $1$ is destroyed

Let $E_2$ be the event that at least one road in path $2$ is destroyed

$$P(E_1 \cap E_2) = P(E_1)P(E_2)$$

By independence.

$$P(E_1)P(E_2)= p \cdot (1 - (1-p)^{N-1})$$

Did you draw a picture with fewer cities? For a, if two or more bridges go out there will be a disconnection. For b, you need to destroy the bridge from A to Z and one other.

Hint

for a) you need the probability that at least two bridges are damaged, so work out $1-$ the probability of no damage or exactly one damaged

For b) work out the probability of damage to AZ alone or of AZ damaged but the rest undamaged