Given is the graph below. Starting on the leftmost vertex x, a bug moves randomly on it. How likely is it that it reaches the rightmost vertex y in the minimum number (7) of moves?
Note that the levels of a given distance to x are ordered in columns separated by the green lines.
How do we detect which vertex to color red? We detect the red vertices in level 7, then in level 6, then in level 5, and so on. In level 7, y is red. In level 6, a vertex is red if it has a red neighbor in level 7. In level i, a vertex is red if it has a red neighbor in level i+1.
Now, what is the probability that the bug goes from y to x in 7 steps? Of course, we could redraw the graph (the levels are different now) and analyze the question using the same tool. If you are interested in questions like this, go to the page on random walks, which may also be used to answer the question.
Given is this graph (see here for information on the context).The probability for success for the bug is 1/4686.
Without reversing moves we get 1/533.
Let's do another example (see
here for the context). The probability we get is 1/15,116,544
Erich Prisner 2002-2004