Over on my other blog I’ve started writing about an interesting but apparently nontrivial problem, which some readers of this blog may find interesting as well. Suppose you have a network of computers with some one-directional wires between them. Each wire is labelled with the probability that a message sent along the wire will successfully reach the computer on the other end; assume that each message sent along a wire succeeds or fails independently of any other messages sent on the same wire. Every time a computer successfully receives a message along an incoming wire, it immediately resends a copy of the message along each outgoing wire. The question is: given some particular network, if we start a message at a particular computer , what is the probability that at least one copy of the message will reach a given target computer ?

As a simple example, can you figure out the probability that a message starting at in the diagram below will successfully reach ?

The solution can be found on my other blog — more to come!

##
About Brent

Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

This seems to be related to Baysian Networks / Graphical Models, which are used to propagate evidence about some random variables throughout a network (graph) where edges encode statistical dependencies…

Yes, someone made a similar comment over on my other blog! I learned a tiny bit about Bayesian networks a long time ago in a class in grad school, but had forgotten about them. It definitely seems related, though I don’t yet understand any of the details well enough to see what light that might shed on the problem.