Our (software dev) team is working with a system that can be represented as a DAG with a starting node and an ending node. Our goal is to ensure a message can flow from the start vertex to the stop vertex.
We have a probability associated with each vertex in the DAG which represents the likelihood that the node will be able to propagate the message to its children. We want to calculate the likelihood that at least 1 successful path exists exists between the start node and the stop node.
What we've attempted (feel free to skip reading this part because we don't know what we're doing):
I know that it's probably a good idea to reduce this problem by replacing "nodes with probabilities" to edges with weights, but I'm not sure what problem it reduces to.
Suppose we have a network defined as the following:
Start node children: A,C
A children: B
B children: end node
C children: B,D
D children: end node
Probabilities:
(A,.9)
(B,.8)
(C,.2)
(D,.5)
There are three paths from start to end: SABT,SCBT,SCDT. Call these E1,E2,E3, respectively
The probability that each of these runs successfully is then just the product of the probabilities on the path, ie P(E1)=.9*.8=.72, P(E2)=.2*.8=.16, P(E3)=.2*.5=.1
We think we're looking for P(E1 ∪ E2 ∪ E3), and since the paths are dependent on nodes going down, we think that our formula is:
P(E1 ∪ E2 ∪ E3) = P(E1) + P(E2) + P(E3) - P(E1 ∩ E2) - P(E1 ∩ E3) - P(E2 ∩ E3) + P(E1 ∩ E2 ∩ E3)
our final P(E1 ∪ E2 ∪ E3) was .756
for example:
P(E2 ∪ E3) = P(E2) + P(E3) - P(E2 ∩ E3) = .16 + .10 - (.2*.8.*.5) = .18
Is this the right approach? And if so, is there a better way to calculate this probability? Seems like the way we're doing things, the calculations grow exponentially as the number of paths grow.
Your calculations seems correct.
This problem is known as the reliability (or network reliability, graph reliability) problem and is notably difficult (it is #P-complete)
This problem is easy if the underlying graph is series-parallel (see Reliability block diagram)