The OP should have mentioned that it's this algorithm:

https://en.wikipedia.org/wiki/Reservoir_sampling

IMO it's a lot clearer if it's not in Perl ...

The pseudocode in Wikipedia also avoids division.

If you want to monte carlo it, https://gist.github.com/patio11/546c64c927c749c69964b18527fa... ; feel free to adjust the constants upwards and/or do a chi squared test after doing so.

It didn't sound plausible to me (because I misunderstood what the algorithm was; yay perl), hence quickly testing it, but it seems to work, and after appreciating what the algorithm actually is (see sibling replies), it not only works but it _should_ work. (There is a CS versus engineering joke in here, somewhere.)

Perhaps surprisingly, yes, it does! This is called "reservoir sampling", and a blog post with some more details is available at https://blog.plover.com/prog/weighted-reservoir-sampling.htm....

It does.

It's a special case of reservoir sampling.

https://en.wikipedia.org/wiki/Reservoir_sampling