Simple challenge: Monty Hall

[Mike Simmons]

I think that's equivalent to

  private static int gamesWonIfTheyStayed(int times) {
    return (int) IntStream.range(0, times).filter(i -> picksTheCar()).count();
  }

(Correcting an off-by-one error.)

[Edited to change "(long)" to "(int)"  - Mike]

[Junilu Lacar]

Mike Simmons wrote:I think that's equivalent to

  private static int gamesWonIfTheyStayed(int times) {
    return (long) IntStream.range(0, times).filter(i -> picksTheCar()).count();
  }

(Correcting an off-by-one error.)

Very nice!

I was playing around with BitSet earlier today for a different problem and I guess it was stuck in my head. Even when you think you've got it pretty simple, somebody comes along and shows you an even simpler way. Thanks!  

[Junilu Lacar]

So here's the simplest/clearest solution we've come up with:

package com.coderanch.diversions;

import java.util.*;
import java.util.stream.IntStream;

public class MontyHallSim {
    private static final Random rand = new Random();

    public static void main(String[] args) {
        simulate(900_000);
    }

    private static void simulate(int times) {
        reportResults(times, gamesWonIfTheyStayed(times));
    }

    private static int gamesWonIfTheyStayed(int times) {
        return IntStream.range(0, times).map(i -> picksTheCar() ? 1 : 0).sum();
    }

    private static boolean picksTheCar() {
        return randomDoor() == randomDoor();
    }

    private static int randomDoor() {
        return rand.nextInt(3);
    }

    private static final String REPORT_FORMAT = """
                Monty Hall simulation with %,d games
                - %,d wins if contestant switched (%4.2f%%)
                - %,d wins if contestant stayed   (%4.2f%%)
            """;

    private static void reportResults(int count, int stayedWins) {
        int switchedWins = count - stayedWins;
        System.out.printf(REPORT_FORMAT,
                count,
                switchedWins, percentageOf(switchedWins, count),
                stayedWins, percentageOf(stayedWins, count)
        );
    }

    private static double percentageOf(int wins, int count) {
        return 100.0 * wins / count;
    }
}

De-factoring by manually doing the inlining that an optimizing compiler would most likely do for you:

package com.coderanch.diversions.solutions;

import java.util.Random;
import java.util.stream.IntStream;

public class MontyHallShort {
    private static final Random rand = new Random();
    private static final int TIMES = 900_000;
    
    public static void main(String[] args) {
        reportResults(TIMES, IntStream.range(0, TIMES).map(i ->
                rand.nextInt(3) == rand.nextInt(3) ? 1 : 0).sum());
    }

    private static final String REPORT_FORMAT = """
                Monty Hall simulation with %,d games
                - %,d wins if contestant switched (%4.2f%%)
                - %,d wins if contestant stayed   (%4.2f%%)
            """;

    private static void reportResults(int count, int stayedWins) {
        int switchedWins = count - stayedWins;
        System.out.printf(REPORT_FORMAT,
                count,
                switchedWins, 100.0 * switchedWins / count,
                stayedWins, 100.0 * stayedWins / count
        );
    }
}

Comparing the two, I'd probably choose to go with the clearer version rather than the shorter.

[Liutauras Vilda]

Junilu Lacar wrote:solution we've come up with

I must say a solution is very very different from what I envisioned before we started coding

[Junilu Lacar]

I'm always imagining a conversation in my head when I'm programming solo, maybe to simulate the experience I'd have if I were programming in a pair or ensemble. My imagination is obviously limited though so I'll pop out to the internet and find other alternative solutions. Then I'll take those solutions and imagine a conversation around them.

I guess I just miss the experience of collaborative programming. My next gig that's about to start should be a good one though because I'm being brought on to coach teams in adopting XP.

[Junilu Lacar]

This is what I had before I started refactoring:

package com.coderanch.diversions.solutions;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;

public class MontyHallLong {

    private static final int SIMS = 900_000;
    static Random rand = new Random();

    private static final List<Boolean> choices = new ArrayList<>();
    static {
        choices.add(Boolean.FALSE);
        choices.add(Boolean.FALSE);
        choices.add(Boolean.TRUE);
    }

