Win a copy of Murach's MySQL this week in the JDBC and Relational Databases forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Simple challenge: Monty Hall

 
Sheriff
Posts: 17644
300
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Saw something about Monty Hall today and thought it would make a fun little challenge. What I found was that it's an exercise in simplification and clear thinking. My initial solution was very complex and after a number of iterations, I managed to get it down to its essence.

Monty Hall Problem - https://en.wikipedia.org/wiki/Monty_Hall_problem

Basically, you're a contestant on a game show where you're presented with three doors. Behind one of those doors is a brand new car. Behind the other two doors are goats. The game starts by you picking one of the three doors. The host will then open one of the other two doors to reveal a goat (never the car -- the host knows which door has the car). You now are given a choice to either stick with your original pick or switch to the other door that's wasn't opened by the host. It may be counterintuitive, but you actually have a 2/3 chance of winning the car if you switch your pick to the other door.

The challenge: Write a program to simulate N Monty Hall games played and show that there's consistently a better chance of winning the car if you switch to the other door instead of staying with your original pick.

Post your solutions and let's discuss.
 
Junilu Lacar
Sheriff
Posts: 17644
300
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Interesting to see the past discussions about this and how many people argued incorrectly about the odds of winning. A correct simulation clearly shows there's a better chance of winning if you switch. Even if you can convince yourself otherwise through "logic" it's very hard to argue with empirical evidence.
 
Marshal
Posts: 79019
375
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
The Monty Hall game is by no means difficult to program. What probabilities did people expect?
 
Campbell Ritchie
Marshal
Posts: 79019
375
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Doesn't the host only offer the change when the contestant chooses the poor prize?
[edit]No, I think I was wrong there.
 
Junilu Lacar
Sheriff
Posts: 17644
300
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:The Monty Hall game is by no means difficult to program. What probabilities did people expect?



Ah, but I discovered that I fell victim to a pattern I often see in the real world: overcomplicating the solution by being too literal with the implementation we come up with. Paradoxically, the simple solution is much harder to arrive at than a complex solution.

This is why I'm curious to see how other people solve this and have the reassurance that it's not just me who has the tendency to overcomplicate things.
 
Junilu Lacar
Sheriff
Posts: 17644
300
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:Doesn't the host only offer the change when the contestant chooses the poor prize?
[edit]No, I think I was wrong there.



The host knows where the car is and they will always open a door that has a goat behind it. The contestant is always given the chance to switch before the car is revealed, regardless of whether or not they would have won with their first pick. That's the dilemma.
 
Junilu Lacar
Sheriff
Posts: 17644
300
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:The Monty Hall game is by no means difficult to program. What probabilities did people expect?


People incorrectly expect that after one of the other doors is opened, you now have a 50-50 chance of winning the car. In fact, you have a 2 in 3 odds of winning the car if you switch and only 1 in 3 odds if you stay.
 
Junilu Lacar
Sheriff
Posts: 17644
300
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
So this is where I started:

1 - I need to simulate 3 doors and put the car randomly behind one of them
2 - I need to simulate the contestant's pick
3 - I need to figure out which of the other doors the host would open
4 - I need to figure out whether the contestant wins by sticking with their original pick or switching to the other door

When I tried to implement this, it got quite complicated. If you think your solution would be much simpler, what does it look like and what was your thought process?
 
Master Rancher
Posts: 4758
71
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
As one who read Marilyn vos Savant's column on this back when it came out in 1990, and understood the right answer(s) back then... while the problem itself is indeed counterintuitive, MvS caused additional confusion with her poorly-specified version of the problem (actually from a reader, but she continued it and never noticed the error), which persists in this very thread.  Specifically, it's important to say that the host will always behave as described - it isn't just something that happened on one occasion.   That is what allows us to describe the probabilities so precisely - otherwise you're wondering, well, why did the host give us this information, what's his motivation, and would he behave differently under different inputs?  When in fact, the problem only works if the host's behavior is completely deterministic.  MvS lumped all who questioned her as "they just don't understand", and completely missed the ambiguity in the problem statement.

The above Wikipedia article also notes that when Monty Hall himself was interviewed (the host of the original game show upon which the problem is based), he pointed out that on his show, he did have different options, and didn't always open another door, but he modified his behavior to the situation to apply pressure on the contestant.  

