# Etiqueta: Combinatorics

## Monty Hall problem

Bertrand’s box paradox is a classic paradox of elementary probability theory. It was first posed by Joseph Bertrand in his Calcul des probabilités, published in 1889. There are three boxes: a box containing two gold coins, a box containing two silver coins, a box containing one gold coin and one silver coin. After choosing a box at random and withdrawing one coin […]

**Bertrand’s box paradox** is a classic paradox of elementary probability theory. It was first posed by Joseph Bertrand in his *Calcul des probabilités*, published in 1889.

There are three boxes:

- a box containing two gold coins,
- a box containing two silver coins,
- a box containing one gold coin and one silver coin.

After choosing a box at random and withdrawing one coin at random, if that happens to be a gold coin, it may seem that the probability that the remaining coin is gold is ^{1}?_{2}; in fact, the probability is actually ^{2}?_{3}. Two problems that are very similar are the Monty Hall problem and the Three Prisoners problem.

These simple but slightly counterintuitive puzzles are used as a standard example in teaching probability theory. Their solution illustrates some basic principles, including theKolmogorov axioms.

The **Monty Hall problem** is a brain teaser, in the form of a probability puzzle (Gruber, Krauss and others), loosely based on the American television game show *Let’s Make a Deal* and named after its original host, Monty Hall. The problem was originally posed in a letter by Steve Selvin to the *American Statistician* in 1975 (Selvin 1975a), (Selvin 1975b). It became famous as a question from a reader’s letter quoted inMarilyn vos Savant‘s “Ask Marilyn” column in *Parade* magazine in 1990 (vos Savant 1990a):

Suppose you’re on a game show, and you’re given the choice of three doors: Behind one door is a car; behind the others, goats. You pick a door, say No. 1, and the host, who knows what’s behind the doors, opens another door, say No. 3, which has a goat. He then says to you, “Do you want to pick door No. 2?” Is it to your advantage to switch your choice?

Vos Savant’s response was that the contestant should switch to the other door. (vos Savant 1990a)

The argument relies on assumptions, explicit in extended solution descriptions given by Selvin (1975b) and by vos Savant (1991a), that the host always opens a different door from the door chosen by the player and always reveals a goat by this action—because he knows where the car is hidden. Leonard Mlodinow stated: “The Monty Hall problem is hard to grasp, because unless you think about it carefully, the role of the host goes unappreciated.” (Mlodinow 2008) It is also assumed that the contestant prefers to win a car, rather than a goat.

Contestants who switch have a 2/3 chance of winning the car, while contestants who stick to their choice have only a 1/3 chance. One explanation notices that 2/3 of the time, the initial choice of the player is a door hiding a goat. The host is then forced to open the other goat door, and the remaining one must, therefore, hide the car. “Switching” only fails to give the car when the player picks the “right” door to begin with, which only has a 1/3 chance.

Many readers of vos Savant’s column refused to believe switching is beneficial despite her explanation. After the problem appeared in *Parade*, approximately 10,000 readers, including nearly 1,000 with PhDs, wrote to the magazine, most of them claiming vos Savant was wrong (Tierney 1991). Even when given explanations, simulations, and formal mathematical proofs, many people still do not accept that switching is the best strategy (vos Savant 1991a). Paul Erd?s, one of the most prolific mathematicians in history, remained unconvinced until he was shown a computer simulation confirming the predicted result (Vazsonyi 1999).

The Monty Hall problem has attracted academic interest from the surprising result and simple formulation. Variations of the Monty Hall problem are made by changing the implied assumptions and can create drastically different consequences. For one variation, if Monty only offers the contestant a chance to switch when the contestant initially chose the door hiding the car, then the contestant should *never* switch. For another variation, if Monty opens another door randomly and happens to reveal a goat, then *it makes no difference* (Rosenthal, 2005a), (Rosenthal, 2005b).

The problem is a paradox of the *veridical* type, because the correct result (you should switch doors) is so counterintuitive it can seem absurd, but is nevertheless demonstrably true. The Monty Hall problem is mathematically closely related to the earlier Three Prisoners problem and to the much older Bertrand’s box paradox.

