Season 10 Episode 3
Imagine a counter that starts at zero and, each second, either goes up by one or down by one. It'll stop at 10 or minus 10 or when you stay stop. Can you play strategically to cut your losses, or to quit while you're ahead?
Further Reading
Random Walks
In episode 3 of OOMC (four years ago!) we had another problem to do with random walks (with a frog jumping on lily pads); Probability with Lauren.
The question in that episode is as follows. Imagine a counter that starts at zero and, each second, either goes up by one or down by one. What’s the probability that it will return to zero at some point?
This removes the stopping condition at \(\pm 10\), and it’s related to the discussion we had at the end of this episode about unbounded random walks.
For a random walk on the number line, the answer is that the probability is 1. We say that the sequence “almost surely” returns to the origin.
Technical note about “almost”! There’s something tricky going on here; although there are infinitely many sequences that do not return to the origin (imagine a sequence that always increases, for example, or one that repeatedly takes two steps forwards then one step back), they are assigned a probability of zero. It’s a bit like how in geometry, a line drawn on a plane is considered to have no area. There are points on the line, but not that many of them compared to all the points that make up the plane. If you’ve heard of “different sizes of infinity” then that’s a related idea, but note that cardinality on its own is not enough to describe what’s going on here because the line and the plane both contain uncountably many points (moreover, they have the same cardinality). Instead, we really need something called Measure Theory if we’re going to properly understand how to assign probabilities to an infinite set of possible outcomes. There’s a third-year course at Oxford on this, linking area and measurement and probability.
If you generalise the random walk to two-dimensional motion (consider points in the \(xy\)-plane where both coordinates are integers and move in one of the four cardinal directions chosen uniformly at random), then the probability that you will eventually return to the origin is 1. There are some nice pictures of what these random walks might look like on Wikipedia.
It’s then perhaps surprising that in 3D, the probability that you return to the origin is not 1, it’s about 34%.
Sometimes I think that three dimensions is not very many, and sometimes I think that it’s plenty.
Recurrence Relations
I’ll copy a recommendation from that previous episode of OOMC; to solve problems like this, it is helpful if we can solve recurrence relations. Here’s a textbook with a method for solving a large class of recurrence relations.
I’m linking to a textbook rather than giving you a simplified explanation because I think that at least some of you just want to see the literal technique that you might be taught at university. It's a tough read though; reading maths textbooks is a huge amount of work, and usually involves getting stuck or confused, stopping, going back to try to understand something earlier, then coming back and thinking again about the bit that didn’t make sense.
Random Walk Probabilities
We saw that, for a random walk starting at zero that will stop at either \(-a\) or at \(b\), with \(a\) and \(b\) both positive integers, the probability that the random walk reaches \(-a\) before it reaches \(b\) is \(\frac{a}{a+b}\). Armed with this probability, we can ask other questions about games with random walks.
Imagine a counter that starts at zero and, each second, either goes up by one or down by one. It'll stop at 10 or minus 10 or when you stay stop. Suppose that your reward when the counter stops at some number \(n\) will be \(n^3\). So for positive \(n\) that’s quite a large reward, especially if you wait for larger numbers, but for negative \(n\) it’s actually not a reward at all, it’s a loss, and a large loss if you let the number run too low. This doesn’t change the probabilities above, but it does change the expected reward.
Can you choose \(a\) and \(b\) like we did in the episode, so as to maximise your expected reward?
If you want to get in touch with us about any of the mathematics in the video or the further reading, feel free to email us on oomc [at] maths.ox.ac.uk.