The Monty Hall Game

Claude Boivin, Stat.ASSQ

2020-01-26

The Monty Hall Game

Let us recall the Monty Hall Game from its statement in the Wikipedia article 1 on the subject:

"Suppose you're on a game show. Three doors *A*, *B* and *C* are in front of you. Behind one door is a brand new car, and behind the two others, a goat. You are asked to pick one of the three doors. Then the host of the game, who knows what's behind the doors, opens one of the two remaining doors and shows a goat. He then asks you: "Do you want to switch doors or keep your initial choice?"

Say you have chosen the door A and the host has opened door B. The question now is: Is it to your advantage to switch your choice from door A to door C?"

Some notation to begin with

For each door A, B, C, consider the same frame of discernment (Fod) F with three possible values: \[F = \{car, goat 1, goat 2\}.\] I use (0,1)-vectors to identify each element of the frame. Hence, the element “car” is identified by the vector \((1, 0, 0)\), goat 1 by the vector \((0, 1, 0)\) and goat 2 by the vector \((0, 0, 1)\).

With this notation, any subset of F has a unique (0,1) representation. For example, the subset \(\{goat 1, goat 2\}\) is represented by the vector \((0, 1, 1)\).

Analysis of the problem

We have three things to consider:

  1. How the three doors are linked;
  2. Evidence pertaining to door A (choice of the contestant);
  3. Evidence pertaining to door B (the action of the host).

1. How the three doors are linked

There are six possible combinations of the car and the two goats behind the three doors A, B, C:

\(\{car, goat 1, goat 2\}\) \(\{car, goat 2, goat 1\}\) \(\{goat 1, car, goat 2\}\) \(\{goat 1, goat 2, car\}\) \(\{goat 2, car, goat 1\}\) \(\{goat 2, goat 1, car\}\).

These combinations are elements of the product space \(F_{ABC} = \prod(A, B, C)\). The number of elements of \(F_{ABC}\) is \(3^3 = 27\). The six possible dispositions of the car and goats determine a subset S of the Fod \(F_{ABC}\). A mass of 1 is allotted to this subset S.

I use the function bcaRel to code the desired relation between the doors.

3. Evidence pertaining to door B

But the host wanted to add some thrill to the game. He has opened door B and revealed a goat. The host has given us a small piece of evidence: Goat 1 or goat 2 was behind door B. Since the host knows what is behind each door, the mass value of this piece of evidence is: \(m({goat1, goat2}) = 1\).

Let’s translate this in R with function bca:

The hypergraph of the Monty Hall game

We now have all the elements of a small belief network made of one relation (MHABC_rel) between three variables: Door A, Door B, Door C, and two pieces of evidence coming from the Contestant (MHA_E) and the Host two (MHB_E). Variables A, B and C (doors) are the nodes of the graph. The edges (hyperedges) are the evidences MHA_E (named ev_A on the graph) and MHB_E (ev_B on the graph) and the relation MHABC_rel (r_ABC on the graph). We use the package igraph 2 to produce a bipartite graph corresponding to the desired hypergraph.

Now, the solution with the calculus of belief functions

Since we want to know if there is advantage to switch doors, our goal is the calculation of a belief function MHC attached to the variable of interest C (Door C). To obtain this belief function, we need to combine evidence for doors A (Contestant) and B (Host) with the relation linking the three doors in the product space \(F_{ABC}\). We will use a process of successive elimination of variables until only variable C remains.

The calculations involved follow the principles of the valuation language of Shenoy 3; see also 4. The variables are linked to functions (called valuations). A function can be a piece of evidence attached to a variable or a relation between two or more variables.

Three kinds of operations are involved in the calculations: a) the minimal (vacuous) extension of a mass function to a larger Fod; b) the combination of two mass functions by Dempster’s rule; c) the marginalization of a mass function, i.e. eliminating a variable to reduce the function to a smaller Fod.

First step: Eliminate variable A (Door A)

Using function extmin, we extend the mass function MHA_E to the space \(\prod(A, B, C)\); then we combine MHA_E extended with MHABC_rel, using functions dsrwon and nzdsr (normalization); finally, we use function elim to eliminate A by marginalizing to \(\prod(B, C)\). The mass function obtained is named MHBC. This gives a reduced network with B and C.

# 1. Extend MHA to the product space A x B x C
MHA_ext <- extmin(MHA_E, MHABC_rel )
"Evidence of Contestant extended to the product space A x B x C"
#> [1] "Evidence of Contestant extended to the product space A x B x C"
bcaPrint(MHA_ext)
#>                                                                                                                                                                 MHA_ext
#> 1                   car car car + car car goat1 + car car goat2 + car goat1 car + car goat1 goat1 + car goat1 goat2 + car goat2 car + car goat2 goat1 + car goat2 goat2
#> 2 goat1 car car + goat1 car goat1 + goat1 car goat2 + goat1 goat1 car + goat1 goat1 goat1 + goat1 goat1 goat2 + goat1 goat2 car + goat1 goat2 goat1 + goat1 goat2 goat2
#> 3 goat2 car car + goat2 car goat1 + goat2 car goat2 + goat2 goat1 car + goat2 goat1 goat1 + goat2 goat1 goat2 + goat2 goat2 car + goat2 goat2 goat1 + goat2 goat2 goat2
#>   specnb              mass
#> 1      1 0.333333333333333
#> 2      2 0.333333333333333
#> 3      3 0.333333333333333
#
# 2. Combine MHA_ext and MHABC_rel
MHA_ABC_comb <- dsrwon(MHA_ext,MHABC_rel)
# since  the measure of contradiction is 0, no need to normalize
MHA_ABC_comb$con
#> [1] 0
# "Subsets resulting from the combination of Expert 1 extended and r1"
bcaPrint(MHA_ABC_comb)
#>                        MHA_ABC_comb specnb              mass
#> 1 car goat1 goat2 + car goat2 goat1      1 0.333333333333333
#> 2 goat1 car goat2 + goat1 goat2 car      2 0.333333333333333
#> 3 goat2 car goat1 + goat2 goat1 car      3 0.333333333333333
#
# 3. Eliminate variable A
MHBC <- elim(MHA_ABC_comb, xnb = 1)
bcaPrint(MHBC)
#>                        MHBC specnb              mass
#> 1 goat1 goat2 + goat2 goat1      1 0.333333333333333
#> 2     car goat2 + goat2 car      2 0.333333333333333
#> 3     car goat1 + goat1 car      3 0.333333333333333

After this first step, the graph is updated.

The reduced belief network

#> + 4/4 vertices, named, from 1652a34:
#> [1] B    C    r_BC ev_B

Conclusion:

As we can see, we double our chances of winning the car if we switch from door A to door C.

Note that there is no loss of generality by fixing the choices in the analysis (door A for the contestant, door B for the host).

To be more specific and make a bridge with probability theory, we can add to our result all the elementary events that have 0 mass, so that we can see their measure of plausibility.

The function addTobca serves this purpose.

  1. https://en.wikipedia.org/w/index.php?title=Monty_Hall_problem&oldid=829292640↩

  2. Csardi G, Nepusz T: The igraph software package for complex network research, InterJournal, Complex Systems 1695. 2006. https://igraph.org↩

  3. P. P. Shenoy. A Valuation-Based Language for Expert systems. International Journal of Approximate Reasoning 1989, 3 383–411↩

  4. P. P. Shenoy. Valuation-Based Systems. Third School on Belief Functions and Their Applications, Stella Plage, France. September 30, 2015↩