1
$\begingroup$

We have a large file that can't fit into internal memory. How do we randomly pick one line so that each line has the same probability to be picked?

And how do we randomly pick such n lines so that they all have the same probability?

We don't know the number of lines beforehand.

Any hint on where to start solving this, which algorithm to use, or at least an idea where to start would be appreciated.

$\endgroup$
3
  • $\begingroup$ How do you pick a line ? $\endgroup$
    – user16034
    Nov 13, 2017 at 19:09
  • $\begingroup$ Randomly. Or what do you mean? $\endgroup$
    – Maria
    Nov 13, 2017 at 19:23
  • $\begingroup$ How do you address the lines ? $\endgroup$
    – user16034
    Nov 13, 2017 at 19:24

1 Answer 1

2
$\begingroup$

Your problem is known as reservoir sampling. The algorithm maintains a currently picked line, whose initial value is the very first line. For $k > 1$, you replace the currently picked line by the $k$th line with probability $1/k$. If there are $n$ lines in total, the probability that the $k$th line is chosen is $$ \frac{1}{k} \cdot \left(1-\frac{1}{k+1}\right) \left(1-\frac{1}{k+2}\right) \cdots \left(1-\frac{1}{n}\right) = \\ \frac{1}{k} \cdot \frac{k}{k+1} \frac{k+1}{k+2} \cdots \frac{n-1}{n} = \frac{1}{n}. $$

$\endgroup$
2
  • $\begingroup$ I think OP is asking for the general case of Reservoir Sampling with buffersize = $n$. $\endgroup$ Nov 13, 2017 at 21:23
  • $\begingroup$ Yes, it's not completely clear. The answer can be found in the link in any case. $\endgroup$ Nov 13, 2017 at 21:24

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.