Probability of getting from one point to another given probability that path is open

Question

The points Woodstock and Tunbridge (W and T) are connected above in 3 different scenarios. p and q are the probability that the path is open. The question is what is the probability one can get from W to T.

Assuming all of the path probabilities are mutually independent:

For a) I think it is pq

For b) I think it's p + q - pq

I'm not sure how to approach c, I thought I would try inclusion exclusion for four possible path (A, B, C, D) from W to T: P(A) = P(B) = 0.72, P(C) = 0.608, P(D) = 0.77, from multiplying the probabilities through (and assuming you can't go backwards):

$P(A \cup B\cup C\cup D) = P(A) + P(B) + P(C) + P(D)-P(A \cap B)-P(A \cap C)-P(A \cap D)-P(B \cap C)-P(B \cap D)-P(C \cap D)+P(A \cap B \cap C)+P(A \cap C \cap D)+P(B \cap C \cap D)+P(A \cap B \cap D)-P(A \cap B \cap C \cap D) = 0.72+0.72+0.608+0.77-0.72^2-0.72*0.608-0.72*0.77-0.72*0.608-0.72*0.77-0.608*0.77+0.72^2*0.608+0.72*0.608*0.77+0.72*0.608*0.77+0.72^2*0.77-0.72^2*0.608*0.77=0.993$

I don't think this is right, since the odds look really high and I'm sure there has to be a cleaner way to approach this problem.

Answer 1

If you're looking for a cleaner way to approach the last problem, break it up into two cases: when the $CD$ path is open, and when the $CD$ path is closed.

1. If the $CD$ path is open, we can treat $\{C,D\}$ as a single location. The probability that we get from Woodstock to $\{C,D\}$ is $1 - 0.1\cdot 0.2 = 0.98$ ($1$ minus the probability that both paths are closed). The probability that we get from $\{C,D\}$ to Tunbridge is also $0.98$. So the probability that we get from Woodstock to Tunbridge is $0.98^2$.
2. If the $CD$ path is closed, we have two independent routes from Woodstock to Tunbridge: via $C$, and via $D$. Each one is open with probability $0.9 \cdot 0.8 = 0.72$, and closed with probability $0.28$. So the overall probability that we can get from Woodstock to Tunbridge is $1-0.28^2$.

Since the $CD$ path is open with probability $0.95$, then we can combine these two cases into a final probability of $$ 0.95 \cdot (0.98^2) + 0.05 \cdot (1 - 0.28^2) = 0.95846. $$

---

This "deletion-contraction" method generalizes to arbitrary problems of this type: when we have a graph $G$ with a probability $p_e$ for each edge $e$ and we want to know the probability that there is an $s,t$-path for some vertices $s$ and $t$. Rather than use inclusion-exclusion over all paths (which may be numerous and hard to find), choose an edge $e$ and consider the two possibilities. When $e$ is absent, we are solving the same problem in the simpler graph $G-e$. When $e$ is present, we are solving the same problem in the simpler graph $G\cdot e$ (where we combine the endpoints of $e$ into one vertex).

Answer 2

It is fine to use Inclusion/Exclusion, but your implementation is wrong. For instance, you are incorrect to substitute $0.72 \times 0.608$ for $P(A \cap C)$, because the rule $P(E \cap F) = P(E) P(F)$ holds only if the events $E$ and $F$ are independent. Events $C$ and $A$ are not independent because both require that the line segment $WC$ is open. The only pair of your events $A$, $B$, $C$, and $D$ that is independent is the pair consisting of $A$ and $B$. No other pair is independent, nor is any collection of three or more of the events.

To remedy this, we note that $$P(A \cap C) = P(\text{WC open and CT open and CD open and DT open}) = 0.8 \times 0.9 \times 0.95 \times 0.8 = 0.5472.$$ and $$P(A \cap D) = P(\text{WC open and CT open and CD open and WD open}) = 0.8 \times 0.9 \times 0.95 \times0.9 = 0.6156.$$ Similar analysis shows that $$P(B \cap C) = 0.5472$$ and $$P(B \cap D) = 0.6156.$$ Meanwhile, the intersection of $C$ and $D$ requires that all line segments are open, which occurs with probability $$P(C \cap D) = 0.8^2 \times 0.9^2 \times 0.95 = 0.49248.$$ The intersection of three or more events also requires that all line segments are open. Altogether, this gives $$ \begin{split} P(A \cup B \cup C \cup D) &= 0.72 + 0.72 + 0.608+0.7695 \\ & \, \, \, \, \, \, \, \, - 0.72^2 - 2 \times 0.5472 - 2 \times 0.6156 - 0.49248\\ & \, \, \, \, \, \, \, \, + 4 \times 0.49248 \\ & \, \, \, \, \, \, \, \, - 0.49248 \\ & = 0.95846 \end{split} $$ This final answer is slightly less than your original answer, but not by much. However, it is not unrealistic that there is a high probability of being able to travel from Woodstock to Tunbridge, because there are four possible paths, each of which is open with a pretty high probability.