P\'olya considered random walkers in one, two, and three dimensions. In one dimension, he envisioned the walker on a very long street. At each intersection the walker flips a fair coin to decide which direction to walk next. In two dimensions, the walker is walking on a grid of streets, and at each intersection he chooses one of the four possible directions with equal probability. In three dimensions, the walker moves on a three-dimensional grid, and at each intersection there are now six different directions that the walker may choose, each with equal probability.
(a) Write a program to simulate a random walk in one dimension starting at 0. Have your program print out the lengths of the times between returns to the starting point (returns to 0). See if you can guess from this simulation the answer to the following question: Will the walker always return to his starting point eventually or might he drift away forever?
(b) The paths of two walkers in two dimensions who meet after n steps can be considered to be a single path that starts at (0,0) and returns to (0,0) after 2n steps. This means that the probability that two random walkers in two dimensions meet is the same as the probability that a single walker in two dimensions ever returns to the starting point. Thus the question of whether two walkers are sure to meet is the same as the question of whether a single walker is sure to return to the starting point.
Write a program to simulate a random walk in two dimensions and see if you think that the walker is sure to return to (0,0). If so, P\'olya would be sure to keep meeting his friends in the park. Perhaps by now you have conjectured the answer to the question: Is a random walker in one or two dimensions sure to return to the starting point? P\'olya answered this question for dimensions one, two, and three. He established the remarkable result that the answer is yes in one and two dimensions and no in three dimensions.
(c) Write a program to simulate a random walk in three dimensions and see whether, from this simulation and the results of (a) and (b), you could have guessed P\'olya's result.