Hacker News Reader

Comment by yoz-y | Hacker News Reader

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.

View on HN

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.

Reply on news.ycombinator.com