    public static void main(String[] args) {
        runSim();
    }

    private static void runSim() {
        int winsSwitched = 0;
        int winsStayed = 0;
        for (int i = 0; i < SIMS; i++) {
            Collections.shuffle(choices);
            if (winBySwitching(rand.nextInt(3), choices)) {
                winsSwitched++;
            } else {
                winsStayed++;
            }
        }
        System.out.printf("Sims: %d%n switched: %d,%n stayed: %d,%n Chances of winning by switch: %4.2f%%",
                SIMS, winsSwitched, winsStayed, 100.0 * winsSwitched / SIMS);
    }

    static boolean winBySwitching(int pick, List<Boolean> choices) {
        int door1 = (pick + 1) % 3;
        int door2 = (pick + 2) % 3;
        return choices.get(door1) ^ choices.get(door2);
    }
}

These are my notes on how I got lines 40 and 41:

0* 1  2
0  1* 2
0  1  2*

The starred number is the picked door, figure out the other doors

pick	(pick + 1) % 3	(pick + 2) % 3
0	1	2
1	2	0
2	0	1

[Junilu Lacar]

Speaking of imagined discussions, I was just wondering what the discussion might be around the picksTheCar() method:
   private static boolean picksTheCar() {        return randomDoor() == randomDoor();    }
