AFAIK does Fisher-Yates start with the highest range in rand not the lowest.

The proof may contain similar elements but I have trouble seeing the obvious analogy...

Cheers Rolf
_{(addicted to the Perl Programming Language :)
Wikisyntax for the Monastery}

Or do I miss a math trick to even the choices?

update

Actually it should work fine.

You have to think it from the end, the n'th line has a 1/n chance which is correct.

The line before is competing with the rest and has a 1/(n-1) chance, which is correct. °

And so on, proof by induction.

Indeed clever! =)

update

°) because the lines before have a combined chance of (n-1)/n and you have to multiply the odds. This leaves line n-1 with a chance of 1/n over all. .. :)

You’re a *much* better mathematician than I. It’s from the Camel, 8.6. Picking a Random Line from a File. I can’t screenshot it or cut and paste it either because the text contains math images. The trick lies in reselecting lines as it goes and the odds of selection being “fair” across the entire file. As you say, one line is guaranteed to be picked. As subsequent lines are scanned, the odds of choosing them, and replacing the original selection, become proportionate to how many lines have been read.

Update: didn’t see your update before I stubmitted. :P

Thanks for sharing! :)

It's a nice example of Conditional probability!

Cheers Rolf
_{(addicted to the Perl Programming Language :)
Wikisyntax for the Monastery}

PS:

> You’re a much better mathematician than I.

Well, it's my degree after all! :)