You are at the grocery store buying a bag of oranges. The oranges are pre-bagged and all bags are sold at the same price.

All bags have the same number of oranges, but they do not weigh the same. You would not like to be cheated, or in other words, to not buy a bag below the median weight.

You begin by grabbing a bag with each hand to compare them. Once you decide on the heavier one you discard the one that feels lighter, keeping the one that feels heavier in your other hand, and pick up another bag with your free hand to make another comparison and continue the process.

Given that you are right about which bag is heavier 90% of the time (for simplicity assume your chances of misjudging the heavier of two bags are independent of their weight difference). How many bags will you have to pick up to be 85% certain that you are not being cheated?.

The number of bags to choose from is very large and there are no bags whose weight is equal to the median weight.

As you never pick up a bag again once you've put it down, the number of bags is one more than the number of times you compare weights. We'll also assume that the probability distribution of the weights is not skewed, so the probability a given bag is above (or below) average is 1/2.

If you weigh only two bags (one weighing), there is 1/4 probability that both are above the average.  There is also a 1/2 probability that one is above average and one below.  In the former case, you are certain to pick one that is above average; in the latter case, you have 9/10 probability of picking the one that's above average. So the overall probability of picking one that's above average, after one weighing is

p(1) = 1/4 + (1/2) * (9/10) = .7

In each subsequent weighing, the probibility, p(n), of choosing between two above-average bags is p(n-1) * (1/2). The probability of choosing between one below-average and one above-average is (1 - p(n-1)) * 1/2  +  p(n-1) * 1/2, which is just 1/2.  Thus the probability of holding an above-average bag after n weighings is

p(n-1)*(1/2) + (1/2)*(9/10)

so going from one weighing, to two weighings makes the probability

p(2) = .7*(1/2) + (1/2)*(9/10) = .8

We see each subsequent weighing averages the previous probability with .9, so for example p(3) = .85 and p(4) = .875, and the probabilities asymptotically approach .9.

So, after 3 weighings you will have an 85% chance of getting an above-average, rather than below-average, weighing bag.  This requires having picked up 4 bags.

Posted by Charlie on 2005-06-05 17:37:23