Cars vs. Goats

There was an episode of NUMB3RS (113 - Man Hunt) that included a brief explanation of the Monty Hall Problem.

Monty Hall's "Let's Make A Deal" is gameshow where you choose a door to win either a goat or a car--the objective being to win the car.

Wikipedia has a pretty thorough article on the Monty Hall Problem, but I want to make my own little problem and proof using PMI, because I wuvvy wuv wuvs PMI so much, yes I do!


Cars vs. Goats (AKA: Monty Hall Problem)

Suppose there is a gameshow in which the player chooses a door. Behind any door is either a goat, or a car; and the objective is to pick the door with a car. After a door is chosen (but not opened), the host opens a door, behind which is a goat. Theplayer must then make a choice: stay with the chosen door, or switch to another door.

More specifically, let's deal with the case where there are c doors and only 1 car. That means, there are c - 1 goats, and the player can choose to switch to one of c - 2 remaining doors, with the objective of finding the car.

Scenario One: c = 3
In this case, there are three doors, and suppose the car is behind door three. There are three initial choices the player can make: door one, door two or door three. Then, the player can choose to either switch or stay.

Here are the results:

initial:	1	2	3
switch:	Car!	Car!	Goat
stay:	Goat	Goat	Car!

If we look at the switch row, we see that 2/3 result in cars.
If we look at the stay row, we see that 1/3 results in a car.

Thus, it is better to switch when there are three doors and one car.

Scenario One: c = 4
Let's suppose the car is behind door number four. The only real difference now is that there are two possible switch choices, but that's easy to take into consideration.

Results:

initial:	1	2	3	4
switch1:	Car!	Car!	Car!	Goat
switch2:	Goat	Goat	Goat	Goat
stay:	Goat	Goat	Goat	Car!

Looking at both switch rows, we see that 3/8 result in cars.
Looking at the stay row, we see that 1/4 results in a car.
Since 3/8 > 1/4, switching is still a better choice.

The remaining cases
Let's skip over the details of the next few cases. Let S be our probability of success in finding the car when choosing to switch, and c be the number of doors; still having only one car.

Summary:

c	3	4	5	6	7
S	2/3	3/8	4/15	5/24	6/35

Noticeable patterns:

• S_c = (c - 1) / [c (c - 2)]
  To simplify things let's separate the Numerator and the Denominator,
  
  let N_c = c - 1
  
  let D_c = c (c - 2)
• N_(c+1) = N_c + 1
  
• D_(c+1) = D_c + 2c + 1

Proof of pattern of S:

1. Prove that N_(c+1) = (c + 1) - 1

First, look at the best case of N_c = c - 1, ie: when c = 3

N₍₃₎ = (3) - 1

N₍₃₎ = 2

This is true!

Now prove all following cases are true; ie: prove N_(c+1) = (c+1) - 1

N(c+1) = Nc - 1
N(c+1) = (c - 1) + 1	Substitute.
N(c+1) = c	Simplify. Hoorays!

2. Prove that D_(c+1) = (c+1)(c+1 - 2)

First, look at the best case of D_c = c (c - 2), ie: when c = 3

D₍₃₎ = 3 (3 - 2)

D₍₃₎ = 3 (1)

D₍₃₎ = 3

This is true!

Now prove all following cases are true; ie: D_(c+1) = (c+1) (c+1 - 2)

D(c+1) = Dc + 2c - 1
D(c+1) = [c (c - 2)] + 2c -1	Substitute.
D(c+1) = c2 -2c + 2c - 1	Expand.
D(c+1) = c2 - 1	Simplify.
D(c+1) = (c + 1) (c - 1)	Difference of Squares. Hoorays!

Therefore,

S_c = (c - 1) / [c (c - 2)]

This doesn't really mean anything relevant yet, though. We've just proven that we always know our success rate, and not that switching is better than staying. Let's look at the staying data now.

Let T be the success rate of staying, and we'll compare with S.

c	3	4	5	6	7
T	1/3	1/4	1/5	1/6	1/7
S	2/3	3/8	4/15	5/24	6/35

Pretty dismal, eh? Let's prove that S > T. But first, we must prove that T always follows a pattern...

Patterns noticed in T:

T_c = 1 / c

T_(c+1) = (T_c) * c / (c + 1)

Prove that T_(c+1) = 1 / (c + 1)

Best case: c = 3

T₃ = 1 / 3

This is true!

All following:

T(c+1) = (Tc) * c / (c + 1)
T(c+1) = [1/c] * c / (c+1)	Substitute.
T(c+1) = c / [c (c + 1)]	Multiply through.
T(c+1) = 1 / (c + 1)	Simplify. Hoorays!

Prove that it is always better to switch:

Here's the final piece! We must prove that S_c > T_cProof by Contradiction.
Go!

Sc	<	Tc	Assume.
(c - 1) / [c (c - 2)]	<	1 / c	Substitute.
c (c - 1) / [c (c - 2)]	<	c / c	Multiply by c.
(c - 1) / (c - 2)	<	1	Since c > 2, this is most definitely false! In fact, (c-1)/(c-2) cannot even be equal to 1.  It is always greater than 1.   Since all our steps after the initial assumption of Sc <>c, that assumption must have been incorrect. Therefore, Sc > Tc  for all integers c > 2. Hoorays!

Thus, it is always better to switch.


I'll write something more journal-like later.
--Charissa