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:
Mr Puentes starts at Gloyperville. He gloyps (jumps) 1 mile east with probability p > 1/2, and gloyps 1 mile west with probability 1 – p. If Mr Puentes keeps gloyping forever, what is the expected number of times he will gloyp back into Gloyperville?
The answer is surprisingly simple… Let’s first notice that it’s obvious he’s eventually going to gloyp east of Gloyperville forever, drifting further and further right. So that naturally leads to considering the probability a path of length 2m lies entirely east of Gloyperville 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 to get that the probability his path forever stays east of Gloyperville is simply 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 Gloyperville and summing over all n, we get that the expected number of gloyps back into Gloyperville 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 gloyps back to Gloyperville explodes. This seems to suggest that if gloyping east or west is equally likely, no matter how far Mr Puentes drifts away from Gloyperville, he will eventually return with probability 1!
The University of Melbourne