7 ms·
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 ite
by Elte 8d ago
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.
- Anon_troll 8d agoAn 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.
- matsemann 8d agoThis feels very analogous to the three doors puzzle.