The Randy Hall Problem
Pick one of three doors, and then swap to a neighboring door with a specific probability. If you do this many times, can this ultimately lead to a random selection?
Welcome to Fiddler on the Proof, the spiritual successor to FiveThirtyEight’s The Riddler column.
Every Friday morning, I present mathematical puzzles intended to challenge and delight you. Most can be solved with careful thought, pencil and paper, and the aid of a calculator. The “Extra Credit” is where the analysis typically gets hairy, or where you might turn to a computer for assistance.
I’ll also give a shoutout to 🎻 one lucky winner 🎻 of the previous week’s puzzle, chosen randomly from among those who submit their solution before 11:59 p.m. the Monday after puzzles are released. I’ll do my best to read through all the submissions and give additional shoutouts to creative approaches or awesome visualizations, the latter of which could receive 🎬 Best Picture Awards 🎬.
This Week’s Fiddler
You are a producer on a game show hosted by Randy “Random” Hall (no relation to Monty Hall). The show has three doors labeled 1 through 3 from left to right, and behind them are various prizes.
Contestants pick one of the three doors at which to start, and then they press an electronic button many, many times in rapid succession. Each time they press the button, they either stay at their current door or move to an adjacent door. If they’re at door 2 and move to an adjacent door, that new door will be 1 or 3 with equal probability.
Randy has decided that when a contestant presses the button while at door 2, there should be a 20 percent chance they remain at door 2.
As the producer, you want the chances of a contestant ultimately winding up at each of the three doors to be nearly equal after many button presses. Otherwise, mathematicians will no doubt write you nasty letters complaining about how your show is rigged.
If a contestant presses the button while at door 1 (or door 3), what should the probability be that they remain at that door?
This Week’s Extra Credit
Randy has an updated suggestion for how the button should behave at door 2. What hasn’t changed is that if a contestant is at door 2 and moves to an adjacent door, that new door will be 1 or 3 with equal probability.
But this time, on the first, third, fifth, and other odd button presses, there’s a 20 percent the contestant remains at door 2 (if they happen to be there). On the second, fourth, sixth, and other even button presses, there’s a 50 percent chance the contestant remains at door 2 (again, if they happen to be there).
Meanwhile, the button’s behavior at doors 1 and 3 should in no way depend on the number of times the button has been pressed.
As the producer, you want the chances of winding up at each of the three doors—after a large even number of button presses— to be nearly equal.
If a contestant presses the button while at door 1 (or door 3), what should the probability be that they remain at that door?
Making the ⌊Rounds⌉
There’s so much more puzzling goodness out there, I’d be remiss if I didn’t share some of it here. This week, I’m sharing a timely article from The New York Times featuring Moon Duchin, who has extensively studied the mathematics of gerrymandering. There’s also some good stuff in there on recombination algorithms and ranked choice voting, so check it out!
Want to Submit a Puzzle Idea?
Then do it! Your puzzle could be the highlight of everyone’s weekend. If you have a puzzle idea, shoot me an email. I love it when ideas also come with solutions, but that’s not a requirement.
Standings
I’m tracking submissions from paid subscribers and compiling a leaderboard, which I’ll reset every quarter. All correct solutions to Fiddlers and Extra Credits are worth 1 point each. Solutions should be sent prior to 11:59 p.m. the Monday after puzzles are released. At the end of each quarter, I’ll 👑 crown 👑 the finest of Fiddlers. If you think you see a mistake in the standings, kindly let me know.
Last Week’s Fiddler
Congratulations to the (randomly selected) winner from last week: 🎻 Dave Moran 🎻 from Ann Arbor, Michigan. I received 85 timely submissions, of which 70 were correct—good for an 82 percent solve rate.
Last week, you and your opponent were beginning a best-of-seven series, meaning the first team to win four games would win the series. Both teams were evenly matched, meaning each team had a 50 percent chance of winning each game, independent of the outcomes of previous games.
As the team manager, you were trying to motivate your team as to the criticality of the first game in the series (i.e., “Game 1”). You specifically wanted to educate them regarding the “probability swing” coming out of Game 1—that is, the probability of winning the series if they won Game 1 minus the probability of winning the series if they lost Game 1. (For example, the probability swing for a winner-take-all Game 7 was 100 percent.)
What was the probability swing for Game 1?
Suppose your probability of winning the series, given that you have won A games to date and your opponent has won B games, is p(A,B). Using this notation, this puzzle was then asking you to compute p(1,0) − p(0,1). But what were p(1,0) and p(0,1)? To find out, you could work backwards!
You knew that p(4,0), p(4,1), p(4,2), and p(4,3) were all equal to 1. In other words, given that you’ve already won four games in the best-of-seven series, your probability of winning was 1, or 100 percent. Similarly, p(0,4), p(1,4), p(2,4), and p(3,4) were all 0.
Now for the working backwards: What was p(3,3), your probability of winning the series when it was tied three games apiece? Intuitively (and from symmetry), you knew this had to be 50 percent. But how could you prove this? Well, there was a 50 percent chance you won the game, in which case your probability of winning the series was then p(4,3). And you had a 50 percent chance of losing, in which case the series was then p(3,4). Averaging these two cases, your chances of winning the series were 0.5·p(4,3) + 0.5·p(3,4) = 0.5·1 + 0.5·0 = 0.5, or 50 percent—just as we already figured.
Nevertheless, grinding through these steps illustrated a recursive formula you could use to work backwards and calculate all the other probabilities: p(A,B) = 0.5·p(A+1,B) + 0.5·p(A,B+1). So, given that p(3,3) = 0.5 and p(4,2) = 1, you could next determine that p(3,2) = 0.75. And similarly, p(2,3) = 0.25. In general, it turned out that p(A,B) + p(B,A) = 1.
The following table (rows for A, columns for B) shows the results all the way back to the beginning of the series.
It turned out that p(1,0) = 21/32 and p(0,1) = 11/32, which meant the probability swing for Game 1 was 21/32 − 11/32 = 10/32, which was equivalent to 5/16, or 31.25 percent. Interestingly, Game 2 was guaranteed to have the exact same probability swing, no matter who won Game 1.
Among submissions to the puzzle, the next most popular response (after the correct one) was 1/7. One way to arrive at this was to tabulate the 35 sequences of Ws (for wins) and Ls (for losses) that resulted in your team winning a best-of-seven series. Of these, 20 began with a W, while only 15 began with an L. Thus, the probability swing appeared to be 20/35 − 15/35, which equaled 5/35, or 1/7. However, there was indeed an error in this logic—the (incorrect) assumptoin that all 35 winning sequences were equally likely. However, as an illustration, the probability of winning via WWWW was 1/16 (i.e., 24), whereas the probability of winning via WWWLLLW was 1/128 (i.e., 27). If you were to weight each of these cases by their respective probabilities, you should indeed get the correct answer of 5/16.
Last Week’s Extra Credit
Congratulations to the (randomly selected) winner from last week: 🎻 Jonathan Mooser 🎻 from Mountain View, California. I received 61 timely submissions, of which 46 were correct—good for a 75 percent solve rate.
Instead of a best-of-seven series, now the series was much, much longer. In particular, the first team to win N games would win the series, so technically this was a best-of-(2N−1) series, where N was some very, very large number.
In the limit of large N, what was the probability swing for Game 1 in terms of N?