Is that a head-scratcher / eyebrow-scruncher? Would a comment like this help?
   private static boolean picksTheCar() {        return randomDoor() == randomDoor();        // i.e.,  theirPick == theCar    }
I believe in the general rule that comments are an indication of code that isn't as clear as it could be but I think the comment could be helpful. What do you think? A good exception to the rule?

[Stephan van Hulst]

Then why not just write the following?

var winningDoor = randomDoor();
var  chosenDoor = randomDoor();

return chosenDoor == winningDoor;

I really don't think there are ever any valid reason to write comments that explain what you are doing, only ever why you are doing things.

[Junilu Lacar]

Thanks, Stephan.

When I first started reading the Refactoring book, I noticed there were a few seemingly contradictory refactorings. For example,
Introduce Explaining Variable vs. Inline Temporary Variable

This was a little confusing to me as a newbie to refactoring because I didn't have a good grasp of the contexts in which each was appropriately applied. In this case, pick and car would be explaining variables, which is what I had originally.

private static boolean picksTheCar() {
   int pick = randomDoor();
   int car = randomDoor();
   return pick == car;
}

But then, each of those variables are only used one time. Also, the method name already says the intent is to see if they picked the car. So applying Inline Variable refactoring:

private static boolean picksTheCar() {
  return randomDoor() == randomDoor();
}

But then maybe this is too cryptic for someone new to the code or maybe to myself if I come back to it in the future.

So now, rather than revert to the explaining variables, I add a comment to see if I feel better about that.

For some reason, I feel better with the comment than I do with the explaining variable, which is pretty conflicting given that, like you, I also think comments that explain what you're doing should be avoided.

[Stephan van Hulst]

The problem is that over time, comments have the habit of going out of sync with the code. Using explaining variables will not.

[Liutauras Vilda]

Junilu Lacar wrote:So here's the simplest/clearest solution we've come up with
https://coderanch.com/t/40/754647/Simple-challenge-Monty-Hall#3502756

To be brutally honest, to me it isn't a most simplest or clearest solution. You have to be quite intelligent to find it simplest or clearest.

[Campbell Ritchie]

It would need comments to explain it

[Junilu Lacar]

Liutauras Vilda wrote:

Junilu Lacar wrote:So here's the simplest/clearest solution we've come up with
https://coderanch.com/t/40/754647/Simple-challenge-Monty-Hall#3502756

To be brutally honest, to me it isn't a most simplest or clearest solution. You have to be quite intelligent to find it simplest or clearest.

Campbell Ritchie wrote:It would need comments to explain it

Fair enough. I was reading it again (for the 30th time probably) thinking what someone new to the code might experience as they read through the code and I can certainly see how they'd need some kind of explanation of what the thought process is behind the logic. This is probably where the kind of comment Stephan mentioned, explaining why something was done in a certain way, is warranted.

[Junilu Lacar]

Stephan van Hulst wrote:The problem is that over time, comments have the habit of going out of sync with the code. Using explaining variables will not.

I general, I would agree with you. However, this is one line of code with one comment. The likelihood that the comment and the code will diverge, at least in my mind, is very low.

[Stephan van Hulst]

The alternative is no chance of divergence.

[Campbell Ritchie]

Junilu Lacar wrote:. . . the kind of comment Stephan mentioned . . . is warranted.

Agree. You can have a few other comments warranted by the circumstances, too.

/**
 * ... Uses Bedžryczowksy's algorithm ...
 */
public Foo someMethod(Bar something)
{
  /* For more info about Bedžryczowksy's algorithm, see ... */
  // ...
}

/* Earlier objects = Campbell, Stephan, and Junilu */
int count = 3;

You can change the first example to use only one comment. The second example works a lot better if you actually have three things already counted And of course nobody should forget their /** Documentation Comments */
[edit]Just in case anybody can't read the green text, it says, “/** Documentation Comments */”.

[Junilu Lacar]

Stephan van Hulst wrote:The alternative is no chance of divergence.

True that.

I just did a Community of Practice mobbing session with some other coaches and brought up the same question. The explaining variables ended up being the preference in that discussion as well.

[Junilu Lacar]

Campbell Ritchie wrote:And of course nobody should forget their /** Documentation Comments */

Agree.

(Don't use color though, people might have a hard time seeing color ) <just kidding>  

[Mike Simmons]

Well, I'm still of the opinion that in order to convince skeptics of the validity of the results, the simulation needs to actually simulate all the parts of the problem, not just simplify the unimportant parts out of existence.  Otherwise we can reduce it to a random number simulator for already-known probabilities:

import java.util.Random;
import java.util.stream.IntStream;

public class ExtraSimplifiedMontyHall {
  private final boolean doSwitch;
  public ExtraSimplifiedMontyHall(boolean doSwitch) {
    this.doSwitch = doSwitch;
  }

  public static void main(String[] args) {
    new ExtraSimplifiedMontyHall(true).runSimulation();
    new ExtraSimplifiedMontyHall(false).runSimulation();
  }

  private void runSimulation() {
    final int NUM_RUNS = 1_000_000;
    System.out.println("\nRunning "+ NUM_RUNS + " times with doSwitch="  + doSwitch + "\n");
    Random random = new Random();
    long wins = IntStream.range(0, NUM_RUNS).filter(i -> random.nextInt(3) < (doSwitch ? 2 : 1)).count();
    System.out.println("wins=" + wins);
    System.out.println("percentage=" + (100.0 * wins / NUM_RUNS) + "%");
  }
}

Output:

Running 1000000 times with doSwitch=true

wins=666311
percentage=66.6311%

Running 1000000 times with doSwitch=false

wins=333274
percentage=33.3274%

But that's unlikely to convince anyone who isn't already on board.  In contrast, here's my improved version for a simulation detailing each part of the process, with additional info on how likely each chain of events is:

import java.util.Arrays;
import java.util.Map;
import java.util.Random;
import java.util.TreeMap;
import java.util.TreeSet;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class MontyHall {
  private final int NUM_RUNS = 1_000_000;
  private final int NUM_DOORS = 3;
  private static final Random random = new Random();
  private final boolean doSwitch;
  private final Map<String,Long> recordMap = new TreeMap<>();

  public MontyHall(boolean doSwitch) {
    this.doSwitch = doSwitch;
  }

  public static void main(String[] args) {
    new MontyHall(true).runSimulation();
    new MontyHall(false).runSimulation();
  }

  private void runSimulation() {
    System.out.println("\nRunning "+ NUM_RUNS + " times with doSwitch="  + doSwitch + "\n");
    long wins = IntStream.range(0, NUM_RUNS).filter(i -> playGame()).count();
    recordMap.forEach((record, count) -> System.out.println(record + ": count:" + count + " (" + (100.0 * count / NUM_RUNS) + "%)"));
    System.out.println("wins=" + wins);
    System.out.println("percentage=" + (100.0 * wins / NUM_RUNS) + "%");
  }

  private boolean playGame() {
    int prizeDoor = chooseRandom();
    int choice1 = chooseRandom();
    int openedDoor = chooseExcluding(prizeDoor, choice1);
    int choice2 = doSwitch ? chooseExcluding(choice1, openedDoor) : choice1;
    boolean isWin = choice2 == prizeDoor;
    var record = String.format("Game record: [prizeDoor=%d, choice1=%d, openedDoor=%d, choice2=%d, isWin=%-5b]",
      prizeDoor, choice1, openedDoor, choice2, isWin);
    recordMap.compute(record, (rec, prevCount) -> prevCount == null ? 1 : prevCount + 1);
    return isWin;
  }

  private int chooseRandom() {
    return random.nextInt(NUM_DOORS);
  }

  private int chooseExcluding(int... exclusions) {
    var exes = Arrays.stream(exclusions).boxed().collect(Collectors.toCollection(TreeSet::new));
    int n = random.nextInt(NUM_DOORS - exes.size());
    for (int e : exes) {
      if (n >= e) n++;
    }
    return n;
  }
}

Output:

Running 1000000 times with doSwitch=true

Game record: [prizeDoor=0, choice1=0, openedDoor=1, choice2=2, isWin=false]: count:55495 (5.5495%)
Game record: [prizeDoor=0, choice1=0, openedDoor=2, choice2=1, isWin=false]: count:55753 (5.5753%)
Game record: [prizeDoor=0, choice1=1, openedDoor=2, choice2=0, isWin=true ]: count:111217 (11.1217%)
Game record: [prizeDoor=0, choice1=2, openedDoor=1, choice2=0, isWin=true ]: count:110918 (11.0918%)
Game record: [prizeDoor=1, choice1=0, openedDoor=2, choice2=1, isWin=true ]: count:110973 (11.0973%)
Game record: [prizeDoor=1, choice1=1, openedDoor=0, choice2=2, isWin=false]: count:55411 (5.5411%)
Game record: [prizeDoor=1, choice1=1, openedDoor=2, choice2=0, isWin=false]: count:55479 (5.5479%)
Game record: [prizeDoor=1, choice1=2, openedDoor=0, choice2=1, isWin=true ]: count:111165 (11.1165%)
Game record: [prizeDoor=2, choice1=0, openedDoor=1, choice2=2, isWin=true ]: count:111377 (11.1377%)
Game record: [prizeDoor=2, choice1=1, openedDoor=0, choice2=2, isWin=true ]: count:110568 (11.0568%)
Game record: [prizeDoor=2, choice1=2, openedDoor=0, choice2=1, isWin=false]: count:55992 (5.5992%)
Game record: [prizeDoor=2, choice1=2, openedDoor=1, choice2=0, isWin=false]: count:55652 (5.5652%)
wins=666218
percentage=66.6218%

Running 1000000 times with doSwitch=false

Game record: [prizeDoor=0, choice1=0, openedDoor=1, choice2=0, isWin=true ]: count:55401 (5.5401%)
Game record: [prizeDoor=0, choice1=0, openedDoor=2, choice2=0, isWin=true ]: count:55755 (5.5755%)
Game record: [prizeDoor=0, choice1=1, openedDoor=2, choice2=1, isWin=false]: count:111476 (11.1476%)
Game record: [prizeDoor=0, choice1=2, openedDoor=1, choice2=2, isWin=false]: count:111410 (11.141%)
Game record: [prizeDoor=1, choice1=0, openedDoor=2, choice2=0, isWin=false]: count:110942 (11.0942%)
Game record: [prizeDoor=1, choice1=1, openedDoor=0, choice2=1, isWin=true ]: count:55563 (5.5563%)
Game record: [prizeDoor=1, choice1=1, openedDoor=2, choice2=1, isWin=true ]: count:55468 (5.5468%)
Game record: [prizeDoor=1, choice1=2, openedDoor=0, choice2=2, isWin=false]: count:110493 (11.0493%)
Game record: [prizeDoor=2, choice1=0, openedDoor=1, choice2=0, isWin=false]: count:111810 (11.181%)
Game record: [prizeDoor=2, choice1=1, openedDoor=0, choice2=1, isWin=false]: count:110807 (11.0807%)
Game record: [prizeDoor=2, choice1=2, openedDoor=0, choice2=2, isWin=true ]: count:55481 (5.5481%)
Game record: [prizeDoor=2, choice1=2, openedDoor=1, choice2=2, isWin=true ]: count:55394 (5.5394%)
wins=333062
percentage=33.3062%

[Junilu Lacar]

Mike Simmons wrote:
Well, I'm still of the opinion that in order to convince skeptics of the validity of the results, the simulation needs to actually simulate all the parts of the problem, not just simplify the unimportant parts out of existence.  Otherwise we can reduce it to a random number simulator for already-known probabilities:
   ...    long wins = IntStream.range(0, NUM_RUNS).filter(i -> random.nextInt(3) < (doSwitch ? 2 : 1)).count();    ...

But isn't that line saying something very different from this one?

   int stayWins = IntStream.range(0, NUM_RUNS).map(i -> pickedTheCar() ? 1 : 0).sum();

(Re the forum rendering bug: a ">" in a code block will throw its parsing logic for a loop. You can turn off HTML to skirt around the bug)

In your incantation, there's only one random pick and it's always compared to either 1 or 2, which already predetermines the outcome.

By contrast, pickedTheCar() compares two random choices: the door the contestant chooses and the door the car is behind. So whether you win or lose by staying still depends on whether or not the door you picked is the same door as where the car was randomly placed.

In a session I had with some colleagues this morning, they first predicted that they'd win more often if they stayed with their original pick. We did it manually, with me pre-selecting a number for where the car would be then them picking a number. I'd then tell them which of the other numbers didn't represent the car and they got to choose whether they stayed or switched. What was funny was that the first few times, they were lucky enough to win either way they tried. But they still weren't sure about the probabilities and I didn't tell them what they were. I suggested we write a program to simulate what we just did manually and see empirically what the probabilities were. We wrote basically the same program together, every step having a conversation about what each statement meant.

By the end, after they saw the results, they agreed that it was more favorable to switch. I think being involved in coming up with the logic for the simulation helped convince them that the results were legitimate.

Next time, I'll try the same exercise with a different group of colleagues and maybe do 10 or more manual runs with them. Once they understand the mechanics, I'll try to get them to write the simulation program and work through the logic. I'll let you guys know how that goes. Should be in a couple of weeks or so.

[Junilu Lacar]

If I remember correctly (this morning was such a loooong time ago   ) we started out by just summing up the times they stayed and picked the same door as where the car was.

// iteration 1:
if (pickedTheCar()) {
   winsByStaying++;
}

Then we discussed how to represent the idea of winning by switching to the other door instead. We ended up with the same code:

// iteration 2:
if (pickedTheCar()) {
  winsByStaying++;
} else {
  winsBySwitching++;
}

I'll admit that the discussion might have been biased with my input so next time I'll try to stay quiet while others work through the logic.

[Mike Simmons]

Junilu Lacar wrote:(Re the forum rendering bug: a ">" in a code block will throw its parsing logic for a loop. You can turn off HTML to skirt around the bug)

Ah, thanks - I've taken advantage of that now.

[Mike Simmons]

Junilu Lacar wrote:But isn't that line saying something very different from this one?

   int stayWins = IntStream.range(0, NUM_RUNS).map(i -> pickedTheCar() ? 1 : 0).sum();

Well, I'd make that

int stayWins = IntStream.range(0, NUM_RUNS).filter(i -> pickedTheCar()).count();

But more to your point...

Junilu Lacar wrote:In your incantation, there's only one random pick and it's always compared to either 1 or 2, which already predetermines the outcome.

Sure.  Because the rules have already predetermined that the chance of winning is either 2/3 or 1/3, depending on whether you switch or not.  I've just jumped a little farther ahead to the answer.  But then again, yours has also simplified the process, eliminating the parts that didn't actually matter that much.  To be honest, if you're working with someone who has agreed that your pickedTheCar() implementation will completely correlate with winning (if you don't switch) or losing (if you do switch)... then I don't know why they need the simulation at all.  Obviously pickedTheCar() will be true 1/3 of the time.

To be clear, I completely agree with your logic.  I just don't know how obstinate the doubters will be.  People can get really stuck on their 50/50 interpretation, and convinced that you are then changing the problem when you try to simplify it.  So I like providing a solution that fully enumerates all the 12 permutations of events that can occur if you don't switch, and the 12 different permutations that occur if you do switch, and shows how they add up to a 1/3 chance of winning by not switching, and a 2/3 chance of winning by switching.  Whether or not that is more convincing, may depend on the persons who need to be convinced.

[Junilu Lacar]

Mike Simmons wrote:
Well, I'd make that

int stayWins = IntStream.range(0, NUM_RUNS).filter(i -> pickedTheCar()).count();

Yeah, I tried exactly that but count() returns a long which then has to be downcast to an int.  Otherwise, the receiving variable needs to be declared as a long. Also, I saw that the documentation said that count() is a special case of the reduction mapToLong(e -> 1L).sum() so I took the path of least resistance (for me) and went with map().sum(). I do like the semantics of filter().count() though.

Kotlin makes it so much nicer though:

fun pickedTheCar() = rand.nextInt(3) == rand.nextInt(3)

val winsIfStayed = (1..times).count { pickedTheCar() }

[Piet Souris]

Without loss of generality, you may assume that the contestant always chooses the first door. Simplifies things. Coming up with beautifully refactored code for such a trivial problem is easy enough. But what if the contestant has no clue whether to switch or not, and decides to flip a coin? Would that not be a muchmore interesting simulation? And those of us saying it is fifty-fifty wouldn't be far off...

[Junilu Lacar]

Mike Simmons wrote:if you're working with someone who has agreed that your pickedTheCar() implementation will completely correlate with winning (if you don't switch) or losing (if you do switch)... then I don't know why they need the simulation at all.