The problem continues to attract the attention of cognitive psychologists. The typical behaviour of the majority, i.e., not switching, may be explained by phenomena known in the psychological literature as: 1) the endowment effect (Kahneman et al., 1991); people tend to overvalue the winning probability of the already chosen – already “owned” – door; 2) the status quo bias (Samuelson and Zeckhauser, 1988); people prefer to stick with the choice of door they have already made; 3) the errors of omission vs. errors of commission effect (Gilovich et al., 1995); all else considered equal, people prefer that any errors that they are responsible for to have occurred through ‘omission’ of taking action rather than through having taken an explicit action that later becomes known to have been erroneous. Experimental evidence confirms that these are plausible explanations which do not depend on probability intuition (Kaivanto et al., 2014; Morone and Fiore, 2007).

### Criticism of the simple solutions

As already remarked, most sources in the field of probability, including many introductory probability textbooks, solve the problem by showing the conditional probabilities the car is behind door 1 and door 2 are 1/3 and 2/3 (not 1/2 and 1/2) given the contestant initially picks door 1 and the host opens door 3; various ways to derive and understand this result were given in the previous subsections. Among these sources are several that explicitly criticize the popularly presented “simple” solutions, saying these solutions are “correct but … shaky” (Rosenthal 2005a), or do not “address the problem posed” (Gillman 1992), or are “incomplete” (Lucas et al. 2009), or are “unconvincing and misleading” (Eisenhauer 2001) or are (most bluntly) “false” (Morgan et al. 1991). Some say that these solutions answer a slightly different question – one phrasing is “you have to announce *before a door has been opened* whether you plan to switch” (Gillman 1992, emphasis in the original).

The simple solutions show in various ways that a contestant who is determined to switch will win the car with probability 2/3, and hence that switching is the winning strategy, if the player has to choose in advance between “always switching”, and “always staying”. However, the probability of winning by *always* switching is a logically distinct concept from the probability of winning by switching *given the player has picked door 1 and the host has opened door 3*. As one source says, “the distinction between [these questions] seems to confound many” (Morgan et al. 1991). This fact that these are different can be shown by varying the problem so that these two probabilities have different numeric values. For example, assume the contestant knows that Monty does not pick the second door randomly among all legal alternatives but instead, when given an opportunity to pick between two losing doors, Monty will open the one on the right. In this situation the following two questions have different answers:

- What is the probability of winning the car by
*always*switching? - What is the probability of winning the car
*given the player has picked door 1 and the host has opened door 3*?

The answer to the first question is 2/3, as is correctly shown by the “simple” solutions. But the answer to the second question is now different: the conditional probability the car is behind door 1 or door 2 given the host has opened door 3 (the door on the right) is 1/2. This is because Monty’s preference for rightmost doors means he opens door 3 if the car is behind door 1 (which it is originally with probability 1/3) or if the car is behind door 2 (also originally with probability 1/3). For this variation, the two questions yield different answers. However as long as the initial probability the car is behind each door is 1/3, it is never to the contestant’s disadvantage to switch, as the conditional probability of winning by switching is always at least 1/2. (Morgan et al. 1991)

Players who STAY have won 49040 cars out of 145987 games yielding a winning percentage of 34%

players who SWITCH have won 68356 cars out of 103063 games yielding a winning percentage of 66%

## Video Transcript:

You’re on a game show and there are three doors in front of you. The host, Monty Hall, says, “Behind one door is a brand new car. Behind the other two doors are goats. Pick a door!” You think, “Well, it doesn’t matter which door I choose, every door has a 1/3 chance of having the car behind it.” So, you choose door number 1. Now it gets interesting. Monty, the host, who knows where the car is, opens door number 2 and reveals a goat. The host always opens a door to reveal a goat. The host says, “If you want, you can switch to door number 3.” What should you do? Stay with your original choice or switch to the other door? All right, so what are you going to do? Stay or switch? Well, it’s a fifty-fifty chance of winning the car in either door. Right? [Wrong!] You actually double your chances of winning the car by switching doors. And that is why the Monty Hall Problem is so evasive!

Choose an explanation to the Monty Hall Problem:

1/3 vs 2/3 – Solution #1 to the Monty Hall Problem

There is a 1/3 chance of the car being behind door number 1 and a 2/3 chance that the car isn’t behind door number 1. After Monty Hall opens door number 2 to reveal a goat, there’s still a 1/3 chance that the car is behind door number 1 and a 2/3 chance that the car isn’t behind door number 1. A 2/3 chance that the car isn’t behind door number 1 is a 2/3 chance that the car is behind door number 3.

100 Doors! – Solution #2 to the Monty Hall Problem

