Earlier quoted context omitted.
The algorithm for the simplest variant of that problem (take a single random sample from a list of a priori unknown length) can be derived by simple inductive reasoning. If the list has size 1, the problem is trivially solved. Otherwise suppose we have a list (x:xs) and we recursively solve the problem for xs. If all the recursion returns is the random sample from xs, we clearly have insufficient information to take…
>Then the result for (x:xs) is (r, n) where n = n' + 1 and r = x with probability 1/n or else r'. Do you mean r = x:r' instead of r = x?
When you approach it inductively the way I did, there really isn't any choice in the matter, which is why this algorithm design technique is so powerful. Udi Manber developed the technique in his paper Using Induction to Design Algorithms from 1988 and later used it throughout his great old book Introduction to Algorithms: A Creative Approach from the early 1990s. Here's the paper in case you're curious: http://akira.ruc.dk/~keld/teaching/algoritmedesign_f05/Artik...