User:Mathsid

Generalized Monty Hall Problem

We will consider generalizations of the classical problem with 3 doors and 1 prize discussed above to N doors with k prizes.

Pursuing the more general problems makes it difficult to use heuristic (and often erroneous) arguments and forces one to more precisely formulate exactly what problems are to be solved and what assumptions are being made to execute their solution. Rather than doors, we will formulate these problems in terms of boxes and prizes in boxes.

Rules:
(a) the player initially selects one of N boxes.
(b) The host cannot open a box with a prize and must open exactly p of the N-1 remaining boxes that do not contain a prize.
(c) The player must be then given an opportunity to exchange the box previously chosen with one of the q = N - 1 - p remaining unopened boxes.

The rules show that p + q = N-1 and that p ≤ N-1-k. Therefore q ≥ N-1 –(N – 1 –k) = k. For completeness, we allow the possibility that p = 0, i.e. the host opens no box.

Problems

(1) Find probability that the box initially chosen contains a prize.
(2) Find the conditional probability that the player wins a prize given that it is known that k specific boxes are empty and that the player does not exchange the previously chosen box with one of the remaining unopened boxes.
(3) Find the conditional probability that the player wins a prize given that it is known that k specific boxes are empty and that the player does exchange the previously chosen box with one of the remaining unopened boxes.

We assume the boxes are numbered 1, 2, ... , N. Since all probabilities to be considered are conditional on knowing the box initially chosen, and as this information is available to both player and host, we can assume with no loss of generality (by renumbering the boxes if necessary) that the player initially chose box 1.

Notation:

P(A): probability of A.
P(A|B): conditional probability of A given B.
A^c: complement of A.
A\B = A $\,\cap$ B^c

C_k : the set of subsets of size k of {1, …, N}

X : a random variable with values in C_k. X is the set of boxes with prizes.

R_p(x) : is set of all subsets of size p of {2, …, N} The collection R_p(x) is set of all possible sets of boxes that can be opened if the prize set is x, $x\in C_{k}$.

D_p(x) = {2, …, N} \R_p(x): is the set of all possible boxes that can remain if the prize set is x. A set s in R_p (x) has size q and contains x if $1\notin x$ and x\ {1} if $1\in x$.

$\Omega _{xs}$:the conditional probability that player wins a prize player if the player switches given X = x and S = s.

For B a subset of {1,...,N}