To be clear, I completely agree with your logic.

How you phrased it isn't the logic expressed in the code though, if I understand what you're saying correctly.

if (by_chance_you_happened_to_pick_the_car()) {
    you_would_win_if_you_stay++;

} else { // you picked a goat, so
    you_would_win_if_you_switch++; 
    // because the unopened door is the car
}

The conditional statement "if by chance you happened to pick the car" is still random.

[Junilu Lacar]

Piet Souris wrote:Without loss of generality, you may assume that the contestant always chooses the first door. Simplifies things. Coming up with beautifully refactored code for such a trivial problem is easy enough. But what if the contestant has no clue whether to switch or not, and decides to flip a coin? Would that not be a muchmore interesting simulation? And those of us saying it is fifty-fifty wouldn't be far off...

You're right, the empirical evidence does hover around 50% even when the contestant's pick is still random. This is how I interpreted your scenario.

  void runSim(int times) {
    int wins = 0;
    for (int i = 0; i < times; i++) {
      int car = rand.nextInt(3);
      int pick = rand.nextInt(3);
      if (rand.nextBoolean()) { // switch
        wins += (car == pick) ? 0 : 1;
      } else {
        wins += (car == pick) ? 1 : 0;
      }
    }
    reportResults(times, wins);
  }

Monty Hall problem (1,000,000 runs)
wins: 499,506