"If the host is required to open a door all the time and offer you a switch, then you should take the switch," he said. "But if he has the choice whether to allow a switch or not, beware. Caveat emptor. It all depends on his mood."  Smart guy, Monty.
 
Junilu Lacar
Sheriff
Posts: 17644
300
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Mike Simmons wrote:MvS caused additional confusion with her poorly-specified version of the problem (actually from a reader, but she continued it and never noticed the error), which persists in this very thread.  Specifically, it's important to say that the host will always behave as described - it isn't just something that happened on one occasion.



Is it not clear enough to say "The host will then open one of the other two doors to reveal a goat (never the car -- the host knows which door has the car)"? In what ways can this be misunderstood?
 
Saloon Keeper
Posts: 15437
361
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I think it was my first or second year of Uni when I first heard about this problem, and although the explanation made absolute sense to me, the problem just begged to be simulated.

I wish I still had that program somewhere. It was one of the first projects I wrote for myself in Java.
 
Mike Simmons
Master Rancher
Posts: 4758
71
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Junilu - you're right, I misread your version.  The "will then open" is more like a general rule that must apply whatever happens.  The MvS version was all present tense, might be an incident that happens only once:

"You pick a door, say No. 1, and the host, who knows what's behind the doors, opens another door, say No. 3, which has a goat." - Might happen differently to someone else on another day.  Too vague to be a general rule.

Anyway, I retract the "persists in this very thread" part - sorry about that.
 
Junilu Lacar
Sheriff
Posts: 17644
300
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Mike Simmons wrote:The above Wikipedia article also notes...


That article is so much longer than I would have expected it to be. Reading through it in more detail, I can see that I'm not the only one who likes to make things more complicated than they have to be  
 
Junilu Lacar
Sheriff
Posts: 17644
300
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Mike Simmons wrote:Anyway, I retract the "persists in this very thread" part - sorry about that.


No problem

And thanks for putting me on to the rest of the article, I only did a very cursory read initially but now I see that a whole lot of people got very involved with such a seemingly simple problem.
 
Junilu Lacar
Sheriff
Posts: 17644
300
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Stephan van Hulst wrote:I wish I still had that program somewhere. It was one of the first projects I wrote for myself in Java.


Ah, to be able to see the code we wrote back in the day. One of the first problems I worked on in college was the Fibonacci number series. This was only in our second or third week, after we were taught about if statements and while loops. I don't think our teach even taught us about recursion, just told us to read the relevant chapter in the textbook. Took me all night to figure it out by myself.
 
Stephan van Hulst
Saloon Keeper
Posts: 15437
361
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I recall that my code back in the day was much less verbose (almost C-like), but this is how I would write it today:


 
lowercase baba
Posts: 13089
67
Chrome Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I like the fact that a good way to get a grip on this problem is to make it MORE complicated...sort of.  Often to understand a problem you reduce the number of options.  But in this case....

Imagine there are a million doors, with a car behind one and a goat behind the rest.  

You pick a door.

The host opens ALL THE OTHER DOORS BUT ONE, and all show a goat.

Now do you switch?

 
Stephan van Hulst
Saloon Keeper
Posts: 15437
361
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
What I like about your example Fred, is that most people would probably still intuitively say that it doesn't matter, and that the final choice has a 50% chance of picking the door with the car.
 
Junilu Lacar
Sheriff
Posts: 17644
300
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks, Stephan, for putting in the effort. At least I can take comfort in the fact that I didn't come up with the most complicated solution on my first go around.  

My simplified solution doesn't have a DOORS constant, although at one point I did, nor is the literal 3 hard-coded anywhere. It's a basic assumption in the simplified program that the number of doors is 3.

Spoke too soon. I do have 3 hard-coded but it's only in one place:

This method is called exactly two times in the simplified solution: to get the contestant's pick, and to get the winning door.
 
Junilu Lacar
Sheriff
Posts: 17644
300
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Here are my results:

Monty Hall simulation with 900,000 runs
switched: 600,168 wins,
stayed: 299,832 wins,
Odds of winning by switching: 66.69%
 
Marshal
Posts: 8835
631
Mac OS X VI Editor BSD Java
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Those who read wikipedia article, and still found it hard to understand how that works, I wrote a simpler version to explain that.

