Hacker News Reader

Hacker News

Comment by dsego | Hacker News Reader

Full thread

dsego

Why doesn't it return on the first match?

View on HN

Because it would always return the first match in that case.

You still need to see all of the items once.

Imagine you have 2 items.

First one has 100% chance to be selected. So it does. Then the second has 50% chance to be selected. If it isn’t you effectively chosen the first one and have 50/50 chance to return either.

Now you add a third item. There is 50/50 chance of having either selected. And 1/3 chance of replacing the selection with the new one. Resulting in a 1/3 chance of selecting any of the three. (Because 1/2-1/6 = 1/3) 1/6 because there is 50% chance you will “steal” the selection.

Thank you for writing this out, I didn't quite get what was going on at first. But then, to formalize the recursion from your example: let's assume we're at item n in the iterator, and at that point we've selected a winner from the previous n-1 items with equal probability, i.e. each item had a 1/(n-1) chance of being selected. The probability that item n will override it is 1/n. The probability that the old winner will remain selected is thus (n-1)/n. That means that the old winner remains selected with probability 1/(n-1) * (n-1)/n, which cancels out to 1/n, so each item is indeed selected with equal probability in the end.

An alternative wording for the same idea:

If you are at picture 1, you have 100% chance of selecting it as the current winner.

If you are at picture 2, you have 1/2 chance of selecting it as the current winner, or 1/2 chance of keeping the previous fairly selected winner.

At picture 3, 1/3 chance of picking it, or 2/3 chance of retaining the previous fairly-selected winner. There are two of them, so 1/3 chance of each.

At picture n, you have a 1/n chance of picking it, or an (n-1)/n chance of retaining the previous fairly-selected winner. There are n-1 previous pictures, so all of them have had 1/n chance of being picked.

At every single step, there is the invariant of all pictures being considered that far having had an equal chance of being selected, and the next step always retains the invariant.

This feels very analogous to the three doors puzzle.

Oh, I understand, should've examined more carefully, the count starts at 0 and increments, so random is not from the total but from the elements counted so far.

exactly. There is something wrong with the code snippet.

No there is not. First element is defacto winner, but you still have to loop through the rest with 1/n chance of being selected to fully give each element a chance of winner selection

Yeah I think the "wrong feeling" is just that this could, in theory, be O(1) with something like:

  pics[Math.random() * len(pics)]

... assuming that random() gives you a number from 0..1 - but that's why it feels "wrong".

len(pics) either already knows about the length or it needs to count so it’s O(n)

The len(pics) can be O(n), especially if iterators are used like here. Also, an O(1) lookup would require a previous O(n) pass over the data anyway.

The picture selection algorithm's kind of single-pass iterator usage might have been more performant back in the XP days, as it avoids possibly expensive operations.

Modern CPU/other optimizations might make a multi-pass approach more performant due to better memory locality or other factors.

On count == 1, the winner gets set to the first element, true. But the function does not return yet! So the value might get overwritten during the remainder of the for-loop.

I re-examined it, the count changes, that's why it works. The random is not between 1 and total, it's between 1 and current count.

Reply on news.ycombinator.com