$I_{B}(t)=\left\{{\begin{aligned}&1\,\,if\,\,t\in B\\&0\,\,if\,\,t\in B\\\end{aligned}}\right.$

$h(x,s)=\left\{{\begin{aligned}&1\,\,if\,\,x\backslash \{1\}\subset s\,\\&0\,\,if\,x\backslash \{1\}\not \subset s\\\end{aligned}}\right.$

A: the event the player switches and wins a prize.

Problems 1 – 3 in the notation just introduced are:

${\begin{aligned}&(1)\,\,\,\,\,\,\,\,P(1\in X).\\&(2)\,\,\,\,\,\,\,P(1\in X|S=s).\\&(3)\,\,\,\,\,\,\,P(A\,|X=s).\\\end{aligned}}$

Solutions
The calculations of the probabilities needed in problems 1 – 3 depend of course on the distribution of X as well as the conditional distribution of S given X. Initially we will solve the problems making no assumptions about these distributions. These distributions are not actually made explicit even in the classical problem of 1 prize and 3 doors though the “usual assumptions” in the classical case are that X is uniformly distributed and that conditional distribution of S given X is either fixed by the rules or uniformly distributed over its possible values. In the generalization considered here we call this the “every thing uniform case” and we will present explicit solutions to the 3 problems in this case. In general the distributions of X as well as the conditional distribution of S given X would be known to the host and could, in fact, be considered a strategy of the host so certainly the host could compute the needed probabilities. However, generally the player would not know these distributions and therefore could not calculate the needed probabilities and therefore, except in certain special cases discussed below, could not determine if switching or remaining with the initially chosen box was a better choice.

We note that the rules demand that $P(S=s|X=x)=0\,\,if\,\,x\backslash \{1\}\not \subset s$.

Hence
$(1)\,\,\,\,\,\,\,\,P(S=s|X=x)=P(S=s|X=x)h(x,s)$.

Problem 1
$(2)\,\,\,\,\,\,\,\,P(win)=P(1\in X)=\sum \limits _{x}{I_{x}(1)}P(X=x)$.

To solve problems 2 and 3 we need to compute P(S = s). To this end let

$(3)\,\,\,\,\,\,\,\,E_{1}=\sum \limits _{x}{P(S=s|X=x)I_{x}(1)h(x,s)P(X=x)}$
and

$(4)\,\,\,\,\,\,\,\,E_{2}=\sum \limits _{x}{P(S=s|X=x)I_{x^{c}}(1)h(x,s)P(X=x)}$
. Then
$(5)\,\,\,\,\,\,\,\,P(S=s)=E_{1}+E_{2}.$

Problem 2

$(6)\,\,\,\,\,\,\,\,P(win\,\,and\,\,not\,switch|S=s)={\frac {E_{1}}{E_{1}+E_{2}}}={\frac {1}{1+{\frac {E_{2}}{E_{1}}}}}$

Problem 3
There are two possible routes to win if the player switches. One is that box 1 has a prize and the player exchges for one of the k-1 prize box in s and the other is that box 1 does not have a prize and the player switches for one of the k boxes in s that contain a prize. Reflecting the possibilities let

$(7)\,\,\,\,\,\,\,\,{E}'_{1}=\sum \limits _{x}{P(S=s|X=x)\Omega _{xs}I_{x}(1)h(x,s)P(X=x)}$
and

$(8)\,\,\,\,\,\,\,\,{E}'_{2}=\sum \limits _{x}{P(S=s|X=x)\Omega _{xs}I_{x^{c}}(1)h(x,s)P(X=x)}.$
Then

$(9)\,\,\,\,\,\,\,\,P(win\,\,and\,\,\,switch|S=s)={\frac {{E}'_{1}+{E}'_{2}}{E_{1}+E_{2}}}\,$

Case where all distributions are uniform

In this special case the computations needed reduce to counting the various possiblilities. There are in all

$\left({\begin{aligned}&N\\&k\\\end{aligned}}\right)$
subsets of size k of {1,...,N} of which

$\left({\begin{aligned}&N-1\\&k-1\\\end{aligned}}\right)$ contain 1 and $\left({\begin{aligned}&N-1\\&\,\,\,k\\\end{aligned}}\right)$ do not contain 1. Hence
$(10)\,\,\,\,\,\,\,\,P(win)={\frac {\left({\begin{aligned}&N-1\\&k-1\\\end{aligned}}\right)}{\left({\begin{aligned}&N\\&k\\\end{aligned}}\right)}}={\frac {k}{N}}$.
Given an x which contains 1 there are q-(k-1)non prize boxes that are in s and these can be selected from N-1-(k-1) possible boxes. Thus

$(11)\,\,\,\,\,\,\,\,P(S=s|X=x)I_{x}(1)h(x,s)=\,\,{\frac {1}{\left({\begin{aligned}&N-k\\&q+1-k\\\end{aligned}}\right)}}I_{x}(1)h(x,s)$
Similarly,given an x which does not contain 1 there are q-k non-prize boxes to be selected from N-1-k possiblities. Thus

$(12)\,\,\,\,\,\,\,\,P(S=s|X=x)I_{x^{c}}(1)h(x,s)={\frac {1}{\left({\begin{aligned}&N-1-k\\&q-k\\\end{aligned}}\right)}}I_{x^{c}}(1)h(x,s).$

The sum

$\sum \limits _{x}{h(x,s)I_{x}}(1)$
is the number of choices for the set x \{1} of prize boxes contained in s. Thus

$(13)\,\,\,\,\,\,\,\,\sum \limits _{x}{h(x,s)I_{x}}(1)=\left({\begin{aligned}&q\\&k-1\\\end{aligned}}\right),$

$(14)\,\,\,\,\,\,\,\,\sum \limits _{x}{h(x,s)I_{x^{c}}}(1)=\left({\begin{aligned}&q\\&k\\\end{aligned}}\right).$
By (3),(11), and (13)

$(15)\,\,\,\,\,\,\,\,E_{1}={\frac {1}{\left({\begin{aligned}&N-k\\&q+1-k\\\end{aligned}}\right)}}{\frac {\left({\begin{aligned}&q\\&k-1\\\end{aligned}}\right)}{\left({\begin{aligned}&N\\&k\\\end{aligned}}\right)}}$

and by (4), (12), and (14)

$(16)\,\,\,\,\,\,\,\,E_{2}={\frac {1}{\left({\begin{aligned}&N-1-k\\&q-k\\\end{aligned}}\right)}}{\frac {\left({\begin{aligned}&q\\&k\\\end{aligned}}\right)}{\left({\begin{aligned}&N\\&k\\\end{aligned}}\right)}}$.
Then a small calculation shows

${\frac {E_{2}}{E_{1}}}={\frac {\left({\begin{aligned}&q\\&k\\\end{aligned}}\right)}{\left({\begin{aligned}&N-1-k\\&q-k\\\end{aligned}}\right)}}{\frac {\left({\begin{aligned}&N-k\\&q+1-k\\\end{aligned}}\right)}{\left({\begin{aligned}&q\\&k-1\\\end{aligned}}\right)}}={\frac {N-k}{k}}$
Thus

$1+{\frac {E_{2}}{E_{1}}}=1+{\frac {N-k}{k}}={\frac {N}{k}}$. Consequetly (6) shows

$(17)\,\,\,\,\,\,\,\,\,P(win\,\,and\,\,not\,\,switch|S=s)={\frac {E_{1}}{E_{1}+E_{2}}}={\frac {k}{N}}.$
Thus in the uniform case considered here the additional information gained by the player knowing that various boxes are empty does not change the chance that the player wins a prize if the player remains with box initially selected.
To determine the solution to problem 3 we note that in the everything uniform case considered here

$\Omega _{xs}=\left\{{\begin{aligned}&{\frac {k-1}{q}}\,\,\,if\,\,1\in x\\&{\frac {k}{q}}\,\,if\,\,1\notin x\\\end{aligned}}\right.$
Consequently,

${E}'_{1}={\frac {k-1}{q}}E_{1}$
and

${E}'_{2}={\frac {k}{q}}E_{1}.$
Thus
${\frac {{E}'_{1}+{E}'_{2}}{E_{1}+E_{2}}}={\frac {k-1}{q}}{\frac {E_{1}}{E_{1}+E_{2}}}+{\frac {k}{q}}\left(1-{\frac {E_{1}}{E_{1}+E_{2}}}\right)={\frac {k(N-1)}{qN}}$
Hence by (9)
$(18)\,\,\,\,\,\,\,\,P(win\,\,and\,\,switch|S=s)={\frac {k(N-1)}{qN}}.$
Comparison of (14 )and 15)shows

$(19)\,\,\,\,\,\,\,\,{\frac {P(win\,\,switch|S=s)}{P(win\,\,not\,\,switch)}}={\frac {N-1}{q}}.$
Thus, swiching has a ${\frac {N-1}{q}}$ advantage. In the extreme case when no boxes are opened (q = N - 1) there is no advantag and the chance of winning with or without switching is the same as the prior probability of winning a prize. At the other extreme when q = k the player is ${\frac {N-1}{k}}$ times more likely to win a prize by switching.
The case of N boxes and 1 prize with all distributions uniform seems to been discussed by D. L. Fergeson (1975) in a letter to Selvin (Selvin 1975b) but I know reference to the case of k > 1 prizes.

Host opens maximum number of boxes ( k = q)
When k = q the set s must be the prize set x if $1\notin x$. Additionally,

$\Omega _{xs}=1\,\,if\,\,1\notin x,\,\,s=x.$
Therefore, in this case, $E_{2}={E}'_{2}=P(X=s).$ Specializing to the case when X is uniformly distributed, $\Omega _{xs}={\frac {k-1}{k}},\,\,if\,\,1\in x$ and setting

$\sum \limits _{x}{P(S=s|X=x)I_{x}(1)h(x,s)=\alpha }$
we find using (6) and (9) that

${\begin{array}{*{35}l}{}&P(win\,\,not\,\,switch)={\frac {\alpha }{\alpha +1}}\\{}&and\\{}&P(win\,\,switch)={\frac {\alpha {\frac {k-1}{k}}+1}{\alpha +1}}.\\\end{array}}$
Therefore,
$P(win\,\,switch)-P(win\,\,not\,\,switch)=1-{\frac {\alpha }{k}}.$ Hence no matter how P(S =s |X = x) is determined it is always advantageous for the player to switch. However, in cases when X is not uniformly distributed it may be advantageous to to remain with the initially chosen box. For example, if k = 1 and P(X=N) = 0 then P(win switch|S={N}) = 0.

Related Problem

Mathematically, The extended Monty Hall problem discussed here is the same as the following extension of the * Three Prisoners Problem. <br\> There are N prisoners of which k will be selected at random and set free and the remaining N - k will remain in jail. We refer to the prisoners as 1, …, N. Prisoner 1 knows the are to be k freed and asks the guard to give him the names of p of the prisoners who will remain claiming that information will not change his chance of being amongst those chosen to go free. We assume the guard does not lie and never tells prisoner 1 if he is to be freed if he is one of those to be freed. Is the prisoner correct? If the guard offers him the opportunity to switch with an unnamed prisoner is this advantageous? <br\> If we identify the prisoners with the boxes and going free with the prizes we see that the prisoner problem is mathematically the same as the extended Monty Hall problem.

Further extension of the Monty Hall problem

A further generalization of the Monty Hall problem allows the player to initially choose m >=1 boxes. The host then reveals p empty boxes and the player now has the option to exchange r of his initially chosen boxes with r of the q unopened boxes. However, the player can only keep 1 of the prizes if his final set of boxes contains more than one prize. As before, the player knows that there are k prizes and that the host will open p boxes. The player is at liberty to choose r. For mathematical completeness we allow the case r = 0, which of course, corresponds to the case that the player remains with the initial choice of boxes. In this generalization, the 2nd and 3rd problems coalesce with r =0 corresponding to not switching at all (problem 2) and an additional problem is suggested in determining what is an optimal r.

With this generalization it is convenient to the number the boxes 1, 2, …, m+N and let the players initial boxes be 1, … , m. The constraints on the quantities are:

${\begin{aligned}&(a)\,\,p\leq N-k,\\&(b)\,\,q\geq k,\\&(c)\,\,r\leq \min(m,q),\\\end{aligned}}$

Additional notation

${\begin{aligned}&X:\,\,\,\,\,\,\,the\,\,subset\,\,of\,\,size\,\,k\,\,of\,\{1,\ldots ,m+N\}\,\,of\,\,prizes.\\&X_{0}=X\cap \{1,\ldots ,m\}:\,\,\,\,\,\,the\,\,set\,\,of\,\,prizes\,\,in\,\,\{1,\ldots ,m\}.\\&X_{1}=X\cap \{m+1,\ldots ,m+N\}:\,\,\,\,\,\,the\,\,set\,\,of\,\,prizes\,\,in\,\,\{m+1,\ldots ,m+N\}.\\&|X_{0}|:\,\,the\,\,number\,\,of\,\,po\operatorname {int} s\,\,\,in\,\,\,X_{0}.\\&h_{0}(x)=\left\{{\begin{aligned}&\left\{1\,\,if\,\,x_{0}\subseteq \right.\,\{1,\ldots ,m\},\\&0\,\,elsewhere.\\\end{aligned}}\right.\\&h_{1}(s,x)=\left\{{\begin{aligned}&1\,\,if\,x_{1}\subseteq s,\\&0\,\,elsewhere.\\\end{aligned}}\right.\\&I_{j}(x)=\left\{{\begin{aligned}&1\,\,\,if\,|X_{0}|\,=j,\\&0\,\,if\,|X_{0}|\,\neq j.\,\\\end{aligned}}\right.\\\end{aligned}}$

Solutions in the everything uniform case

We will limit the consideration of the expanded problem to the case X is uniformly distributed, the conditional distribution of S given X is uniformly distributed on its permissible set of values, and the sets of size r chosen from {1, …, m} and S are conditional on S and X uniformly distributed. Additionally, it is somewhat easier to state the results in terms of the probability of not getting a prize.

For easy reference we list some facts:

${\begin{aligned}&(20)\,\,\,\,\,\,\,\,{\frac {\left({\begin{aligned}&a\\&b\\\end{aligned}}\right)}{\left({\begin{aligned}&a-1\\&b-1\\\end{aligned}}\right)}}={\frac {a}{b}},\\&(21)\,\,\,\,\,\,\,\,{\frac {\left({\begin{aligned}&a-1\\&\,\,\,\,b\\\end{aligned}}\right)}{\left({\begin{aligned}&a\\&b\\\end{aligned}}\right)}}={\frac {a-b}{a}},\\&(22)\,\,\,\,\,\,\,\,{\frac {\left({\begin{aligned}&\,\,\,\,a\\&b-1\\\end{aligned}}\right)}{\left({\begin{aligned}&a\\&b\\\end{aligned}}\right)}}={\frac {b}{a-b-1}},\\&(23)\,\,\,\,\,\,\,\,\sum \nolimits _{x}{h_{0}(}x)h_{1}(s,x)I_{j}(x)=\left({\begin{aligned}&m\\&j\\\end{aligned}}\right)\left({\begin{aligned}&q\\&k-j\\\end{aligned}}\right).\\&\,\\\end{aligned}}$

Unconditional probability of no prize

$(24)\,\,\,\,\,\,\,\,P(win\,\,\,no\,\,prize)=P(X_{0}=\varnothing )={\frac {\left({\begin{aligned}&N\\&k\\\end{aligned}}\right)}{\left({\begin{aligned}&m+N\\&\,\,\,\,\,k\\\end{aligned}}\right)}}.$

Conditional probability of winning no prize given S

${\begin{aligned}&(25)\,\,\,\,\,\,\,\,\,\,P(S=s|X_{0}=x_{0},X_{1}=x_{1})I_{j}(x)={\frac {1}{\left({\begin{aligned}&N-k+j\\&q-k+j\\\end{aligned}}\right)}}h_{0}(x)h_{1}(s,x)I_{j}(x),\\&(26)\,\,\,\,\,\,\,\,\,P(X_{0}=x_{0},X_{1}=x_{1})={\frac {1}{\left({\begin{aligned}&N+m\\&\,\,\,\,\,k\\\end{aligned}}\right)}},\\&Using\,\,(23),\,(25)\,\,and\,\,(26)\\&(27)\,\,\,\,\,\,\,\,P(S=s)=\sum \limits _{j=0}^{\min(m,k,r)}{{\frac {\left({\begin{aligned}&q\\&k-j\\\end{aligned}}\right)\left({\begin{aligned}&m\\&j\\\end{aligned}}\right)}{\left({\begin{aligned}&N-k+j\\&q-k+j\\\end{aligned}}\right)\left({\begin{aligned}&N+m\\&\,\,\,\,\,k\\\end{aligned}}\right)}}.}\\\end{aligned}}$

If we switch r boxes and there are j prizes in {1,…,m} then the player wins no prize if and only if all of the j prize boxes amongst those {1,…,m} are included in the r boxes switched and none of the k – j boxes in the set s are included in those switched from the set s. Call this the event C_r. Then

${\begin{aligned}&(28)\,\,\,\,\,\,\,\,P(C_{r}|S=s,X=x)I_{j}(x)\,={\frac {\left({\begin{aligned}&m-j\\&\,\,\,\,r\\\end{aligned}}\right)}{\left({\begin{aligned}&m\\&r\\\end{aligned}}\right)}}{\frac {\left({\begin{aligned}&q-k+j\\&\,\,\,\,\,\,\,r\\\end{aligned}}\right)}{\left({\begin{aligned}&q\\&r\\\end{aligned}}\right)}}I_{j}(x).\\&Using\,\,\,(25),\,\,(26),\,\,(27),and\,\,\left(28\right)\\&(29)\,\,\,\,\,\,\,\,\,P(C_{r}|\,S=s)={\frac {\sum \limits _{j=0}^{\min(k,m,r)}{\frac {\left({\begin{aligned}&m-j\\&r-j\\\end{aligned}}\right)\left({\begin{aligned}&q-k+j\\&\,\,\,\,\,\,\,r\\\end{aligned}}\right)\left({\begin{aligned}&m\\&j\\\end{aligned}}\right)\left({\begin{aligned}&q\\&k-j\\\end{aligned}}\right)}{\left({\begin{aligned}&m\\&r\\\end{aligned}}\right)\left({\begin{aligned}&q\\&r\\\end{aligned}}\right)\left({\begin{aligned}&N-k+j\\&q-k+j\\\end{aligned}}\right)}}}{\sum \limits _{j=0}^{\min(m,k)}{\frac {\left({\begin{aligned}&q\\&k-j\\\end{aligned}}\right)\left({\begin{aligned}&m\\&j\\\end{aligned}}\right)}{\left({\begin{aligned}&N-k+j\\&q-k+j\\\end{aligned}}\right)}}}}.\\&\,\\\end{aligned}}$

Case of k = 1 prize.
Formula (29) simplifies considerably for the special cases when m = 1 or k = 1. The case m = 1, reproduce the complement probability given in equation (17) for r = 0 and in equation (10) for r =1. Carrying out the calculations for the case k = 1 shows the denominator of (29) becomes

${\frac {N+m}{\left({\begin{aligned}&N\\&q\\\end{aligned}}\right)}}$<br\> while the numerator of (29) becomes

${\begin{aligned}&{\frac {\frac {Nq-r(N-q)}{q}}{\left({\begin{aligned}&N\\&q\\\end{aligned}}\right)}}.\\&Therefore\\&(30)\,\,\,\,\,\,\,\,\,P(C_{r}|\,S=s)={\frac {Nq-r(N-q)}{q}}.\\\end{aligned}}$

Since N – q ≥ 0 we see that the probability of losing is maximal for r = 0, i.e., not switching, and steadily declines with increasing r becoming minimal if the player exchanges the maximum number of boxes possible (r = min (m,q)).