[Junilu Lacar]

Piet Souris wrote:Would that not be a muchmore interesting simulation? And those of us saying it is fifty-fifty wouldn't be far off...

I don't know if it's a more interesting simulation but it certainly gives different results, as I've shown empirically. The two scenarios are different though, statistically speaking. The former has 2/3 probability of winning if you follow the strategy of always switching your choice to the other door. When the contestant flips a coin to decide whether or not to switch, the coin flip itself changes the equation to a 50-50 chance of winning the car.

[Junilu Lacar]

But wait a minute...

I ran another set of experiments with this code:

    enum PlayStrategy {

        ALWAYS_STAY {
            @Override
            boolean wins() {
                int car = PlayStrategy.anyDoor();
                int pick = PlayStrategy.anyDoor();
                return pick == car;
            }
        },

        ALWAYS_SWITCH {
            @Override
            boolean wins() {
                int car = PlayStrategy.anyDoor();
                int pick = PlayStrategy.anyDoor();
                return pick != car;
            }
        },

        RANDOMLY_SWITCH {
            @Override
            boolean wins() {
                int car = PlayStrategy.anyDoor();
                int pick = PlayStrategy.anyDoor();
                boolean switches = PlayStrategy.maybe();
                return (car != pick) && switches;
            }
        },

        RANDOMLY_STAY {
            @Override
            boolean wins() {
                int car = rand.nextInt(DOORS);
                int pick = rand.nextInt(DOORS);
                boolean stays = PlayStrategy.maybe();
                return (car == pick) && stays;
            }
        };

        private static final int DOORS = 3;
        private static final Random rand = new Random();

        private static boolean maybe() {
            return rand.nextBoolean();
        }

        private static int anyDoor() {
            return rand.nextInt(DOORS);
        }

        abstract boolean wins();
    }

    public static void main(String[] args) {
        simulate(PlayStrategy.ALWAYS_STAY);
        simulate(PlayStrategy.ALWAYS_SWITCH);
        simulate(PlayStrategy.RANDOMLY_SWITCH);
        simulate(PlayStrategy.RANDOMLY_STAY);
    }

    private static void simulate(PlayStrategy playStrategy) {
        int wins = 0;
        for (int i = 0; i < TIMES; i++) {
            if (playStrategy.wins()) wins++;
        }
        report(playStrategy, TIMES, wins);
    }

    private static final String STRATEGY_REPORT = """
                Monty Hall problem playing with %s strategy
                wins : %,d
                times: %,d
                prob : %4.2f 
                
            """;

    private static void report(PlayStrategy playStrategy, int times, int wins) {
        System.out.printf(STRATEGY_REPORT,
                playStrategy, wins, times, percentageOf(wins, times));
    }

