Copyright 2017-2018 Jason Ross, All Rights Reserved

Here's what you could have won!
A Single Goat - you don't want to win this!

The Original Simulation

In The Monty Hall Problem – A Simulation In JavaScript we wrote a simulation for the Monty Hall Problem. The simulation consisted of two separate iterations through some JavaScript code that recorded the results of the competitor either changing their selection, or keeping their original choice, respectively.

Looking again at this, the idea of there being two iterations through the same code seemed a little excessive and made me start to idly wonder: could this be done in one iteration? This might make the simulation faster, although it would need to be timed to make sure of this, and it doesn’t take long to run anyway. It might improve the integrity of the simulation though. After all, what if something happens during those two iterations so that the odds involved in the second iteration change? It’s not likely but it’s just about possible – maybe the random number generator has a bug or some other strange side effect occurs, and then we can’t be sure what would happen.

If we could get all the information we need from a single game that should eliminate this possibility.

Revisiting The Simulation

Looking closer at the situation that’s being simulated, we can see that all of the information we need is available in every game. Once the contestant has selected one door and the host has opened another, there are only two remaining unopened doors: the one the contestant selected, or the door that nobody has selected or opened yet. Either the contestant can win by keeping their original selection, or by selecting the other door.

We don’t care whether the contestant ACTUALLY wins or loses, just whether they WOULD win if they kept their original selection, or whether they would have to changed their selection.

The Updated Simulation

This script implements the simulation in a single-pass form. It’s based on the original script in the original article, but now just records whether a win would result from keeping the original selection or by changing it. The runSingleSimulationSinglePass function, called from runMontyHallSimulationSinglePass does most of the work:

function chooseRandomIndex() {
	// Choose a random index in the range 0 to 2 inclusive.
	return Math.floor(Math.random() * 3);
}

// No proper enums in JavaScript, so emulate then like this.
var SimulationResultEnum = {
	ORIGINAL_SELECTION_WINS: 1,
	CHANGING_SELECTION_WINS: 2
};

function runSingleSimulationSinglePass() {
	// Run the simulation once. Return what the contestant has to do to win the car. 

	// Decide where the car is hidden. 
	var carIndex = chooseRandomIndex();

	// Let the "contestant" choose a door.
	var userIndex = chooseRandomIndex();

	// Choose a door to open to the contestant. This can't be either:
	// 1. The door with the car behind it
	// or
	// 2. The door that the contestant has chosen
	//
	// To do this, create an array of the possible indexes, then filter
	// out the ones we can't use.
	var validOpenDoorIndexes = [0, 1, 2].filter(value => {
		return (value != carIndex) && (value != userIndex);
	});

	// Now choose a door at random to open to the contestant
	var openedDoorIndex = validOpenDoorIndexes[Math.floor(Math.random() * validOpenDoorIndexes.length)];

	// There are only two doors left now; the original one chosen by the
	// contestant and the one that the host didn't open. The car is
	// behind one of them.

	// There is only one door left that the contestant can choose.
	// This is the door that is neither:
	// 1. The door that the contestant initially chose
	// nor
	// 2. The door that was opened
	var remainingDoorIndex = [0, 1, 2].filter(value => {
		return (value != userIndex) && (value != openedDoorIndex);
	})[0];

	// Now determine whether the contestant would win by keeping their
	// original selection, or by changing to the remaining door.
	if (userIndex == carIndex) {
		return SimulationResultEnum.ORIGINAL_SELECTION_WINS;
	} else if (carIndex == remainingDoorIndex) {
		return SimulationResultEnum.CHANGING_SELECTION_WINS;
	} else {
		throw new Error("Simulation error - the car index could not be found.");
	}
}

class SimulationResults {
	// Excapsulate the results of the single pass simulation in a class
	// simply to formalize the fields used in separate parts of the
	// code.
	constructor() {
		this.originalSelectionWins = 0;
		this.changingSelectionWins = 0;
	}
}

function runMontyHallSimulationSinglePass(timesToRun) {
	// A single-pass implementation of the simulation, which
	// keeps a count of whether each round would have been won
	// by keeping the original selection, or by changing the
	// selection.

	var result = new SimulationResults();
	for (var count = 0; count < timesToRun; ++count) {
		switch (runSingleSimulationSinglePass()) {
			case SimulationResultEnum.ORIGINAL_SELECTION_WINS:
				{++result.originalSelectionWins;
				}
				break;
			case SimulationResultEnum.CHANGING_SELECTION_WINS:
				{++result.changingSelectionWins;
				}
				break;
		}
	}

	return result;
}

The Results

Clicking the “Run Simulation” button below will run both versions of the simulation, so you can compare the results:

Simulation Running As Two Iterations
Contestant changed their choice Contestant DID NOT change their choice
Total simulation count:
Games won: ( %) ( %)
Total duration to run simulation: ms ms
Simulation Running As A Single Iteration
Contestant changed their choice Contestant DID NOT change their choice
Total simulation count:
Games won: ( %) ( %)
Total duration to run simulation: ms

As you can see the results are unchanged – changing the selected door after the goat is revealed is still the best option. The single-pass simulation seems to take the same time to simulate 200,000 games as the original took for the same number, although the original was split into two runs. Cutting down to 100,000 runs in the single pass code obviously halves its running time.

Conclusion

Sometimes when you take a look at an existing piece of code you’ll start to get ideas about improving it. These might start off as just a feeling, or may suddenly occur to you in a detailed form. Either way it might be worth investigating; for the sake of spending some time researching you may end up with faster, simpler or more correct code, or a combination of all three.

Made In YYC

Made In YYC
Made In YYC

Hosted in Canada by CanSpace Solutions