2
$\begingroup$

Imagine you've got entries coming in, without knowing when they end (how many will follow from now on). You're supposed to pick random one and be fair. You can't save the entries that passed but you can remember how many passed.

At this point, if you imagine it, it seems impossible. At the point of choosing, you don't know what should be item's chance to be chosen.

But maybe there is some trick. And if not we'll have to prove that it's impossible - which I expect to be part of negative answer.

$\endgroup$
  • $\begingroup$ What do you mean by "fair"? If there is a countable infinite of entries, there's no way for every entry to have the same probability of being chosen unless that probability is $0$ (in which case you don't choose anything). $\endgroup$ – Robert Israel Dec 9 '14 at 1:49
  • 2
    $\begingroup$ Or is the number of entries finite (in which case you really didn't mean "endlessly")? $\endgroup$ – Robert Israel Dec 9 '14 at 1:51
  • $\begingroup$ @RobertIsrael It's finite. I'l try to rephrase the question. $\endgroup$ – Tomáš Zato Dec 9 '14 at 2:18
4
$\begingroup$

There is a standard algorithm for this:

  1. Let $S$ (the selected entry) be the first entry.
  2. If there is a second entry, generate a random number $x$ between 0 and 1. If $x\lt \frac12 $ discard the previous selection and let $S$ be the second entry instead.
  3. If there is a third entry, generate a random number $x$ between 0 and 1. If $x\lt \frac13$ discard the previous selection and let $S$ be the third entry instead.

(Repeat similarly until the final entry is reached; the $i$th entry should be selected with probability $\frac1i$, replacing whatever was previously selected, and should otherwise be discarded. )

The selected entry is whatever remains in $S$ after this procedure completes.

Pseudocode:

i := 0
while (another entry remains) do:
  E := (read next entry)
  i := i + 1
  x := random (0,1)
  if x < 1/i do:
    S := E
  end;
end;
(the selected entry is now in S)

A simple induction proof establishes that if there are $n$ entries then each is selected with probability exactly $\frac1n $. For if that is true of the first $n-1$ entries, then they are each selected with probability $\frac1 {n-1}$ before the final step. Then the final entry is selected with probability $\frac1n $; if the final entry is not selected then the earlier entry already in $S$ has been selected with total probability $\frac1 {n-1}\frac {n-1}n$.

This is a well-known algorithm among computer programmers; a web search for "select random line without counting lines" will find many discussions of the problem and its solution. )

$\endgroup$
  • 1
    $\begingroup$ If I recall correctly this is called "reservoir sampling", also worth googling. $\endgroup$ – Michael Lugo Dec 9 '14 at 2:48
  • $\begingroup$ I feel really dumb for not figuring this out (I thought about the problem quite some while before I decided to put all the values in array before picking random one...). $\endgroup$ – Tomáš Zato Dec 9 '14 at 2:50
  • $\begingroup$ Yes, thanks, although that usually refers to the case where we are selecting $k$ items. Here $k=1$, which somewhat simplifies the algorithm. $\endgroup$ – MJD Dec 9 '14 at 2:52
  • $\begingroup$ Tomáš: you shouldn't feel dumb; most people do not consider this method obvious. $\endgroup$ – MJD Dec 9 '14 at 2:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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