exercise:5299dd9b75: Difference between revisions
From Stochiki
(Created page with "<div class="d-none"><math> \newcommand{\NA}{{\rm NA}} \newcommand{\mat}[1]{{\bf#1}} \newcommand{\exref}[1]{\ref{##1}} \newcommand{\secstoprocess}{\all} \newcommand{\NA}{{\rm NA}} \newcommand{\mathds}{\mathbb}</math></div> Mathematicians have been known to get some of the best ideas while sitting in a cafe, riding on a bus, or strolling in the park. In the early 1900s the famous mathematician George Pòlya lived in a hotel near the woods in Zurich. He liked to wa...") |
No edit summary |
||
| Line 1: | Line 1: | ||
Mathematicians have been known to get some of the best ideas while | |||
best ideas while | |||
sitting in a cafe, riding on a bus, or strolling in the park. In the early | sitting in a cafe, riding on a bus, or strolling in the park. In the early | ||
1900s the famous mathematician George Pòlya lived in a hotel near the | 1900s the famous mathematician George Pòlya lived in a hotel near the | ||
| Line 18: | Line 11: | ||
times, but certainly much too often and I felt embarrassed: It looked as if I was snooping around | times, but certainly much too often and I felt embarrassed: It looked as if I was snooping around | ||
which was, I assure you, not the case.<ref group="Notes" >G. Pòlya, “Two Incidents,” ''Scientists at Work: Festschrift in Honour of Herman Wold,'' ed. T. Dalenius, G. Karlsson, and S. | which was, I assure you, not the case.<ref group="Notes" >G. Pòlya, “Two Incidents,” ''Scientists at Work: Festschrift in Honour of Herman Wold,'' ed. T. Dalenius, G. Karlsson, and S. | ||
Malmquist (Uppsala: Almquist | Malmquist (Uppsala: Almquist & Wiksells Boktryckeri AB, 1970).</ref> | ||
</blockquote> | </blockquote> | ||
This set him to thinking about whether random walkers were destined to meet. | This set him to thinking about whether random walkers were destined to meet. | ||
Pòlya considered random walkers in one, two, and three dimensions. In one dimension, he envisioned the walker on a very long street. At each | Pòlya 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 | intersection the walker flips a fair coin to decide which direction to walk next (see [[exercise:B30e58533f#fig 1.5|Figure a]]). In two dimensions, the walker is walking | ||
next (see | on a grid of streets, and at each intersection he chooses one of the four possible directions with equal probability (see [[exercise:B30e58533f#fig 1.5|Figure b]]). In | ||
on a grid of streets, and at each intersection he chooses one of the four | three dimensions (we might better speak of a random climber), the walker moves on a three-dimensional grid, and at each intersection there are now six | ||
possible directions with equal probability (see | different directions that the walker may choose, each with equal probability (see [[exercise:B30e58533f#fig 1.5|Figure c]]). | ||
three dimensions (we might better speak of a random climber), 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 | |||
(see | |||
The reader is referred to [[guide:Ff217e6881|Random Walks in Euclidean Space]], where this and related problems are discussed. | |||
<ul><li> Write a program to simulate a random walk in one dimension starting at | <ul><li> 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 | 0. Have your program print out the lengths of the times between returns to | ||
the | the starting point (returns to 0). See if you can guess from this simulation 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 | answer to the following question: Will the walker always return to his | ||
starting | starting point eventually or might he drift away forever? | ||
point eventually or might he drift away forever? | |||
</li> | </li> | ||
<li> The paths of two walkers in two dimensions who meet after <math>n</math> steps | <li> The paths of two walkers in two dimensions who meet after <math>n</math> steps | ||
| Line 50: | Line 35: | ||
walker in two dimensions ever returns to the starting point. Thus the | 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 | question of whether two walkers are sure to meet is the same as the question | ||
of | of whether a single walker is sure to return to the starting point. | ||
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 | Write a program to simulate a random walk in two dimensions and see if you | ||
think that the walker is sure to return to <math>(0,0)</math>. If so, Pòlya would be | think that the walker is sure to return to <math>(0,0)</math>. If so, Pòlya would be | ||
sure | sure to keep meeting his friends in the park. Perhaps by now you have conjectured | ||
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 | the answer to the question: Is a random walker in one or two dimensions sure | ||
to | to return to the starting point? Pòlya answered this question for dimensions | ||
return to the starting point? Pòlya answered this question for dimensions | |||
one, two, and three. He established the remarkable result that the answer is | one, two, and three. He established the remarkable result that the answer is | ||
''yes'' in one and two dimensions and ''no'' in three dimensions. | ''yes'' in one and two dimensions and ''no'' in three dimensions. | ||
Revision as of 20:48, 12 June 2024
Mathematicians have been known to get some of the best ideas while sitting in a cafe, riding on a bus, or strolling in the park. In the early 1900s the famous mathematician George Pòlya lived in a hotel near the woods in Zurich. He liked to walk in the woods and think about mathematics. Pòlya describes the following incident:
At the hotel there lived also some students with whom I usually took my meals and had friendly relations. On a certain day one of them expected the visit of his fiancée, what (sic) I knew, but I did not foresee that he and his fiancée would also set out for a stroll in the woods, and then suddenly I met them there. And then I met them the same morning repeatedly, I don't remember how many times, but certainly much too often and I felt embarrassed: It looked as if I was snooping around which was, I assure you, not the case.[Notes 1]
This set him to thinking about whether random walkers were destined to meet.
Pòlya 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 (see Figure a). 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 (see Figure b). In three dimensions (we might better speak of a random climber), 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 (see Figure c).
The reader is referred to Random Walks in Euclidean Space, where this and related problems are discussed.
- 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?
- The paths of two walkers in two dimensions who meet after [math]n[/math] steps can be considered to be a single path that starts at [math](0,0)[/math] and returns to [math](0,0)[/math] after [math]2n[/math] 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 [math](0,0)[/math]. If so, Pòlya 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òlya 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.
- 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òlya's result.
Notes