Hosted by The Math Forum

# Random Walks

MacPoW Home ||  Forum PoWs ||  Teachers' Place ||  Student Center ||  Search MacPoW

Alice and Bob live at opposite corners of the illustrated grid. Each departs for the house of the other at the same time, walking along the grid at the same speed, and choosing one of the many shortest-length paths uniformly at random. What is the probability that they will meet en route?

You can assume that Alice and Bob each have a stack of maps. On each map one of the possible shortest routes is highlighted, and the stack consists of all possible such maps. Before leaving, Alice and Bob each choose one of the maps at random, with equal probability, and they follow the indicated route.

The exact wording from the source is:

"..independently choosing a path to the other's house with uniform distribution out of all possible minimum-distance paths (that is, all min-distance paths are equally likely)"

It is interesting to note that the problem is different, and I believe you get a different answer, if Alice and Bob randomly choose, with equal probability, between going East and North (or West and South) when they have such a choice.

```                                  ------------------Bob
|         |         |
|         |         |
|         |         |
|         |         |
---------------------
|         |         |
|         |         |
|         |         |
|         |         |
--------------------------------------------------
|        |         |         |         |         |
|        |         |         |         |         |
|        |         |         |         |         |
|        |         |         |         |         |
--------------------------------------------------
|        |         |         |
|        |         |         |
|        |         |         |
|        |         |         |
------------------------------
|        |         |         |
|        |         |         |
|        |         |         |
|        |         |         |
------------------------------
|        |         |         |
|        |         |         |
|        |         |         |
|        |         |         |
Alice-------------------------

```
Source: International Math Talent Search Round 34, Mathematica and Informatics Quarterly, Feb. 2000.