7 ms·
Here's a wonderful one I read a little over a year ago: "Estimating the number of unseen species: A bird in the hand is worth log(n) in the bush" https://arxiv
by tgb 6y ago
Here's a wonderful one I read a little over a year ago:
"Estimating the number of unseen species: A bird in the hand is worth log(n) in the bush"
https://arxiv.org/abs/1511.07428 https://arxiv.org/abs/1511.07428
https://www.pnas.org/content/113/47/13283 https://www.pnas.org/content/113/47/13283
It deals with the classic, and wonderful, question of "If I go and catch 100 birds, and they're from 20 different species, how many species are left uncaught?" There's more one can say about that than it might first appear and it has plenty of applications. But mostly I just love the name. Apparently PNAS had them change it for the final publication, sadly.
- specialist 6y agoNice. My math-fu is very weak. I dimly recall a notion for estimating the number of unfound bugs for a code base. Is this similar?
- tgb 6y agoYeah, exactly. If you wanted to know that your code was bug free, how could you do it? Set a team of experts to each independently scour for bugs. But when do you stop? The quick answer is that you should keep going until every bug you've found, has been found at least twice. I think of this as being that you "just barely" found a bug if only one person identified it, so there are probably still bugs you have "just barely" not found remaining.
- uyt 6y agoIs that a direct application of the paper or something else? (sorry I didn't read it) Just wondering because this rule of thumb sounds intuitively wrong to me. Depending on the difficulty of the bugs and the skill levels of the experts, it seems possible for them to find every "easy" bug at least twice while having none of them finding the hardest bug even once. (real world example would be some obscure zero-day security bug)
- bugzz 6y agoagreed, I thought of the same issue. Seems like there has to be some assumption about even difficulty of finding bugs / catching species of birds
- tgb 6y agoI should have said "at least until" rather than "until", sorry. It's from a result that predates the paper, due to Fisher (using butterflies, not code bugs). The actual guarantee from the result is not that the number of unobserved "species" is small, but that the total population of all unobserved species is small. If you go back to the birds example, then you could say something like "at most 0.1% of all birds are from species that we haven't identified" but maybe those 0.1% of birds are from a million different species each with incredibly tiny populations. In the code bug example, the very rare species would be the bugs that are very unlikely to be found, i.e. it's more about estimating how many more bugs you will find if you continue to analyze it than how many are really there.
- grahamburger 6y agoI thought it was more like: Set a team of experts to find bugs independently for some specified amount of time. Then look at how many of the same bugs were found by multiple experts. If most of the bugs were found by multiple experts, then there are probably not that many more bugs than the total number that they found. If most of the bugs were found by only one expert, then there are probably a lot more than the total that they found. With some math you can pin down the 'probablies' to numeric ranges.
- janekm 6y agoDoes that not assume equal probability of finding bugs? Seems to me that both teams would find the same easily identified bugs (say '=' instead of '==' or revealed by compiler warnings).
- eeZah7Ux 6y agoIs it similar to the german tank problem?
- lowdose 6y agohttps://www.eadan.net/blog/german-tank-problem/ https://www.eadan.net/blog/german-tank-problem/ With python code.
- nerfhammer 6y agoThe German tank problem is easier because it assumes the tanks have sequential serial numbers.
- bordercases 6y ago> But mostly I just love the name. Apparently PNAS had them change it for the final publication, sadly. Big game from an organization with that acronym.
- faitswulff 6y agoBig game or fowl play?
- benrapscallion 6y agoWe used to joke in grad school that PNAS stands for Paper Not Accepted in Science.
- eigenvalue 6y agoThis sounds like a similar problem to an exercise in the famous probability textbook by William Feller about estimating the total number of fish in a lake by catching N of them and tagging them, and then throwing them back in the lake and coming back later to catch another N fish. You check how many of those fish are tagged and derive your estimate from that using the hypergeometric distribution. See the pages here: https://imgur.com/oRF0OD3 https://imgur.com/oRF0OD3 https://imgur.com/UtCZL5A https://imgur.com/UtCZL5A
- Breza 6y agoI appreciate the footnote that basically says "Whoa, this is more practically useful than we realized!"