In this post, I’d like to present an amusing and off-the-beaten-path solution to the classical “Drunkard’s Walk” problem which at the same time derives the well-known generating function for the Catalan numbers. This solution evolved from a suggestion by my former undergraduate student Stefan Froehlich during a discussion in my Math 4802 (Mathematical Problem Solving) class at Georgia Tech in Fall 2007.
In case you’re not familiar with it, here’s the problem (in a formulation I learned from this book by Frederick Mosteller):
A drunken man standing one step from the edge of a cliff takes a sequence of random steps either away from or toward the cliff. At any step, his probability of taking a step away from the cliff is (and therefore his probability of taking a step toward the cliff is ). What is the probability that the man will eventually fall off the cliff?
What is the probability that two randomly chosen integers have no prime factors in common? In honor of Pi Day, I’d like to explain the surprising answer: .
The hero of this story is Leonhard Euler, who worked out this astonishing connection between prime numbers and through a series of brilliant insights. In the spirit of Euler, I will be rather cavalier about issues of convergence and rigor here, focusing on the key underlying ideas.
A large crowd had gathered in Harvard Square, and I was curious what all the cheering and gasping was about. Working my way through the crowd, I saw a street performer who (according to the handwritten red letters on his cardboard sign) went by the name “Zorn the Magnificent”. He displayed a large orange, borrowed an extremely sharp knife from his assistant, and proceeded to chop the orange into five exotic-looking pieces while standing on one hand. Working with almost unfathomably deft precision, he rearranged the pieces into two oranges, each the same size as the original one. The oranges were given out for inspection and the crowd cheered wildly. I clapped as well — even though I was familiar with the old Banach-Tarski paradox — since it was nevertheless an impressive display of skill and I had never seen it done one-handed before. I heard a man with a long white beard whisper to the woman next to him “He hides it well, but I know that he’s secretly using the Axiom of Choice.” Continue reading