And the results were consistently around these numbers:

   Monty Hall problem playing with ALWAYS_STAY strategy
   wins : 333,379
   times: 1,000,000
   prob : 33.34

   Monty Hall problem playing with ALWAYS_SWITCH strategy
   wins : 666,990
   times: 1,000,000
   prob : 66.70

   Monty Hall problem playing with RANDOMLY_SWITCH strategy
   wins : 334,309
   times: 1,000,000
   prob : 33.43

   Monty Hall problem playing with RANDOMLY_STAY strategy
   wins : 167,196
   times: 1,000,000
   prob : 16.72

I need to look at my implementation that gives a 50-50 chance of winning if you randomly decide to switch or stay and why that was producing different results.

[Junilu Lacar]

Junilu Lacar wrote:
You're right, the empirical evidence does hover around 50% even when the contestant's pick is still random. This is how I interpreted your scenario.

Probably not a correct interpretation, given new data.

[Mike Simmons]

Junilu Lacar wrote:How you phrased it isn't the logic expressed in the code though, if I understand what you're saying correctly.

Well, I think it is, but I think we're in dead horse territory.  We can keep rephrasing a lot of different ways.  We agree on the probabilistic outcome, with a chance of either 1/3 or 2/3.

Junilu Lacar wrote:The conditional statement "if by chance you happened to pick the car" is still random.

