Multiple ways to transition a graph I want to calculate the probability of reaching nodes in a graph, where multiple paths are possible.
To be more concrete. I have the following graph:
V = (A,B,C,D,E)
E = (AB, AC, BD, CD, BE, CE, DE), which are weighted with transition probabilities Pab, Pac, ... Note: Pab denotes the probability of reaching B, when going from A to B. Pab + Pac doesn't equal 1, as whatever starts in A can either go to B or to C or to both or to neither of the two.
I start in A. With Pab, B is set to "reached". With Pac, C is set to "reached". If B is set to "reached", with Pbd, D is set to "reached" etc. Hence the following algorithm is performed:
A<-1
B<-0
C<-0
D<-0
E<-0
if (runif(1) < Pab) B<-1
if (runif(1) < Pac) C<-1
if (B==1 & runif(1) < Pbd) D<-1
if (C==1 & runif(1) < Pcd) D<-1
if (B==1 & runif(1) < Pbe) E<-1
if (C==1 & runif(1) < Pce) E<-1
if (D==1 & runif(1) < Pde) E<-1
My question is, with which probability do I reach E?
My intuitive approach was calculating recursively
$$
P(X) = 1 - \prod_{Y \text{ in the set of precursors of } X} (1 - p_{YX}) * P(Y) + (1 - P(Y))
$$
but this overestimates P(E) as apparently some dependent probabilities aren't taken into account.
I feel as if this problem should have a name and simply has to be phrased differently to obtain a solution, but I don't know how. Your help would be very much appreciated!
Many thanks!
 A: I assume that the edges are directed, that is given only $p_{XY}$ but not $p_{YX}$, the probability to reach $Y$ from $X$ is  $p_{XY}$, but the probability to reach $X$ from $Y$ is  zero. In your question we have $X$ is lexicographically smaller than $Y$ for all given $p_{XY}$. So, given the node $A$ is already reached, we can consecutively calculate values $P(\chi_B, \chi_C,\dots)$, where $\chi_X=1$ indicates that a node $X$ was reached, and $\chi_X=0$ indicates that the node $X$ was not reached.
$P(1,0)=1-p_{AB}$
$P(1,1)=p_{AB}$
$P(1,0,0)=(1-p_{AB})(1-p_{AC})$
$P(1,0,1)=(1-p_{AB})p_{AC}$
$P(1,1,0)=p_{AB}(1-p_{AC})$
$P(1,1,1)=p_{AB}p_{AC}$
$P(1,0,0,0)=(1-p_{AB})(1-p_{AC})$
$P(1,0,0,1)=0$
$P(1,0,1,0)=(1-p_{AB})p_{AC}(1-p_{CD})$
$P(1,0,1,1)=(1-p_{AB})p_{AC}p_{CD}$
$P(1,1,0,0)=p_{AB}(1-p_{AC})(1-p_{BD})$
$P(1,1,0,1)=p_{AB}(1-p_{AC})p_{BD}$
$P(1,1,1,0)=p_{AB}p_{AC}(1-p_{BD})(1-p_{CD})$
$P(1,1,1,1)=p_{AB}p_{AC}(p_{BD}+p_{CD}- p_{BD}p_{CD})$
$P(1,0,0,0,1)=0$
$P(1,0,0,1,1)=0$
$P(1,0,1,0,1)=(1-p_{AB})p_{AC}(1-p_{CD})p_{CE}$
$P(1,0,1,1,1)=(1-p_{AB})p_{AC}p_{CD}(p_{CE}+p_{DE}- p_{CE}p_{DE})$
$P(1,1,0,0,1)=p_{AB}(1-p_{AC})(1-p_{BD})p_{BE}$
$P(1,1,0,1,1)=p_{AB}(1-p_{AC})p_{BD}(p_{BE}+p_{DE}- p_{BE}p_{DE})$
$P(1,1,1,0,1)=p_{AB}p_{AC}(1-p_{BD})(1-p_{CD})(p_{BE}+p_{CE}- p_{BE}p_{CE})$
$P(1,1,1,1,1)=p_{AB}p_{AC}(p_{BD}+p_{CD}- p_{BD}p_{CD})(1-(1-p_{BE})(1-p_{CE})(1-p_{DE}))$.
So $P(E)$ is the sum of the last eight (or six) values. 
