In a previous post I defined the network reliability problem. Briefly, we are given a directed graph whose edges are labelled with probabilities, which we can think of as giving the likelihood of a message successfully traversing a link in a network. The problem is then to compute the probability that a message will successfully traverse the network from a given source node to a given target node.
Several commenters pointed out the connection to Bayesian networks. I think they are right, and the network reliability problem is a very special case of Bayesian inference. However, so far this hasn’t seemed to help very much, since the things I can find about algorithms for Bayesian inference are either too general (e.g. allowing arbitrary functions at nodes) or too specific (e.g. only working for certain kinds of trees). So I’m going to put aside Bayesian inference for now; perhaps later I can come back to it.
In any case, Derek Elkins also made a comment which pointed to exactly what I wanted to talk about next.
Star semirings and path independence
Consider the related problem of computing the reliability of the single most reliable path from 
Now, given a graph 
In fact, as shown by O’Connor and Dolan, there are many algorithms that can be recast as computing the star of a matrix, for an appropriate choice of semiring: for example, (reflexive-)transitive closure; all-pairs shortest paths; Gaussian elimination; dataflow analysis; and solving certain knapsack problems. One might hope that there is similarly an appropriate semiring for the network reliability problem. But I have spent some time thinking about this and I do not know of one.
Consider again the simple example given at the start of the previous post:
For this example, we computed the reliability of the network to be 
Inspired by this example, one thing we might try would be to define operations 
Graph reduction
We can at least compute the reliability of series-parallel graphs whose terminals correspond with
- If
consists of a single edge, return that edge’s probability.
- Otherwise,
- If
- If
- If
In the second case, having a parallel composition of graphs ensures that there are no shared edges between them, so
Of course, many interesting graphs are not series-parallel. The simplest graph for which the above does not work looks like this:
Suppose all the edges have probability 
More in a future post!
References
Dolan, Stephen. 2013. “Fun with Semirings: A Functional Pearl on the Abuse of Linear Algebra.” In ACM SIGPLAN Notices, 48:101–10. 9. ACM.
Lehmann, Daniel J. 1977. “Algebraic Structures for Transitive Closure.” Theoretical Computer Science 4 (1). Elsevier: 59–76.
O’Connor, Russell. 2011. “A Very General Method for Computing Shortest Paths.” http://r6.ca/blog/20110808T035622Z.html.
Penaloza, Rafael. 2005. “Algebraic Structures for Transitive Closure.” http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.71.7650.
blog :: Brent -> [String] 
I made it $\frac{169}{729}$ by just bashing out a decision tree, but I’m looking forward to reading about the right way to do it…
If I’m not missing something the formula is
(ab&ac) & (bd|cd) + (ab&!ac) & (bd | bc&cd)) + (!ab&ac) & cdwhich should be 55/243?
I believe the discrepancy is due to interpretation of the puzzle statement. You are right if for every edge e with weight w, that edge works with probability w. I think the correct interpretation (from Brent’s commentary) is that whenever a node without outgoing edges e_i, w_i receives a packet, it forwards a packet onto e_i with probability w_i.
My extra 4/729 is from the possibility that packets are forwarded a->b->c->d and a->c, but the a->c packet is dropped. Your term (bd|cd) conflates this case with a->b->c->d and a->c->d.
Hmm, Brent also says “The way I have defined the problem, that doesn’t matter”. Is that not true then?
By factoring theorem,
Pr(a->d)= Pr(a->d| work)*Pr( work)+ Pr(a->d| fail)*Pr( fail)
There are four parts to be computed:
1. Pr( work)=1/3.
2. Pr( fail)=2/3.
3. Pr(a->d| work) is the reliability of the serial-parallel graph which nodes b, c are merged into one node and its value can be computed as {1/3+1/3-1/3*1/3}^2=25/81.
4. Pr(a->d| fail) is the reliability of the serial-parallel graph which edge is removed and its value can be computed as 1/9+1/9-1/9*1/9=17/81.
Thus, Pr(a->d)=(1/3)*(25/81) + (2/3)*(17/81)= 59/243.
Sorry! I made a wrong computation. Since nodes b and c can be merged as one node only if both b->c and c->b work.
Same result as Sjoerd, with a slightly different procedure.
Let XY denote the event that a message passes from node x to node y. Event AD can be written in disjunctive normal form in terms of events for adjacent nodes
AD = (AB ∩ BD) ∪ (AB ∩ BC ∩ CD) ∪ (AC ∩ CD)
(In contrast to the formula by Sjoerd, there are no complements but the disjunctions are not disjoint)
Using the inclusion-exclusion principle, a generalized version of the formula P(N ∪ M) = P(M) + P(N) – P(M ∩ N), the probability for AD is
P(AD) = P(AB ∩ BD) + P(AB ∩ BC ∩ CD) + P(AC ∩ CD) – P((AB ∩ BD) ∩ (AB ∩ BC ∩ CD)) – P((AB ∩ BD) ∩ (AC ∩ CD)) – P((AB ∩ BC ∩ CD) ∩ (AC ∩ CD)) + P((AB ∩ BD) ∩ (AB ∩ BC ∩ CD) ∩ (AC ∩ CD)) =
P(AB ∩ BD) + P(AB ∩ BC ∩ CD) + P(AC ∩ CD) – P(AB ∩ BC ∩ BD ∩ CD) – P(AB ∩ AC ∩ BD ∩ CD) – P(AB ∩ AC ∩ BC ∩ CD) + P(AB ∩ AC ∩ BC ∩ BD ∩ CD)
and since the events are independent (adjacent nodes!), the result is
P(AD) = 2(1/3)^2 + (1/3)^3 – 3(1/3)^4 + (1/3)^5 = 55/243
Trying a slightly different approach (which unfortunately requires G to be acyclic), I am getting a different value. In order to deal with the possibility of nodes receiving several messages, I associate explicit distributions on numbers of messages with each node and edge:
At a, this distribution is (0,1) since we have 0 messages with probability 0 and 1 message with probability 1.
For each edge, multiply the vector on the source node with the matrix M whose coefficient $m_{i,j}$ represents the probability that i out of j messages survive; we thus get (2/3,1/3) on both ab and ac.
For each node, the distribution is the convolution of the incoming edges. So for b, we also get the distribution (2/3,1/3); then (8/9,1/9) on bc and (16/27,10/27,1/27) for c (the coefficients in the convolution being 8/27=2/3*8/9, 10/27=2/3*1/9+1/3*8/9, 1/27=1/3*1/9).
On edge bd, we again have (8/9,1/9) and on cd, (208/243,34/243,1/243). The final convolution at d is nasty, but we only need the first coefficient, 1664/2187, which is the probability that no messages arrive. The reliability then is 523/2187.
I noticed too late that this whole approach can be described much more neatly in terms of polynomials; given a distribution d on {0,…,n}, we represent d using the polynomial f(x)=d(0)+d(1)x+…+d(n)x^n. The approach can then be described as follows in terms of polynomials f_v and f_e for all nodes v and edges e:
– For the initial node a, f_a(x) = x.
– For any edge e out of a node v with reliability p, f_e(x) = f_v(p*x + (1-p)).
– For any node v with incoming edges e_1,…,e_n, f_v(x) = f_{e_1}(x)*…*f_{e_n}(x).
The reliability is then 1 – f_d(0), where d is the target node.
In principle, this idea could also be applied for graphs with cycles, but then you would need to compute a fixpoint which will consist of power series rather than polynomials.