F# – Monty Hall problem

Do you remem­ber that scene from the movie 21 where Kevin Spacey gave our pro­tag­o­nist Ben the game show host prob­lem?

What Kevin Spacey described is known as the Mon­ty Hall prob­lem. It became famous as a ques­tion from a reader’s let­ter to Mar­i­lyn vos Savant’s “Ask Mar­i­lyn” col­umn in Parade mag­a­zine in 1990.

Marilyn’s answer caused quite a bit of con­tro­ver­sy at the time and whilst I don’t under­stand the for­mal math­e­mat­i­cal proof, it’s a prob­lem that can be eas­i­ly proved through sim­u­la­tions.

 

Simulation with F#

First, let’s set up a few types to rep­re­sent the prob­lem domain:

image

Pret­ty self-explana­to­ry here:

  • behind every Door is a Prize;
  • the Prize is either a Car or a Goat;
  • you Win if you get the Car in the end, oth­er­wise you Lose

When you start a new game you always have three doors, arranged in some ran­dom order.

image

After you had giv­en your ini­tial choice, the game show host will reveal one of the doors that has a Goat?.

Here we have a func­tion that takes in the doors and the player’s ini­tial choice; and return the index of a door that:

  1. the play­er didn’t choose; and
  2. has a goat

image

Putting it togeth­er, we have a func­tion that takes in the doors as well as the player’s strat­e­gy and return whether the play­er Win or Lose at the end of the game.

image

From the code above you can guess the type sig­na­ture of the strat­e­gy func­tion to be int –> int –> int. That is, it takes two inte­gers – the player’s ini­tial choice and the index of the door the host has revealed – and return the player’s final choice.

Now, giv­en the two choic­es we have – to stay or to change, we can rep­re­sent it with two strate­gies:

  • strat­e­gyA would stay with the player’s orig­i­nal choice;
  • strat­e­gyB would change

image

We can now use these two func­tions to call play with.

p.s. notice we have essen­tial­ly imple­ment­ed the Strat­e­gy pat­tern, but with­out all the boil­er­plates and inter­faces and class­es? With just func­tions! Isn’t that sweet?

 

To be kinder to our­selves, let’s add anoth­er helper func­tion that will take in our cho­sen strat­e­gy and run a sim­u­la­tion of 1000 games, and return the num­ber of games that we have won with this strat­e­gy:

image

Final­ly, let’s run our sim­u­la­tions and see how the two strate­gies per­form.

image

Run­ning this sim­u­la­tion over and over, strat­e­gyB con­sis­tent­ly out­per­forms strat­e­gyA by rough­ly 2-to-1, which is exact­ly what we expect­ed.

You can also just run the sim­u­la­tion your­self on .Net Fid­dle here, just click the Run but­ton at the top.

 

Improving our code

Whilst the above is suf­fi­cient for its pur­pose and it’s a pret­ty short solu­tion, there’re cou­ple of things that can be improved in hind­sight:

  • player’s choice – to Stay, or Change – is not explic­it­ly rep­re­sent­ed in the domain;
  • whilst a Change can only lead to one out­come – chang­ing to the door that isn’t revealed nor ini­tial­ly cho­sen – it is expressed implic­it­ly by the log­ic in strat­e­gyB;
  • if we were to intro­duce anoth­er strat­e­gy (e.g. decide to stay or change ran­dom­ly) then we’d have to dupli­cate the log­ic for change.

To make these improve­ments is real­ly easy. We can start by adding a type to present the two choic­es avail­able to the play­er:

image

Then we can update the play func­tion to work with it:

image

So now, our strat­e­gy imple­men­ta­tions become much sim­pler:

image

Again, you can try out this updat­ed ver­sion on .Net Fid­dle here. It also includes a ‘ran­dom’ strat­e­gy which choos­es to Stay or Change using the rand func­tion we cre­at­ed ear­li­er.

 

There are oth­er things we can improve still. For instance, how do we encap­su­late the con­straint of hav­ing only 3 doors as part of our mod­el?

This way, we can elim­i­nate anoth­er invalid state using the type sys­tem. I’ll leave that as a teas­er to you  and feel free to share your solu­tion in the com­ments!