5
$\begingroup$

I have a list and want to select a random item from the list.

An algorithm which is said to be random:

When you see the first item in the list, you set it as the selected item.

When you see the second item, you pick a random integer in the range [1,2]. If it's 1, then the new item becomes the selected item. Otherwise you skip that item.

For each item you see, you increase the count, and with probability 1/count, you select it. So at the 101st item, you pick a random integer in the range [1,101]. If it's 100, that item is the new selected node.

Is it really uniformly random?

My thoughts are:

As the number of nodes increases, the probability for them being selected decreases, so the best chance of selection is for items 1, 2, 3, ..., not for 20, 21, ..., 101.

Each node will not have equal probability of being selected.

Please clarify, as I have trouble understanding this.

$\endgroup$
5
  • $\begingroup$ minor terminology nitpick: an algorithm can be random without being uniformly random. I hope that it's implied whenever you say "random" you mean "uniformly random" $\endgroup$
    – Joe
    Mar 25, 2014 at 18:19
  • $\begingroup$ This is actually known as reservoir sampling. $\endgroup$
    – Juho
    Mar 25, 2014 at 18:32
  • $\begingroup$ "An algorithm which claims itself to be random" -- I seriously doubt it does. ;) (Lost in translation?) $\endgroup$
    – Raphael
    Mar 25, 2014 at 19:31
  • $\begingroup$ @Raphael: corrected :) $\endgroup$ Mar 25, 2014 at 19:39
  • 3
    $\begingroup$ Yuval has explained the maths behind why the algorithm works. The intuition is that, yes, the first few elements are much more likely to be selected when they're first seen but you need to remember that selection is only provisional. Sure, you choose the second item with probability $\tfrac12$ but, with probability $\tfrac13$, you immediately discard it and pick the third instead. So, early elements are very likely but it's also very likely that you'll later change your mind; later elements are unlikely to be chosen but that choice is more likely to be final. The result is uniform. $\endgroup$ Mar 25, 2014 at 20:06

1 Answer 1

11
$\begingroup$

The algorithm works, but to understand why, you need to know basic probability theory. The idea is to prove by induction that at step $t$, the currently selected algorithm is uniform among the first $t$ elements. This is clearly the case when $t=1$. Assume now the induction hypothesis for time $t$, and consider what happens at time $t+1$. With probability $1/(t+1)$, the element at position $t+1$ is selected. With probability $t/(t+1)$, the previously selected element is retained. By assumption, this is a uniformly random element among the first $t$ ones, and so the probability that any given element out of the first $t$ is selected is $t/(t+1) \cdot 1/t = 1/(t+1)$. In total, we see that each of the first $t+1$ elements is selected with the uniform probability $1/(t+1)$.

If you don't like induction, you can also do it all at once. For item $i$ to be selected as the output of the algorithm, it needs to have been selected at time $i$, and to not have been dropped at any further time. If there's a total of $n$ elements then this happens with probability $$ \frac{1}{i} \cdot \frac{i}{i+1} \cdot \frac{i+1}{i+2} \cdots \frac{n-2}{n-1} \cdot \frac{n-1}{n} = \frac{1}{n}. $$

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.