# Monty Hall problem generalized to $n$ doors

Generalize the Monty Hall problem where there are $n \geq 3$ doors, of which Monty opens $m$ goat doors, with $1 \leq m \leq n$.
Original Monty Hall Problem: There are $3$ doors, behind one of which there is a car (which you want), and behind the other two of which there are goats (which you don’t want). Initially, all possibilities are equally likely for where the car is. You choose a door, which for concreteness we assume is Door $1$. Monty Hall then opens a door to reveal a goat, and offers you the option of switching. Assume that Monty Hall knows which door has the car, will always open a goat door and offer the option of switching, and as above assume that if Monty Hall has a choice between opening Door $2$and Door $3$, he chooses Door $2$ and Door $3$ with equal probability .
Find the probability that the strategy of always switching succeeds, given that Monty opens Door $2$.

My approach:
Let $C_i$ be the event that car is behind the door $i$, $O_i$ be the event that Monty opened door $i$ and $X_i$ be the event that intially I chose door $i$. Here $i=1,2,3,...,n$.
Let's start with case where I chose $X_1$. Then:
$P(O_{j_1, j_2, ..., j_m}|C_1, X_1) = {{n-1}\choose{m}}(\frac{1}{n-1})^m$, here $j \in$ {$m$ doors out of $n-1$, i.e., exclude Door$1$ }
$P(O_{k_1, k_2, ..., k_m}|C_t, X_1) = {{n-2}\choose{m}}(\frac{1}{n-2})^m$, here $k \in$ {$m$ doors out of $n-2$, i.e., exclude Door$1$ & Door$t$}, $t \in$ {$2,3, ..., n$}
Also, $P(C_r|X_s) = \frac{1}{n}$, here $r,s \in$ {$1,2,...,n$}

Probability of winning by switching is,

$$P(C_3 | O_{k_1, k_2, ..., k_m}, X_1) = \frac{P(O_{k_1, k_2, ..., k_m}|C_3, X_1).P(C_3|X_1)}{P(O_{m-doors}|X_1)}$$

$$= \frac{P(O_{k_1, k_2, ..., k_m}|C_3, X_1).P(C_3|X_1)}{P(O_{j_1, j_2, ..., j_m}|C_1, X_1).P(C_1|X_1) + \sum_{t=2}^n(P(O_{k_1, k_2, ..., k_m}|C_t, X_1).P(C_t|X_1))}$$

$$= \frac{{{n-2}\choose{m}}(\frac{1}{n-2})^m.\frac{1}{n}}{(\frac{1}{n}).({{n-1}\choose{m}}(\frac{1}{n-1})^m + {{n-2}\choose{m}}(\frac{1}{n-2})^m.(n-1))}$$

$$= \frac{(n-m-1)(n-1)^{m-1}}{(n-2)^m + (n-m-1)(n-1)^m}$$

However, the correct answer is $\frac{(n-1)}{(n-m-1).n}$. Any insights to what I have done wrong.

A correct answer to the problem has been posted. But you asked where your approach went wrong.

Suppose the event $C_1 \cap X_1$ is given. In that event, according to the rules of the game, Monty will open $m$ doors. Apparently you have no information that would make one set of doors more likely to be opened than another, I assume every set of doors is equally likely. (You mention $\frac12 \geq p \geq 1$ at one point, but it seems to be for the three-door problem, not the generalized problem, and you ignore it in your solution.)

Since there are $\binom{n-1}{m}$ distinct sets of doors that Monty could open, the probability to open the set $J = \{j_1,j_2,\ldots,j_m\}$ (where $1\not\in J$), given $C_1 \cap X_1,$ is $$P(O_{j_1, j_2,\ldots, j_m}\mid C_1\cap X_1) = \frac{1}{\binom{n-1}{m}}.$$

That's one error in your computation.

Notice that in the event $X_1,$ just like in the event $C_1\cap X_1,$ there are $\binom{n-1}{m}$ distinct sets of doors that Monty could open, and every set of doors is equally as likely as any other. (Every set is not equally likely when $C_2\cap X_1,$ but each of the events $C_2,$ $C_3,$ $C_4,$ and so forth is as just as likely as $C_2$; by symmetry, when all is added up, no subset of doors is more likely than another.) Therefore $$P(O_{j_1, j_2,\ldots, j_m}\mid X_1) = \frac{1}{\binom{n-1}{m}}.$$

If $C_1 \cap X_t$ is given, where $t \neq 1,$ Monty must open $m$ of the remaining $n - 2$ doors. Following reasoning similar to the above, but considering that there are only $n-2$ available doors, the probability to open any particular set $K = \{k_1, k_2, \ldots , k_m\},$ where $1 \not\in K$ and $t \not\in K,$ is $$P(O_{k_1, k_2,\ldots, k_m}\mid C_1\cap X_t) = \frac{1}{\binom{n-2}{m}}.$$