If stay at the door you picked at the start:

Case 1: At the start, you pick a car. The host can choose whether to reveal goat1 or goat2. [You stay, you get car]
Case 2: At the start, you pick goat1. The host has to reveal goat2. You stay, you get goat1.
Case 3: At the start, you pick goat2. The host has to reveal goat1. You stay, you get goat2.

2 times out of 3, you loose.


If you swap to the other door:

Case 1: At the start, you pick a car. The host can choose whether to reveal goat1 or goat2. You swap, you get either goat1 or goat2.
Case 2: At the start, you pick goat1. The host has to reveal goat2. [You swap, you get car]
Case 3: At the start, you pick goat2. The host has to reveal goat1. [You swap, you get car]

2 times out of 3, you win.
 
Junilu Lacar
Sheriff
Posts: 17644
300
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Here's what's interesting to me: engineers have a strong tendency to over-engineer. It's just something we do. When the requirement says three doors, there's a strong tendency for us to eventually (almost immediately) think "Why do we have to limit it to three?" That thought probably happens right around when we extract the hard-coded and duplicated literal 3 to a constant field like DOORS or DOOR_COUNT. Now we have to make the effort of defining the constant worth it by generalizing the solution to handle any value of DOOR_COUNT.

Does this resonate with anyone?
 
Junilu Lacar
Sheriff
Posts: 17644
300
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Liutauras Vilda wrote:Those who read wikipedia article, and still found it hard to understand how that works, I wrote a simpler version to explain that.


I like it. I prettied it up for you.

If you stay with your original pick:

Case 1: You pick the car. The host reveals either goat1 or goat2. You stay, you have a new car.  
Case 2: You pick goat1. The host has to reveal goat2. You stay, you have goat1.  
Case 3: You pick goat2. The host has to reveal goat1. You stay, you have goat2.  

2 times out of 3, you have a goat if you stay.


If you switch to the other door:

Case 1: You pick the car. The host reveals either goat1 or goat2. You switch, you get either goat1 or goat2.
Case 2: You pick goat1. The host has to reveal goat2. You switch, you have a new car
Case 3: You pick goat2. The host has to reveal goat1. You switch, you have a new car

2 times out of 3, you have a new car. if you switch.
 
Junilu Lacar
Sheriff
Posts: 17644
300
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Here's the core of my simulation logic: If you pick the car, you win if you stay, otherwise you win if you switch. That's it.

I started out with a List<Boolean> and a lot of logic for shuffling, figuring out which of the other doors the host would open, etc.  but I realized in the end that all that was unnecessary.
 
Junilu Lacar
Sheriff
Posts: 17644
300
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I had something like this:

The idea was that the one TRUE choice represented the car (a win), otherwise you don't win. I got rid of this code in the end because I found it wasn't really needed.
 
Mike Simmons
Master Rancher
Posts: 4758
71
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Junilu Lacar wrote:Here's the core of my simulation logic: If you pick the car, you win if you stay, otherwise you win if you switch. That's it.


Yeah, that's a good way to look at it.   The only issue I see with that is that if you understand the problem well enough to realize that, you don't really need the simulation to convince you.  The simulation is to convince everyone else.

Anyway, here's my somewhat minimal approach:
 
fred rosenberger
lowercase baba
Posts: 13089
67
Chrome Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Stephan van Hulst wrote:What I like about your example Fred, is that most people would probably still intuitively say that it doesn't matter, and that the final choice has a 50% chance of picking the door with the car.


These are the same people who say they have a 50-50 chance of winning vs. losing the lottery.
 
Stephan van Hulst
Saloon Keeper
Posts: 15437
361
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Junilu Lacar wrote:Thanks, Stephan, for putting in the effort. At least I can take comfort in the fact that I didn't come up with the most complicated solution on my first go around.  


Yeah, I was acutely aware of this while I was writing the application, and I considered writing the bare minimum to solve the original problem statement. Then I thought, it's a hobby project, I'll overengineer the crap out of it if I want to.

Junilu Lacar wrote:there's a strong tendency for us to eventually (almost immediately) think "Why do we have to limit it to three?"

...

Does this resonate with anyone?


Definitely.

