Hacker News Reader

Comment by tgb | Hacker News Reader

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://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.

View on HN

> 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.

Big game or fowl play?

Ruffled feathers

I bet they were just too chicken to publish it.

I really gobble up this kind of word play.

You're such a turkey

We used to joke in grad school that PNAS stands for Paper Not Accepted in Science.

Yeah they're a real P-NAS.

We used to joke it was Probably Not Actual Science

when you get to pick your own reviewers like they academy members do it might as well just be an opinion column. lol.

This 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/UtCZL5A

I appreciate the footnote that basically says "Whoa, this is more practically useful than we realized!"

Nice. 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?

Yeah, 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.

Is 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)

agreed, I thought of the same issue. Seems like there has to be some assumption about even difficulty of finding bugs / catching species of birds

I 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.

I 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.

Does 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).

Is it similar to the german tank problem?

https://www.eadan.net/blog/german-tank-problem/

With python code.

The German tank problem is easier because it assumes the tanks have sequential serial numbers.

Reply on news.ycombinator.com