On Sat, Sep 01, 2007 at 02:24:25PM +0200, Alban Hertroys wrote:
> Oh, now I see... The first time guarantees that v has a value (as
> random() < 1/1), and after that there is a decreasing chance that a
> new row gets re-assigned to v. That means the last row has a chance
> of 1/n, which would be it's normal chance if the distribution were
> linear, but doesn't the first row have a chance of 1/(n!) to be
> returned?
No. Consider at the first row it has chance 1 of being selected. At the
second row it has chance 1/2 of being *kept*. At the third row it has
chance 2/3 of being kept. At row four it's 3/4. As you see, the
numerators and denominators cancel, leaving 1/n at the end...
Neat huh?
--
Martijn van Oosterhout <kleptog@svana.org> http://svana.org/kleptog/
> From each according to his ability. To each according to his ability to litigate.