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!