In the Masters Golf Tournament held last weekend there were 55 players who had a final score between 10 under par and 9 above. By the pigeonhole principle one would expect many players to have the same score and in particular multiple players to have the best score. There was a tie for first that required a playoff.
But this is the exception, there were only four playoffs in the last twenty years of the Masters. In most years the Masters tournament has a unique player with the lowest score. Why?
I used Golf Tournaments to motivate the Mulmuley-Vazirani-Vazirani isolation lemma. If you have a collection of sets over {1,...,n} and choose random weights w1,...,wn from {1,...,r} let the weight of a set be the sum of the weights of its elements. The MVV lemma states there will be a unique maximum weighted set with probability at least 1-n/r.
It's a cool lemma with a short proof: you argue that with high probability each element i is either in all or none of the max weighted sets.
So how do I tie the lemma to golf tournaments? Actually I don't see a direct connection. But the spirit is the same.
Repeat 50 times the experiment of flipping 50 coins and counting how many of them are heads. How likely is it that a unique one of your experiments has the most heads?
ReplyDeleteI just simulated it and came up with 73% probability that there is a unique maximum in 50 experiments. Very interesting, it's much higher than I thought it would be!
DeleteGolfers scores on holes are not independent of each other. In addition to skill and fundamental human limits, there is the fact that individual golfers know each others' partial scores as they are playing.
ReplyDeleteBasketball is another example of a sport in which the overall score is the sum of a large number of individual scoring steps. Scores almost always are between roughly 75 and 100 points yet the number of games that are tied at the end of regulation is much smaller than 1 in 50.
There even exists a kind of isolation lemma for binomial distributions (see Chapter 5). Basically, the number of binomial variables that attain the minimum is 1+o(1) if there are not too many of them. (If the random variables are Binom(n,p) for constant p, then poly(n) random variables are fine.)
ReplyDelete"By the pigeonhole principle one would expect many players to have the same score and in particular multiple players to have the best score."
ReplyDeleteYou don't teach the pigeonhole principle to student do you? I hope not. The pigeonhole principle does not say anything about spread.
Out of curiosity, when you give a hard exam, how often is there a tie for the top score? I might have a bunch of 88 scores or 92 scores but only a single 97.
This comment has been removed by a blog administrator.
ReplyDelete