Imagine that instead of 3 doors, there are 100. All of them have goats except one, which has the car. You choose a door, say, door number 23. At this point, Monty Hall opens all of the other doors except one and gives you the offer to switch to the other door. Would you switch? Now you may arrogantly think, “Well, maybe I actually picked the correct door on my first guess.” But what’s the probability that that happened? 1/100. There’s a 99% chance that the car isn’t behind the door that you picked. And if it’s not behind the door that you picked, it must be behind the last door that Monty left for you. In other words, Monty has helped you by leaving one door for you to switch to, that has a 99% chance of having the car behind it. So in this case, if you were to switch, you would have a 99% chance of winning the car.

Pick a Goat – Solution #3 to the Monty Hall Problem

To win using the stay strategy, you need to choose the car on your first pick because you’re planning to stay with your initial choice. The chance of picking the car on your first pick is clearly one out of three. But, in order to win using the switch strategy, you only need to pick a goat on your first pick because the host will reveal the other goat and you’ll end up switching to the car. So you want to use the strategy that lets you win if you choose a goat initially because you’re twice as likely to start by picking a goat.

Scenarios – Solution #4 to the Monty Hall Problem

To understand why it’s better to switch doors, let’s play out a few scenarios. Let’s see what will happen if you were to always stay with your original choice. We’ll play out three scenarios, one for each door that the car could be behind (door number 1, door number 2, or door number 3). And it doesn’t matter which door you start out with, so, to keep it simple, we’ll always start by choosing door number 1.

Stay strategy, scenario 1: the car is behind door number 1. You choose door number 1, then the host reveals a goat behind door number 2 and because you always stay, you stay with door number 1. You win the car! Stay strategy, scenario 2: the car is behind door number 2. You start by picking door number 1, the host reveals a goat behind door number 3, and you’re using the stay strategy so you stay with door number 1. You get a goat and don’t win the car. Stay strategy, scenario 3: the car is behind door number 3. You pick door number 1, the host opens door number 2 to reveal a goat, you stay with door number 1, and you get a goat. So, using the stay strategy, you won the car one out of three times. That means that in any one instance of playing the game, your chance of winning the car if you choose to stay is 1/3 or about 33%.

Now let’s try switching doors. Again, we’ll always start by picking door number 1. Switch strategy, scenario 1: the car is behind door number 1. You choose door number 1, the host opens door number 2 to reveal a goat, you are using the switch strategy so you switch to door number 3. You get a goat. Switch strategy, scenario 2: the car is behind door number 2. You start by picking door number 1, the host opens door number 3 to reveal a goat, you switch to door number 2 and win the car! Switch strategy, scenario 3: the car is behind door number 3. You pick door number 1, the host opens door number 2 to reveal a goat, you switch to door number 3 and win the car again! So, with the switch strategy you won the car 2 out of 3 times. That means, that in any one instance of the game, your chance of winning the car if you choose to switch doors is 2/3 or about 67%.

Therefore, if you play the game three times and stay, on average you’ll win the car once. But if you play the game three times and switch each time, on average you’ll win the car twice. That’s twice as many cars!

## Exponential growth

Big changes await us. An unrecognizable economy. The main lesson for me is that growth is not a “good quantum number,” as physicists will say: it’s not an invariant of our world. Cling to it at your own peril. Note: This conversation is my contribution to a series at www.growthbusters.org honoring the 40th anniversary of the Limits to Growth study. […]

Big changes await us. An unrecognizable economy. The main lesson for me is that growth is not a “good quantum number,” as physicists will say: it’s not an invariant of our world. Cling to it at your own peril.

*Note: This conversation is my contribution to a series at www.growthbusters.org honoring the 40th anniversary of the Limits to Growth study. You can explore the series here. Also see my previous reflection on the Limits to Growth work. You may also be interested in checking out and signing the Pledge to Think Small and consider organizing an Earth Day weekend house party screening of the GrowthBusters movie.*

Published on Sep 19, 2012

This video quickly covers the key points that you will find in the long version. Everyone needs to see the long version but many won’t because they don’t have the time. My hope is that people will watch this short version and then be motivated to watch the long version.

I came across “The Most Important Video You’ll Ever See” on YouTube and clicked on it. I didn’t realize that it was an eight part video that lasted over an hour but after finishing part one I had no choice but to watch the whole thing. It truly could be called the most important video you’ll ever see.

## Factorization diagrams