That's another error in your computation.

Since Monty must open some set of $m$ doors no matter where the car is or which door you chose, $P(O_\mathrm{m-doors} \mid X_1) = 1,$ not what you substituted. But in fact it was an error to put that probability where you put it in the first place, because $$P(C_3 \mid O_{k_1, k_2,\ldots, k_m} \cap X_1) \neq \frac{P(O_{k_1, k_2,\ldots, k_m} \mid C_3\cap X_1) P(C_3 \mid X_1)} {P(O_\mathrm{m-doors} \mid X_1)}.$$

A formula that you could have used is one that considers the same set of $m$ doors in all three places where $m$ doors occur in the equation, \begin{align} P(C_3 \mid O_{k_1, k_2,\ldots, k_m} \cap X_1) &= \frac{P(O_{k_1, k_2,\ldots, k_m} \mid C_3\cap X_1) P(C_3 \mid X_1)} {P(O_{k_1, k_2,\ldots, k_m} \mid X_1)} \\ &= \frac{\left(1 / \binom{n-2}{m}\right) (1/n)} {\left(1 / \binom{n-1}{m}\right)} \\ &= \frac{n - 1}{n(n - m - 1)}. \end{align}

• Thanks @DavidK for taking time. This is extremely helpful. I have one more question - How did you arrive at $P(O_{k_1, k_2,\ldots, k_m} \mid X_1) = \left(1 / \binom{n-1}{m}\right)$. I am thinking on following lines: $P(O_{k_1, k_2,\ldots, k_m} \mid X_1) = \left(\frac{1}{\binom{n-1}{m}}.\frac{1}{n}\right) + \left(\frac{1}{\binom{n-2}{m}}.\frac{1}{n}\right).\left(\frac{1}{n-1}\right)$ – Gerry Mar 2 '18 at 14:17
• It's a simple symmetry argument, same as the others. I'm trying to guess how you arrived at your result, but I don't see even a mistaken way to arrive at it. – David K Mar 2 '18 at 15:33
• Somehow I am still not able to convince myself as to how come $P(O_{k_1, k_2,\ldots, k_m} \mid C_1\cap X_1) = P(O_{k_1, k_2,\ldots, k_m} | X_1)$ ? – Gerry Mar 2 '18 at 16:13
• How about following approach by conditioning on $C_i$s: $P(O_{j_1, j_2,\ldots, j_m} \mid X_1) = P(O_{j_1, j_2,\ldots, j_m} \mid C_1\cap X_1) .P(C_1 \mid X_1) + \sum_{t=2}^n\left(P(O_{k_1, k_2,\ldots, k_m} \mid C_t\cap X_1) .P(C_t \mid X_1)\right) = \left(\frac{1}{\binom{n-1}{m}}.(\frac{1}{n})\right) + \sum_{t=2}^n\left(\frac{1}{\binom{n-2}{m}}.(\frac{1}{n})\right) = \left(\frac{1}{\binom{n-1}{m}}.(\frac{1}{n})\right) + \left((n-1).\frac{1}{\binom{n-2}{m}}.(\frac{1}{n})\right)$ – Gerry Mar 2 '18 at 18:08
• The terms of the sum are not all equal. When $t \in \{k_1,\ldots,k_m\}$ the term is zero. So instead of $\frac{n-1}{\binom{n-2}{m}}\cdot\frac1n,$ your sum should be $\frac{n-m-1}{\binom{n-2}{m}}\cdot\frac1n.$ This is equal to $\frac{n-1}{\binom{n-1}{m}}\cdot\frac1n$ (which can be verified by expanding the numerators of the binomial coefficients and doing a couple of judicious cancellations). Adding that to $\frac{1}{\binom{n-1}{m}}\cdot\frac1n,$ we get $\frac{1}{\binom{n-1}{m}}.$ – David K Mar 2 '18 at 20:55

If your initial door is the car, the switching strategy fails.

$\frac{n-1}{n}$ of the time, your initial door is not the car. Then excluding your initial door and the $m$ goat doors, the car must be in one of the $n-m-1$ remaining doors, and presumably the switching strategy picks uniformly at random. So, the probability that switching succeeds is $\frac{n-1}{n} \cdot \frac{1}{n-m-1}$.

• I agree yours is an elegant solution. Would it be possible for you to comment on where I have gone wrong in my verbose solution? This approach yielded correct solution here: math.stackexchange.com/questions/2671238/… – Gerry Mar 2 '18 at 3:17