Why doesn't it return on the first match?

yoz-y 40 minutes ago | parent | next [-]

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.

	▲	Elte 6 minutes ago \| parent [-]
		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.

▲

quentinkent1 42 minutes ago | parent | prev [-]

exactly. There is something wrong with the code snippet.

	▲	arpadav 20 minutes ago \| parent \| next [-]
		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
	▲	kleiba2 19 minutes ago \| parent \| prev [-]
		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.