Yes.  And you can generate that random outcome with one call to nextInt() (my simplest code), or two calls (your code), or several more calls (my fuller simulation code).  All have the same results, statistically.  Which of those you use may depend on who you're trying to convince, and where they may be stuck.

[Liutauras Vilda]

Junilu Lacar wrote:I need to look at my implementation that gives a 50-50 chance of winning if you randomly decide to switch or stay and why that was producing different results.

Not sure I interpret you correctly, but there (where 50-50) you summed up wins, of stayed + switched. While in most recent simulation you treat those wins individually, which makes sense ~33 and ~16, because in those cases where let's say you chose GOAT initially, then randomly decide to switch or stay, so it halves the initial chance of 2/3.

[Junilu Lacar]

So I added this strategy:

        HEADS_SWITCH_TAILS_STAY {
            @Override
            boolean wins() {
                int car = PlayStrategy.anyDoor();
                int pick = PlayStrategy.anyDoor();

                if (Coin.flip() == HEADS) {
                    return car != pick; // switch
                } else {
                    return car == pick; // stay
                }
            }
        };

and ran the simulation. Same results as before:

Monty Hall problem playing with HEADS_SWITCH_TAILS_STAY strategy
   wins : 499,960
   times: 1,000,000
   prob : 50.00

I think the code is right. Anybody see why it would be wrong?

