tag:blogger.com,1999:blog-3722233.post4139833063115474364..comments2021-12-06T01:56:06.040-06:00Comments on Computational Complexity: Unique Golf WinnersLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-3722233.post-83670327303181549972012-04-14T12:42:08.725-05:002012-04-14T12:42:08.725-05:00This comment has been removed by a blog administrator.Anonymoushttps://www.blogger.com/profile/09364120444779754928noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-23028111001291101172012-04-13T17:44:51.981-05:002012-04-13T17:44:51.981-05:00"By the pigeonhole principle one would expect..."By the pigeonhole principle one would expect many players to have the same score and in particular multiple players to have the best score."<br /><br />You don't teach the pigeonhole principle to student do you? I hope not. The pigeonhole principle does not say anything about spread.<br /><br />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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-78610355297268747692012-04-13T02:42:46.437-05:002012-04-13T02:42:46.437-05:00There even exists a kind of isolation lemma for bi...There even exists a kind of <a href="http://dx.doi.org/10.1016/j.dam.2011.03.004" rel="nofollow">isolation lemma for binomial distributions (see Chapter 5)</a>. 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.)Bodo Mantheyhttp://www.math.utwente.nl/~mantheyb/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-89663565929069155232012-04-12T14:36:42.919-05:002012-04-12T14:36:42.919-05:00I just simulated it and came up with 73% probabili...I 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!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-87433693638384762492012-04-12T12:07:29.431-05:002012-04-12T12:07:29.431-05:00Golfers scores on holes are not independent of eac...Golfers 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. <br /><br />Basketball 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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-72400343636243960302012-04-12T11:04:52.372-05:002012-04-12T11:04:52.372-05:00Repeat 50 times the experiment of flipping 50 coin...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?D. Eppsteinhttp://11011110.livejournal.com/noreply@blogger.com