I enjoy problems whose solutions make use of things I know about. That’s part of the reason why I found my research topic stimulating; it alluded to connections between different fields of mathematics, and borrowed results with which an undergraduate student would be familiar. It’s for this reason (and the fact that my other research interest is probability and stochastic processes) that I want to talk about the following fun problem:
Kent Funesic starts at the (fictional) town of Pergory. He jumps 1 mile east with probability p > 1/2, and jumps 1 mile west with probability 1 – p. If Kent keeps jumping forever, what is the expected number of times he will jump back into Pergory?
The answer is surprisingly simple… Let’s first notice that it’s obvious he’s eventually going to stay east of Pergory forever, drifting further and further right. So that naturally leads to considering the probability a path of length 2m lies entirely east of Pergory if it starts and finishes there.
But this is directly related to the number of Dyck paths of length 2m; recall that a Dyck path is a series of up and down steps that finishes at and never dips below the starting height.
Using the fact that the number of Dyck paths of length 2m is just the mth Catalan number, i.e. (2m)!/(m!(m+1)!), we can sum over all possible path-lengths and use the generating function for the Catalan numbers to get that the probability his path forever stays east of Pergory is simply 1 – (2 – 2p) = 2p – 1.
Now it’s just a matter of computing the derivative of a geometric series to get the answer; partitioning his path into n visits to Pergory and summing over all n, we get that the expected number of jumps back into Pergory is (2 – 2p)/(2p – 1). How simple…
It becomes clear from this elegant formula that as p gets closer to 1/2, the expected number of jumps back to Pergory explodes. Indeed, in this case it is true that no matter how far Kent drifts away from Pergory, he will eventually return with probability 1!
Miles Koumouris
The University of Melbourne
