A fun way to solve this problem is through the use of a Monte Carlo simulation: The code for this is relatively straightforward:
from __future__ import division, print_function from multiprocessing import Pool import sys import numpy as np def simulate(n_kids): # create array to track kids + teacher had_potato = np.zeros(n_kids + 1, dtype=np.bool) pos = n_kids // 2 # move the position by either -1 or 1 until complete while np.sum(had_potato) < n_kids: had_potato[pos] = True pos += np.random.randint(2) * 2 - 1 pos %= had_potato.size return np.argmin(had_potato) if __name__ == "__main__": if len(sys.argv) >= 2: n_kids = int(sys.argv) else: n_kids = 30 # initialize random number generator np.random.seed() # simulate for "enough" times n_sim = int(1e6) pool = Pool(processes=8) winners = pool.map(simulate, [n_kids] * n_sim) probs = np.bincount(winners) / float(n_sim) print("Win probabilities") print(probs)
For each simulation run, I maintain a list of positions that the potato has “touched”. At each iteration, we select a random direction to pass the potato, encoded as -1 or 1. This occurs continuously until only one child (the winner) remains. To speed up the simulation, I used a pool1 of worker processes to run several distinct simulations in parallel. The result of a single run is below:
[ 0.034032 0.03448 0.033488 0.03324 0.0334 0.033272 0.033864 0.03368 0.033328 0.032984 0.032872 0.033432 0.032656 0.032552 0.033936 0. 0.033576 0.033336 0.03268 0.034328 0.033424 0.03312 0.032728 0.033016 0.03312 0.032848 0.033464 0.033424 0.033296 0.033552 0.032872]
Running this for a million iterations, we see that each child actually has the same win probability, i.e. 1/30! The teacher’s position (index 15 in the code above) can never win since that’s the position the potato starts off at.
This problem can also be solved with a Monte Carlo simulation. I took a stab at an analytical solution first, drawing out the graph of bathroom-user interactions as a finite state machine. I got stuck trying to determine the “long-term” probability of each state, though I am fairly certain there is indeed an analytical solution (I seem to have forgotten all the material I learned in my stats classes at Stanford ¯\_(ツ)_/¯). Back to Monte Carlo simulations!
For the time being, we can ignore the fact that the bathroom is occupied exactly 50% of the time – that just helps normalize our prior probabilities. Instead, simply encoding the states of the bathroom (user, sign state, actual state) during each function call is enough:
from __future__ import division, print_function import sys import numpy as np def simulate(prob, state): # make new user if bathroom is unoccupied if not state: state = np.random.random() # update actual state state = not state # update sign state if state < prob: pass elif state < 2 * prob: state = True else: state = state if __name__ == "__main__": if len(sys.argv) >= 2: prob_co = float(sys.argv) else: prob_co = 1 / 3.0 # initialize random number generator np.random.seed() # prob := probability that person totally ignores the sign # prob := probability that person forgets sign upon leaving prob = (1 - prob_co) / 2 # (user type, actual state, sign state) state = [0, False, False] # track # of sign state count and # of times correct n_sign = [0, 0] n_valid = [0, 0] # simulate for "enough" times n_sim = int(1e6) for _ in range(n_sim): simulate(prob, state) n_sign[state] += 1 if state == state: n_valid[state] += 1 print("P(occ|sign_occ) = " + str(n_valid / n_sign)) print("P(vac|sign_vac) = " + str(n_valid / n_sign))
As shown, the
simulate function simply runs one bathroom entrance or exit per iteration, keeping track of the user type between two consecutive runs as necessary. I ran the code with
n_sim = int(1e9) and
xrange instead of
range to avoid unnecessary memory consumption (Python 2 is still my preferred interpreter):
P(occ|sign_occ) = 0.624993716521 P(vac|sign_vac) = 0.749989913933
With some obvious rounding, we arrive at probabilities of 0.625 and 0.75. Hence our final answer of 5/8, 3/4.
1 I have an 4-core processor with hyperthreading, bringing the total “CPU count” to 8, hence
processes=8; you can check yours with
python -c "import multiprocessing; print(multiprocessing.cpu_count())".