General Monty Hall Problem and Information Theory

Problem: There are three doors and only there is one door behind which there is a prize.You first select a door, then the host of the game will open one door behind which there is no prize (he can't open the door you had selected). Then you are given the choice to switch the door or not. This is the typical Monty Hall problem people talk about. The general form is that n doors with only one door behind which there is a prize. The host of the game will open m doors (m<n-1) behind which there are no prize. Then you are given the choice to switch to another door.

Solution: The most most important observation about this problem is that "probability" is actually not about "randomness", but about information. How much information we have will influence the probability".  Now let's first look at the basic form of the Monty Hall problem.

• assume you chose door A, the probability that you had made the correct choice, P(A),  is 1/3. Assume the host opened the door C (the case for door B is the same), let us denote this action as O. The probability, P(A|O), which means the probability that you had made the correct choice given the host opened the door C, is what we are interested in. Actually P(A|O) = P(A) = 1/3, since unless you move the prize, there is no way you can change the odds of your original choice.
• Besides, we can systematically calculate P(A|O). According to Bayes's theorem, P(A|O) = P(O|A)*P(A)/P(O). We know P(A) = 1/3. P(O|A) should equal 1/2, since if A is the right answer, B and C are both empty doors. The the probability for the host to open door C is simply 1/2. Then we need to calculate P(O). 
• P(O) = P(O|A)*P(A) + P(O|B)*P(B) + P(O|C)*P(C). It is easy to know, P(O|C) = 0, also  P(O|A)*P(A) =1/6. We have P(O|B) = 1. The reason is that we had already chosen A, but B is the right answer, so the only choice for the host is C. Therefore, P(O) = 1/6+1*1/3 = 1/2. Then we have P(A|O) = 1/3.
• Then the probability to win if we switch is P(B|O) = P(O|B)*P(B)/P(O) = 1*1/3 / (1/2) =2/3, so we need to switch!

Now let's try to tackle the general problem.

• The probability to win if we stick to the original choice (assume it is A again), P(A) = 1/n, also we have P(A|O) = 1/n.
•  The probability to win if we switch, P(S|O) = P(We switch to the correct door | Our original choice is wrong) = (1/(n-m-1))*(1-1/n) = ((n-1) / (n-m-1))*1/n). It is easy to know P(S|O)  > P(A|O), so we still need to switch.
• Thinking in the way of information theory, after host reveal some empty doors, we are given more information. These information will change the probability distribution!

See Also: Monty hall and Bayesian probability theory,  The Monty Hall problem -- over easy

Paint a Cube with Three Colors

Problem: Given a cube, each face can be painted with one of the three colors. Calculate the ways the cube can be colored.

Solution: The problem can be solved by enumeration. While a more formal way is to use Burside's Lemma. Generally we need to understand the symmetry of the permutation on cubes. The main ideas of this method are listed as follows:

1. find the permutation groups of a cube, the easiest one is the identity permutation (just don't change). Then for the six faces, we have 1->1, 2->2 ... and 6->6. So for this permutation, there are 6 circles and the length of each circle is 1. Therefore we have a1^6, where a1 means the sub group that with circle length 1. "6" means there are 6 such circles.
2. then we can rotate along the axis that penetrates the centers of two opposite faces for 90 degree. If we do this, we have a1^2*a4, since two face unchanged, and the rest 4 form a circle. We have 6 such rotations. Therefore at the end we have 6*a1^2*a4.
3. then we can rotate along the axis that penetrates the centers of two opposite faces for 180 degree. If we do this, we have a1^2*a2^2.We have 3 such rotations. Therefore at the end we have 3*a1^2*a2^2.
4. then we can rotate the two opposite vertices (diagonal). We will have a3^2, since three faces that share one vertex are in one circle. We have 8 such rotations. Therefore at the end we have 8*a3^2.
5. then we can rotate along the axis that penetrates the middle points of two parallel edges that are not in the same face for 180 degree. We will have 6*a2^3 at the end.
6. so totally we have 1+6+3+8+6 = 24ways of permutations. So the cycle index (the ways to paint the cube) = 1/24*(a1^6+6*a1^2*a4+3*a1^2*a2^2+8*a3^2+6*a2^3). Since a1=a2=...=a6, we have cycle index =  1/24*(a^6+3*a^4+12*a^3+8*a^2). 
7. when a = 3, we have cycle index = 57.

A Coin, First Throw Get Head, Bet the Second Thow

Problem: A coin (you don't know it is a fair one or biased one), in the first throw, you got a "head". What will you bet for the second throw and what is the probability to win?

Solution: This is a conditional probability problem. Assume the probability to get head is p. f(p) is a uniform distribution. P(H2/H1) = P(H2H1)/P(H1) = int_{p^2*f(p)*dp} / int_{p*f(p)*dp} = (1/3) / (1/2) = 2/3.

M balls and N boxes

Problem: There are M balls and N boxes. Each ball is randomly placed into a box. What is the expected number of boxes that have at least one ball inside?

Solution: We can create a series of identification variables, Ii, which denotes for the i th box, if there is at least one ball inside. If yes, Ii = 1, otherwise Ii = 0. Then our problem is to calculate the expected value to I, where I = I1 + I2 + ... + IN. There is symmetric here, so E(I) = N*E(Ii) = N*(1-(N-1/N)^M)

Related: How many boxes you need to have in order to collect all the toys?

How many boxes you need to have in order to collect all the toys?

Problem: Mike likes potato chips and also like the free toys piggybacked with the chips. There are N different toys in total. In each box of potato chips, there will only be one toy and the type of the toy is randomly decided. If Mile wants to collect all the N different toys, how many boxes of chips he needs to buy (on average)?


Solution: We can solve the problem by using Geometric Distribution. After we had collected i-1 toys ( i <=N), the number of  boxes we should get in order to get the i th toy conforms to a geometric distribution. The probability for the geometric distribution is (N-i+1)/N, thus the expected number of boxes to get the i th toy is N/(N-i+1). Then we can construct a random variable X and X = X1 + X2 + ... + XN, where Xi means the number of  boxes we should get in order to get the i th toy when we already have i-1 different toys. So E(X) = E(X1) + E(X2) + ... + E(XN) = N/N + N/N-1 + ...... + N/1 = N*(1/N + 1/(N-1) + ... + 1)

Related: Coupon collector's problem, M balls and N boxes