[Piet Souris]

Just a slight statistical digression, if you folks allow me:

let the random variable X denote the chance of winning a car, and r.v. P denote the chance of switching. Then a well-known theorem says:

E[X] = E[ E[X | P] ]

Now, given some value of P, p, we get:

E[X | P = p] = 2/3 * p + 1/3 * ( 1 - p) = (1 + p) / 3

and so,

E[X] = (1 + E[P]) / 3

Therefore, if we always switch, we have that E[P] = 1, and if we never switch, E[P] = 0. And if P denotes the flipping of a coin, then E[P] = .5.

Earlier, I suggested that P has a cumulative density function of sqrt(x). Simulating from such a stochast means that you let

var y = random.nextDouble();
var observationOfP = y * y;

To determine E[P], you can either simulate, or use E[P] = integral from 0 to 1 (1 - sqrt(x)) dx. Outcome: 1/3.

Note: I remember Carey Brown once asking how he could get random values that were more close towards 0 than the usual uniform distribution would give. This is an example of such a distribution.

[Piet Souris]

Junilu Lacar wrote:
I think the code is right. Anybody see why it would be wrong?

The outcome is correct!

[Junilu Lacar]

Just playing around now. I wrote this full simulation with (almost?) all the machinations of the game:

        HEADS_SWITCH_TAILS_STAY_FULL_SIM {
            static final List<Boolean> Doors = new ArrayList<>();
            static {
                Doors.add(TRUE);  // car
                Doors.add(FALSE); // goat1
                Doors.add(FALSE); // goat2
            }
            @Override
            boolean wins() {
                Collections.shuffle(Doors);
                int pick = anyDoor();
                int car = Doors.indexOf(TRUE);
                int goat1, goat2;
                switch (car) {
                    case 0 : goat1 = 1; goat2 = 2; break;
                    case 1 : goat1 = 0; goat2 = 2; break;
                    default : goat1 = 0; goat2 = 1; break;
                }
                if (Coin.flip() == HEADS) {
                    // switch
                    return pick == goat1 || pick == goat2;
                } else {
                    // stay
                    return pick == car;
                }
            }
        };

Not that I doubt the bare bones strategy code because if you analyze this version, it can be reduced to the simplified one that ignores the non-essential elements. This still gives a 50% probability of winning just as the simplified one does.

[Liutauras Vilda]

Piet, that's very complicated what you said, so I don't understand a lot, but, is my reasoning correct (in simple words speaking)?

We know that:
By staying with an original pick the chance of winning is 33.3% roughly.
By switching from an original pick the chance of winning is 66.6% roughly.

Now, given we know the proportions of wins by staying and switching, each of those proportions get halved by flipping a coin, because in half of the meant to win cases by staying we'd force to switch, hence loose, and the same with switch proportion, in half of those we'd force to stay instead.

Now the sum of wins from stay and switch is what adds up to a sum which is proportionally a 50% of wins.

Where ~16.6% wins derived from staying and ~33.3% from switching.

[Piet Souris]

Correct!

[Junilu Lacar]

I think what's interesting is that simply knowing and following a strategy can change the probability of winning. For all intents and purposes, however, since contestants only play one game  and they're done, there seems to be no practical difference between 50% chances and 66.67% chance of winning. It's only if the contestants were to play the game multiple times that it would really matter. It matters more to the people who supply the prize because it would be to their advantage for contestants to consistently choose to stay.

[Piet Souris]

Congratulations, Junilu!

Your topic got a mentioning in the October 2022 Journal, and so you earn a cow.