The Best Horse
Problem: You are the chief guest at an auction, where some number of horses will be auctioned, one after the other, randomly permuted. You are a connoisseur of horses, and can judge whether one horse is ‘better’ than another. Being the chief guest, you have a one-time privilege of selecting a horse, after it is revealed, but before it gets auctioned off. You get to keep this horse for yourself. Your objective is to maximize the probability of selecting the best horse. One strategy is to pick the first horse. Can you do any better?
Source: Fifty Challenging Problems in Probability with Solutions by F Mosteller
Disclaimer/Hint: If you are even half like me, you would love attempting this puzzle. Just do it using basic math and you will hit it right. The solution would even imply "Birthday Paradox" beautifully. :)
Update: (22/12/09) Solution posted by Giridhar in comments.
Source: Fifty Challenging Problems in Probability with Solutions by F Mosteller
Disclaimer/Hint: If you are even half like me, you would love attempting this puzzle. Just do it using basic math and you will hit it right. The solution would even imply "Birthday Paradox" beautifully. :)
Update: (22/12/09) Solution posted by Giridhar in comments.
Horses are rated 1, 2, 3, 4, 5; with horse rated 5 being the best.
ReplyDeleteThese arrive in random order.
Strategy :
Guest ignores first two horses,say A & B, in the random order and from then on picks the first one which is better than A & B.
with this strategy, guest is gauranteed to pick the best horse if second best horse appear in the first two positions and the best horse is somewhere in the last 3 positions in the random order.
ex: if 4 1 3 5 2 is the random permutation, with this strategy he picks the best horse.
Hence the probability of choosing best horse is > (2/5) * (3/4) = 0.3
Hence, better than the strategy mentioned in the question.
Thus since randomness is decieving us ( as in picking the first one in the order case ), we also attack it using randomness in our strategy.
The probability of choosing the best horse using the mentioned strategy is exactly equal to 1/5 + (1/5 * 3/4) + (1/5 * 2/4 ) = 9/20 =0.45
I am not sure if this is the best we can do.
Small Correction in the calculation of exact probability ::
ReplyDelete1/5 + (1/5 * 2/3) + (1/5 * 2/4 )
Approximately 0.43
I wonder why did you bring in the number 5 here.. There are n horses and you have to find the best one..
ReplyDeleteThe algorithm suggested is good and applies for general n..
Lets say we will just observe the first h horses and then take the first horse better than all the h horses.
The probability we will chose the best horse can be derived as follows.
One strategy is to skip the first horse, then pick the first subsequent horse which is superior to the first horse. The probability that the first horse is the k-th best horse is 1/n. From among the remaining k-1 horses that are superior to this horse, the probability that the best comes before all others is 1/(k-1). So the overall probability is 1/n times 0 + 1 + 1/2 + 1/3 + 1/4 + .. + 1/(n-1), which is H(n-1)/n which is approx ln(n)/n.
It is easy to show that if we follow the strategy of skipping the first h horses and then pick the first subsequent horse that is superior to all horses so far, the probability is .....
to be continued..
:) Happy Jappy!! :)
Sorry for wrongly assuming that the number of horses is five. ( I was solving at that time another puzzle by Gurmeet which involved number 5).
ReplyDeleteStrategy remains same, except for introduction of variables :
We ignore first x horses, and from then on choose the first horse in the order which is better than x horses that we ignored.
Let us denote by BH( n, x) the probability of choosing the best horse using the above strategy.
for 1 <= x <= n-1,
BH ( n , x ) = 1/n [ Sum ( x/(j-1)) x < j <= n ]
where [x/(j-1)] is the probability that better horse among [1,j-1] horses is among first x ignored horses; only then Best of all horses will be selected using the strategy , given that Best one occupied jth position in the random order.
BH ( n , x ) ~ (x/n)[ ln(n) - ln(x) ]
Differentiating above w.r.t x and equating result to zero , gives that BH (n, x) is maximized at x= n/e.
Thus by ignoring first (n/e) horses in the random order, with probability of (1/e) guest will pick best horse;
That is the best we can do with this strategy.
But some other clever strategy might yield higher probability.
awaiting Pratik to answer,
Giridhar.
Awesome solution.. thanx a lot..
ReplyDelete