The usual trick to sampling one line at random with uniform probability from an arbitrarily large file or stream is worth knowing because people have been askin

The usual trick to sampling one line at random with uniform probability from an arbitrarily large file or stream is worth knowing because people have been asking this as an interview question for >20years at this point[1]. 1. Store the first line with probability p=1 2. When the second line arrives, either keep the first line or with p=.5 drop it and replace it with the second line 3. Continue in this manner with each line. That is to say on the n-th line you either keep the line you have or with p=1/n you drop the line you have and replace the stored line with the new n-th line[2] 4. When you reach the end of the stream or the user quits the program or whatever, return the line you have stored. This will have been selected with uniform probability from the lines you have received. You can sketch the grid for a few lines you can see at every point you have all the lines with uniform probability. It's worth noting that by doing the algorithm in this way you are not in fact ever selecting with uniform probability from an unbounded set so noone is going to revoke your maths license or anything. You are only ever choosing between two things (keep the thing you have or drop it and replace it with a specific new thing). An intuition behind the proof that this does not violate any laws is that in the case of a truly infinite stream this algorithm would never terminate. [1] I know because over 20 years ago I was asked this as an interview question. [2] It's something like this probability. If I was actually answering the question I would work it out properly to be sure.