This week the #puzzle is: The Randy Hall Problem #probabilities #MontyHall

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?

And for 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 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 that happen to be at door 2, there’s a 20 percent the contestant remains at door 2. On the second, fourth, sixth, and other even button presses that happen to be at door 2, there’s a 50 percent chance the contest remains at door 2.

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?

The Randy Hall Problem

Highlight to reveal (possibly incorrect) solution:

Thoughts:

• Notation:
  • Probability of being at door n after k button presses: p_k(n).
  • Probability of being at door n and moving direction d: p(n,d).
• p(2,stay) = 0.2
• p(2,left) = p(2,right) = 0.4 (0.4 * 2 + 0.2 = 1)
• p(1,stay) = p(3,stay) = x
• p(1,right) = 1 – p(1,stay) = 1 – 0.4 = 0.6
• Assume we have reached a steady state after k presses of the button, so p_k(1) = p_k(2) = p_k(3) = 1/3 and p_k+1(1) = p_k+1(2) = p_k+1(3) = 1/3.
• After 1 press of the button we reach new probabilities:
  • p_k+1(1) = p_k(1) * p(1,stay) + p_k(2) * p(2,left)
  • <=> 1/3 = 1/3 * x + 1/3 * 0.4
  • <=> 1 = x + 0.4
  • <=> 0.6 = x
  • For symmetry reasons, the same calculation works for p_k+1(3).
  • p_k+1(2) = p_k(1) * p(1,right) + p_k(2) * p(2,stay) + p_k(3) * p(3,left)
  • <=> 1/3 = 1/3 * 0.4 + 1/3 * 0.2 + 1/3 * 0.4
  • <=> 1 = 0.4 + 0.2 + 0.4
  • It works.

And for extra credit:

Thoughts:

• p(2,stay,odd) = 0.2
• p(2,left,odd) = p(2,right,odd) = 0.4 (0.4 * 2 + 0.2 = 1)
• p(2,stay,even) = 0.5
• p(2,left,even) = p(2,right,even) = 0.25 (0.25 * 2 + 0.5 = 1)
• p(1,stay) = p(3,stay) = x
• p(1,right) = p(3,left) = 1 – x
• Assume we have reached a steady state after k (even) presses of the button, so p_k(1) = p_k(2) = p_k(3) = 1/3 and p_k+2(1) = p_k+2(2) = p_k+2(3) = 1/3.
• Press the button:
  • p_k+1(1) = p_k(1) * p(1,stay) + p_k(2) * p(2,left,odd)
  • <=> p_k+1(1) = 1/3 * x + 1/3 * 0.4
  • <=> p_k+1(1) = 1/3 * (x + 0.4)
  • p_k+1(2) = p_k(1) * p(1,right) + p_k(2) * p(2,stay,odd) + p_k(3) * p(3,left)
  • <=> p_k+1(2) = 1/3 * (1 – x) + 1/3 * 0.2 + 1/3 * (1 – x)
  • <=> p_k+1(2) = 1/3 * (1 – x + 0.2 + 1 – x)
  • <=> p_k+1(2) = 1/3 * (-2 * x + 2.2)
  • p_k+2(1) = p_k+1(1) * p(1,stay) + p_k+1(2) * p(2,left,even)
  • <=> 1/3 = 1/3 * (x + 0.4) * x + 1/3 * (-2 * x + 2.2) * 0.25
  • <=> 1 = (x + 0.4 ) * x + (-2 * x + 2.2) * 0.25
  • <=> 1 = x² + 0.4 * x – 0.5 * x + 0.55
  • <=> 0 = x² – 0.1 * x – 0.45
  • <=> x = (1+√181)/20 ≈ 0.722681

For illustration of all the probabilities:

pk(1)	pk(2)	pk(3)
0.333333	0.333333	0.333333
pk+1(1)	pk+1(2)	pk+1(3)
0.374227	0.251545	0.374227
pk+2(1)	pk+2(2)	pk+2(3)
0.333333	0.333333	0.333333

odd		direction
door	left	stay	right
1		0.722681	0.277319
2	0.4	0.2	0.4
3	0.277319	0.722681

even		direction
door	left	stay	right
1		0.722681	0.277319
2	0.25	0.5	0.25
3	0.277319	0.722681