Probability that node A is connected to another node Example: I have nodes A, B and C.
A is connected to B and C.
B is also connected to C.  
The link between two nodes have a probability to fail.
For the link between A and B, the probability is pAB
Between A and C, it's pAC
B and C, pBC
The probability that A is connected to C is $P = (1-pAC) + pAC(1-pAB)(1-pBC)$
Question:
What is the probability P{A is connected to E} for this graph:

Please write the steps and explain how you find the probability.
Edit:
The only part I have to go on is the A-B-C graph.
The problem is that the graph on the picture has 4 routes from A to E, out of those two have the length of 3 steps and two have 4 steps.
I don't know what to do when that situation arises.
Consider this graph: 

Is it, 
\begin{align}
P\{A\ to\ D\} = &(1-pAB)(1-pBD) + pAB(1-pAC)(1-pCD) +  \\
              &pBD(1-pAC)(1-pCD) + pAC(1-pAB)(1-pBD) +  \\
              &pCD(1-pAB)(1-pBD) + pAB(pBD)(1-pAC)(1-pCD) +  \\
              &pAC(pCD)(1-pAB)(1-pBD)
\end{align}
?
Or it it simply just $P\{A\ to\ D\} = (1-pAB)(1-pBD) + pAB*pBD(1-pAC)(1-pCD)$?
I don't know how to think when there are routes of the same length, or when there is a straight route with a node inbetween, like A - B - C instead of just A - C.
Also, what is this called? I've been trying to solve the graph for 3 days now to no avail. 
 A: The easiest way to solve this problem is via the law of total probability.
Suppose the $C$-$D$ link has failed. Then there are only two paths
from $B$ to $E$, and so there is a connection from $B$ to $E$ as long
as at least one of the paths $B$-$C$-$E$ and $B$-$D$-$E$ has both
links working.  Now, the probability that both links on the
$B$-$C$-$E$ path are working is $V_{BC}V_{CE}$ where $V_{XY}$ is the
probability that the link from $X$ to $Y$ is Viable, and similarly,
$V_{BD}V_{DE}$ is the probability that the $B$-$D$-$E$ path is working.
Hence, 
$$P(B\to D \mid C\text{-}D~\text{failed}) = V_{BC}V_{CE}+V_{BD}V_{DE} - V_{BC}V_{CE}V_{BD}V_{DE}.\tag{1}$$
If the above puzzles you, ponder on the result that 
$P(G\cup H) = P(G)+P(H)-P(G\cap H)$.
Suppose the $C$-$D$ link is Viable. Then, there is a path from $B$ to $D$
exactly when at least one of the links $B$-$C$ and $B$-$D$ is Viable
AND at least one of $C$-$E$ and $D$-$E$ is Viable.  Thus,
$$P(B\to D \mid C\text{-}D~\text{working})=
\left(V_{BC}+V_{BD}- V_{BC}V_{BD}\right)\left(V_{CE}+V_{DE} 
- V_{CE}V_{DE}\right).\tag{2}$$
Now, combine $(1)$ and $(2)$ together using the law of total probability
and then add on what happens with link $A$-$B$, and you are done.
A: Here are my thoughts on case with ABCD, trying to give insights for the more general cases.
They are two important things in your problem


*

*counting the number of different paths

*being able to understand how to count them, i.e. to weight them.


In the ABCD case, there are two routes you can take : ABD ou ACD. 


*

*Assume we start from ABD path. Then, the probability that one can reach D from A is $(1-p_{AB})(1-p_{BD})$.

*Then there also is the path with ACD, the probability that it exists being $(1-p_{AC})(1-p_{CD})$.

*If we just add these two probabilities, first one can check that we can have a probability greater than one, which is never a good sign, second there are a cases we count two times : one path interests us only if the other is not taken. If we assume as we did that we started with ABD, then the ACD path adds to our problem only if the path ABD dos not work, that is either when AB is broken ($p_{AB}$) or when AB is here but BD is broken ($(1 - p_{AB})(p_{BD})$)


Therefore I arrive at 
$$
\mathbb{P}(A->D) = (1-p_{AB})(1-p_{BD}) + (p_{AB} + (1 - p_{AB})p_{BD})(1-p_{AC})(1-p_{CD})
$$
Note that you should (and I think it is the case) get the same result if you start by the path ABD. In this particular case, one can also check that if you develop the formula, B and C play similar roles.
To calculate that more generally, I think you should try it in matrix form with an adjacency matrix, but I will not look at it for now.
A: For your graph:
Write an adjacency matrix $A$ whose coefficients are $1-p_{AB}$, etc. rather than 1.  Set $A_{5,5}$ to 1.  Then the answer is $A^4 \begin{bmatrix}1 \\ 0 \\ 0 \\ 0 \\ 0\end{bmatrix}$.
In general, there is an elegant combinatorics solution.
