> Proving that this really gives all lines the same chance of ending up in $l sounds like a fun math exercise. Quick try with recursive proof: Assume all prec

> Proving that this really gives all lines the same chance of ending up in $l sounds like a fun math exercise. Quick try with recursive proof: Assume all preceding n-1 lines have equal probability of having been picked (p = 1/(n-1)). This is clearly true for the baseline n=2. Then for line n, it will replace the picked line with probability p=1/n, since that is in the algo. Any previous line will now have p=[1/(n-1)] * (1 - 1/n) = 1/n and the assumption holds.