Reblogged from The Math Less Traveled: In an idle moment a while ago I wrote a program to generate "factorization diagrams". Here’s 700: It’s easy to see (I hope), just by looking at the arrangement of dots, that there are in total. Here’s how I did it. First, a few imports: a function to do […]

Reblogged from The Math Less Traveled:

In an idle moment a while ago I wrote a program to generate "factorization diagrams". Here’s 700:

It’s easy to see (I hope), just by looking at the arrangement of dots, that there are in total.

Here’s how I did it. First, a few imports: a function to do factorization of integers, and a library to draw pictures (yes, this is the library I wrote myself; I promise to write more about it soon!).

## systematically generate all permutations

There are many ways to systematically generate all permutations of a given sequence. One classical algorithm, which is both simple and flexible, is based on finding the next permutation in lexicographic ordering, if it exists. It can handle repeated values, for … Continue reading →

There are many ways to systematically generate all permutations of a given sequence. One classical algorithm, which is both simple and flexible, is based on finding the next permutation in lexicographic ordering, if it exists. It can handle repeated values, for which case it generates the distinct multiset permutations each once. Even for ordinary permutations it is significantly more efficient than generating values for the Lehmer code in lexicographic order (possibly using the factorial number system) and converting those to permutations. To use it, one starts by sorting the sequence in (weakly) increasing order (which gives its lexicographically minimal permutation), and then repeats advancing to the next permutation as long as one is found. The method goes back to Narayana Pandita in 14th century India, and has been frequently rediscovered ever since.^{[11]}

The following algorithm generates the next permutation lexicographically after a given permutation. It changes the given permutation in-place.

- Find the largest index
*k*such that*a*[*k*] <*a*[*k*+ 1]. If no such index exists, the permutation is the last permutation. - Find the largest index
*l*such that*a*[*k*] <*a*[*l*]. Since*k*+ 1 is such an index,*l*is well defined and satisfies*k*<*l*. - Swap
*a*[*k*] with*a*[*l*]. - Reverse the sequence from
*a*[*k*+ 1] up to and including the final element*a*[*n*].

After step 1, one knows that all of the elements strictly after position *k* form a weakly decreasing sequence, so no permutation of these elements will make it advance in lexicographic order; to advance one must increase *a*[*k*]. Step 2 finds the smallest value *a*[*l*] to replace *a*[*k*] by, and swapping them in step 3 leaves the sequence after position *k* in weakly decreasing order. Reversing this sequence in step 4 then produces its lexicographically minimal permutation, and the lexicographic successor of the initial state for the whole sequence.

An alternative to the above algorithm, the Steinhaus–Johnson–Trotter algorithm, generates an ordering on all the permutations of a given sequence with the property that any two consecutive permutations in its output differ by swapping two adjacent values. This ordering on the permutations was known to 17th-century English bell ringers, among whom it was known as “plain changes”. One advantage of this method is that the small amount of change from one permutation to the next allows the method to be implemented in constant time per permutation. The same can also easily generate the subset of even permutations, again in constant time per permutation, by skipping every other output permutation.^{[11]}

## N-Queens

N-Queens is an extension of the 8-Queens puzzle, both of which make use of trial-and-error methods and backtracking algorithms. Carl F. Gauss introduced the problem in 1850, but he was unable to completely solve it. The 8-Queens problem is stated … Continue reading →

N-Queens is an extension of the 8-Queens puzzle, both of which make use of trial-and-error methods and backtracking algorithms. Carl F. Gauss introduced the problem in 1850, but he was unable to completely solve it. The 8-Queens problem is stated as follows: Eight queens are to be placed on a chess board in such a way that no queen checks against any other queen. In other words, there can only be one queen per row, column, and diagonal.

### Niklaus Wirth’s algorithm

The data representation is as follows:

var x : |
array [1..n] of integer; |

a : |
array [1..n] of boolean; |

b : |
array [2..2n] of boolean; |

c : |
array [1-n..n-1] of boolean; |

where

*x*[i] denotes the position of the queen in the ith column;*a*[j] means no queen lies in the jth row;*b*[k] means no queen occupies the kth minor diagonal;*c*[k] means no queen occupies the kth major diagonal.

The following pseudocode explains how it works:

`function tryConfig(i: integer) {`

for j <- 1 to n do {

if safe then {

select jth candidate;

set queen;

if i < n then

tryConfig(i+1);

else

record solution;

remove queen;

}

}

}