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@xxxxxxxxx> http://svana.org/kleptog/ > From each according to his ability. To each according to his ability to litigate.
Attachment:
signature.asc
Description: Digital signature