If I'm solving a problem for my employer, I'll try to keep things as simple as possible, generalizing only when there's a good chance that the customer will eventually want to expand the capabilities.

If I'm writing an application for myself, magic numbers or special cases just stick out like sore thumbs for me. I just can't write the simplest thing.
 
Liutauras Vilda
Marshal
Posts: 8835
631
Mac OS X VI Editor BSD Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Junilu, please don't reveal your code yet.
 
Liutauras Vilda
Marshal
Posts: 8835
631
Mac OS X VI Editor BSD Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Junilu Lacar wrote:What I found was that it's an exercise in simplification and clear thinking.


Here is my one.


[EDIT]: did a bit of renaming to better express the intent

And the simulation here (pardon for imprecision):

 
Junilu Lacar
Sheriff
Posts: 17644
300
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Liutauras Vilda wrote:Junilu, please don't reveal your code yet.


Not to worry, I wasn't planning to just yet.
 
Junilu Lacar
Sheriff
Posts: 17644
300
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Stephan van Hulst wrote:Then I thought, it's a hobby project, I'll overengineer the crap out of it if I want to.

 
 
Liutauras Vilda
Marshal
Posts: 8835
631
Mac OS X VI Editor BSD Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
My implementation is very much inline with explanation I provided earlier.
 
Bartender
Posts: 5464
212
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Had Shakespear known about this topic, that title would have been: very much ado about nothing. But for the simulators among us: that contestant is a born doubter, and the chance of switching has a CDF of sqrt(x) between zero and one. What is his chance of driving home that night, instead of riding home?
 
Junilu Lacar
Sheriff
Posts: 17644
300
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks for all of you who shared your solutions. Here's my simplified one:

Here's how I got to eliminating a lot of the original code that I started out with, very similar to the solutions shared:
1. The essence of the game is really whether or not the contestant picked the door with the car. That's encapsulated in picksTheCar() which simply generates two random doors and checks if they're the same.
2. In my opinion, it doesn't make the simulation any less correct to just pick two random numbers and compare them. It still boils down to the two key random picks: which door the contestant chooses and which door the car is behind. As pointed out before, this is because of the hard rule that the host knows where the car is and they will always open a door with a goat behind it.
3. Lines 16-20 essentially express the idea "If the contestant picks the car, they win by staying, otherwise, they win by switching."

This is the first time I've used multiline strings in Java. They're pretty cool. This could have been a few lines shorter but I can't help but Refactor|Extract method.
 
Liutauras Vilda
Marshal
Posts: 8835
631
Mac OS X VI Editor BSD Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I may explain my logic as well.

I look at this in a way that:
  • if you want to win without switching, you must to pick a CAR right away (here you have 1 car only)
  • if you want to win with switching, you must to pick one of the two goats (here you have 2 goats, hence chance is twice bigger)

  • And that is a whole algorithm really.
     
    Liutauras Vilda
    Marshal
    Posts: 8835
    631
    Mac OS X VI Editor BSD Java
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Junilu Lacar wrote:


    That messes up my head. Still trying to wrap my head around this. But it is interesting.

    [EDIT]:
    Ok, I think I get it now. It approaches from likelihood perspective, sort of. Nice!
     
    Junilu Lacar
    Sheriff
    Posts: 17644
    300
    Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Here's another way I thought of:

    Maybe not as readable as the other version though. <shrug>
     
    Liutauras Vilda
    Marshal
    Posts: 8835
    631
    Mac OS X VI Editor BSD Java
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Junilu Lacar wrote:2. In my opinion, it doesn't make the simulation any less correct to just pick two random numbers and compare them. It still boils down to the two key random picks: which door the contestant chooses and which door the car is behind. As pointed out before, this is because of the hard rule that the host knows where the car is and they will always open a door with a goat behind it.


    Very interesting how people differently see the same thing.

    To me it all boils down to, what is the probability, that you'll pick a goat initially.

    CAR, GOAT, GOAT (2/3 or 66.66..%), and that is really your probability of winning a car if you switch.
    It is simple in a way, that you take into account only the initial probability.

    Don't need to think about, ok, what is the probability to find a car if I choose from 3 (1 in 3), now host opens 1 doors, what is probability now if I switch or if I don't... Kind of over complicates things
     
    reply
      Bookmark Topic Watch Topic
    • New Topic