Assume I have a bag with several distinct objects. Particularly, I do not tell you how many objects I have. At each step, I take out one item and give it to you. I may do this in any order, with any probability distribution or even adversarially. You can only hold one item in your hand at a time. So, at each step, you get to choose whether to retain the object already in hand or replace it with the new one. When I run out of objects (or I am simply tired and quit), I stop.
Your goal is adopt a strategy so that the object in your hand at the end is uniformly at random among all items. In other words, irrespective of how many objects I give you or however I choose them, this item in your hand should be equally probable to any other item.
Go figure!
(courtsey Nenad)
Wednesday, March 28, 2007
Saturday, March 24, 2007
Worshipping False Gods
Yet again, the Indian cricket team failed. Being hyped by the media as
the team with the best batting line-up, this is no the first time the
batting order has seen a complete collapse and I fear this would not
be the list time either. Indian cricketers enjoy a god-like (not
God-like, yet) status back home. The facilities, the perks, the
attention and the support they get from the fans, officials and media
is phenomenal and unparalleled. So it sounds right when the fans treat
them harshly after poor defeats. Sometimes their show of
disappointment gets a bit overboard which is definitely not desired.
But again, when the worship the cricketers, nobody complains either!
the team with the best batting line-up, this is no the first time the
batting order has seen a complete collapse and I fear this would not
be the list time either. Indian cricketers enjoy a god-like (not
God-like, yet) status back home. The facilities, the perks, the
attention and the support they get from the fans, officials and media
is phenomenal and unparalleled. So it sounds right when the fans treat
them harshly after poor defeats. Sometimes their show of
disappointment gets a bit overboard which is definitely not desired.
But again, when the worship the cricketers, nobody complains either!
I don't know about the other subcontinent teams but the gods in the
team are definitely past their days of glory. They are only fit for
consultations now; they should be retired and fresh blood should be
brought into the team. It has happened time and again. It took the
board 2 full years to sack and drop Sourav Ganguly. He returned in the
team after regaining his batting form. Look ma! Sourav is now scoring
runs. When and if he loses his rhythm again, he should be dropped.
Same for Sachin, Sehwag and other non-performers.
I feel the cricketers should also be restricted from doing too much
non-cricket stuff. They spend time after endorsements, other business
(whats this recent craze about opening restaurants ?) and doing public
speeches for political parties. Appearing in one or two advertisements
for public service is good, since quite a few of the cricketers are
seen as role models by the youngsters but not as brand ambassadors.
Similarly, being citizen of India they are entitled to the freedom of
voicing their opinion but not with any regularity.
BCCI should cap non-cricket involvement, spend more resource and
effort after domestic cricket and make the seniors also play domestic
cricket. That keeps them in practice and on the other hand provides
the young guns with better exposure. I personally don't think a
foreign coach is necessarily a bad or a good thing. Give the job to
the best person. The richest cricket board can afford to pick the
best.
In other news, Sachin is only one duck away from equalling Srinath's
Indian record of most (19) ODI ducks.
Saturday, March 3, 2007
Debugging Probablity: Car, Goats and Monty Hall
The Monty Hall puzzle is a famous probabity puzzle. In one of its various forms, there is a room with 3 closets. One of them has a car behind it, the other two has a goat each. When you enter the room, the doors were closed so you do not know which closet has what. The challenger asks you to guess which closet contains the car. If you guess correctly, you get the car. If incorrect bad things will happen, no guarantees here. So you think a lot, probably make phone calls to friends and make a guess, say X. Then you proceed to open the door to see what is in your fate. But the challenger stops you and opens one of the other closets Y that has a goat. Then he even gives you a chance to make a new guess Z. You have two options, stick with previous guess (X=Z), switch to the other unopened closet (X!=Z). What to do ?
The correct behaviour (by probability) is to change the guess to the closet that is still unopened, X!=Z. That will double your chance of winning. There are several ways to reason about this. But I am more interested in debugging other claims, mostly faulty. So, lets look at the different explanations.
We can make one assumption. To stop the challenger from getting the better of you, you should choose X uniformly at random from all three closets. So, P[X=car]=1/3 and P[X=goat]=2/3.
1. Repeat the experiment a million times. You would get the the car only one third of the time by sticking to your first door. People who always switch would therefore win the other two thirds. Therefore you should switch.
The only cases when you win by switching is when X=goat. So, P[winning | switching]=2/3 (probability taken over X).
2. Consider all possible cases:
Actually, the complete table says that, if you randomly decide to switch or not switch, then you have a 50-50 chance of winning. Further, it even says that P[win | switch]=P[win | Z!=X]=2/3.
3. One argument is that revealing Y does not matter. The probability of finding the car in the remaining two doors was equal in the beginning, and they are still equal now. The fact that you put your hand on one of them cannot increase or decrease its probability of having the car under it.
The explanation is a bit ambigous. Lets look at various cases and explanations. These are all different experiments.
[C1] At the beginning itself, the challenger opens one of the goat containing closets. P[car in one of the other two]=1/2 in this case.
[C2] The challenger opens a goat closet. The he randomly reshuffles the contents of the other two closets. Here,
P[X=car]=1/3
P[X=car | switch]=P[X=car | not switch]=1/2
[C3] The challenger opens one door while your eyes are closed, showing a goat to the audience.
P[X=car] = 1/3
P[X=car | revealing] = 1/3
this is the same experiment. Just because he opened a door does not change your sample space.
[C4] The challenger reveals a goat closet to you.
P[X=car]=1/3
But, P[X=car | revealing] != 1/2 because the challenger did not reshuffle the contents. In fact, knowing a closet contains a goat makes the probability of winning by switching 2/3. This is different from C1. The challenger has been forced to reveal some information not known before. If X=goat, Monty had to open the non-car closet. If X=car, he will not reveal any information. 2/3 of the cases X=goat, in which case he would leave the car closet closed. 1/3 of the cases X=car and he could choose any goat-door without saying anything. So, if you switch, you have a winning chance of 2/3. Note that, the analysis depends on your initial uniformity of choosing a closet but independent of challengers choice of Y.
4. The analysis sounds easier if you consider a related problem. Say there are 1000 closets, one car and 999 goats. Do the same experiment but here the challenger reveals 98 of the goat closets.
Initially P[X=car]=1/1000. When the challenger opens all but 2 doors, P[X=car] cannot possibly remain the same. In fact, by the argument in C4 above, 999/1000 times X=goat, so the challenger would be forced to leave the car closet open. Then, P[win | switch]=999/1000.
5. Another way of looking at it is, P[X=car]=1/3 which means that if you consider all possible items in the closet, in 1/3 of the cases it would be a car i.e. P[one of the other two has car]=2/3 Revealing a goat does not change this probability (it does change some conditional probabilities). So, even after revealing, P[one of the other two has car]=2/3. But now you know that one of the other two definitely has a goat. So, P[one of the other two that is unopened has a car]=2/3.
6. Consider a slight variant of the puzzle. There are 4 doors with 1 car and 3 goats. After you choose X, the challenger opens one door with goat. Now, with probability 3/4, you chose a goat closet. In which case, the challenger leaves a car closet and a goat closet open. Let us say you always switch to any of the them with probability 1/2. Then your probability of winning in this case is 3/8. With probability 1/4, you choose a car, in which case you always loose when you switch. So, switching gives you 3/8 probability of winning. On the other hand, if you do not switch, then you only win when you chose the car closet, which happens with probability 1/4=2/8. So, switching is better, but not by that much.
The correct behaviour (by probability) is to change the guess to the closet that is still unopened, X!=Z. That will double your chance of winning. There are several ways to reason about this. But I am more interested in debugging other claims, mostly faulty. So, lets look at the different explanations.
We can make one assumption. To stop the challenger from getting the better of you, you should choose X uniformly at random from all three closets. So, P[X=car]=1/3 and P[X=goat]=2/3.
1. Repeat the experiment a million times. You would get the the car only one third of the time by sticking to your first door. People who always switch would therefore win the other two thirds. Therefore you should switch.
The only cases when you win by switching is when X=goat. So, P[winning | switching]=2/3 (probability taken over X).
2. Consider all possible cases:
- X=goat1, Z=X (loose)
- X=goat1, Z!=X (win)
- X=goat2, Z=X (loose)
- X=goat2, Z!=X (win)
- X=car, Z=X (win)
- X=car, Z!=X (loose)
Actually, the complete table says that, if you randomly decide to switch or not switch, then you have a 50-50 chance of winning. Further, it even says that P[win | switch]=P[win | Z!=X]=2/3.
3. One argument is that revealing Y does not matter. The probability of finding the car in the remaining two doors was equal in the beginning, and they are still equal now. The fact that you put your hand on one of them cannot increase or decrease its probability of having the car under it.
The explanation is a bit ambigous. Lets look at various cases and explanations. These are all different experiments.
[C1] At the beginning itself, the challenger opens one of the goat containing closets. P[car in one of the other two]=1/2 in this case.
[C2] The challenger opens a goat closet. The he randomly reshuffles the contents of the other two closets. Here,
P[X=car]=1/3
P[X=car | switch]=P[X=car | not switch]=1/2
[C3] The challenger opens one door while your eyes are closed, showing a goat to the audience.
P[X=car] = 1/3
P[X=car | revealing] = 1/3
this is the same experiment. Just because he opened a door does not change your sample space.
[C4] The challenger reveals a goat closet to you.
P[X=car]=1/3
But, P[X=car | revealing] != 1/2 because the challenger did not reshuffle the contents. In fact, knowing a closet contains a goat makes the probability of winning by switching 2/3. This is different from C1. The challenger has been forced to reveal some information not known before. If X=goat, Monty had to open the non-car closet. If X=car, he will not reveal any information. 2/3 of the cases X=goat, in which case he would leave the car closet closed. 1/3 of the cases X=car and he could choose any goat-door without saying anything. So, if you switch, you have a winning chance of 2/3. Note that, the analysis depends on your initial uniformity of choosing a closet but independent of challengers choice of Y.
4. The analysis sounds easier if you consider a related problem. Say there are 1000 closets, one car and 999 goats. Do the same experiment but here the challenger reveals 98 of the goat closets.
Initially P[X=car]=1/1000. When the challenger opens all but 2 doors, P[X=car] cannot possibly remain the same. In fact, by the argument in C4 above, 999/1000 times X=goat, so the challenger would be forced to leave the car closet open. Then, P[win | switch]=999/1000.
5. Another way of looking at it is, P[X=car]=1/3 which means that if you consider all possible items in the closet, in 1/3 of the cases it would be a car i.e. P[one of the other two has car]=2/3 Revealing a goat does not change this probability (it does change some conditional probabilities). So, even after revealing, P[one of the other two has car]=2/3. But now you know that one of the other two definitely has a goat. So, P[one of the other two that is unopened has a car]=2/3.
6. Consider a slight variant of the puzzle. There are 4 doors with 1 car and 3 goats. After you choose X, the challenger opens one door with goat. Now, with probability 3/4, you chose a goat closet. In which case, the challenger leaves a car closet and a goat closet open. Let us say you always switch to any of the them with probability 1/2. Then your probability of winning in this case is 3/8. With probability 1/4, you choose a car, in which case you always loose when you switch. So, switching gives you 3/8 probability of winning. On the other hand, if you do not switch, then you only win when you chose the car closet, which happens with probability 1/4=2/8. So, switching is better, but not by that much.
