Duplicate results due to lack of entropy using multinomial without replacement?

[KFrank]

Hi Jeff!

@jeffc

I’m trying to confirm that I’ve found a bug in multinomial without replacement.

I can confirm your result, and I do believe that it is a bug.

It seems to only use a 32 bit random number as a ‘seed’ for its own random number generator for choosing all the samples.

This isn’t the cause (but I don’t know what the cause is).

torch.multinomial() uses by default pytorch’s “global” random-number
generator which, on the cpu, is (from memory) a mersenne twister and
has a period that is vastly greater than 2**32.

This means at most there are only 2^32 permutations it will generate without replacement, even when there are far more possible.

I don’t this that this is true. I speculate (but have not confirmed) that
multinomial() will generate all permutations with non-zero probability,
but does so sufficiently non-uniformly that duplicates are generated
much too frequently.

I wrote a short app showing that multinomial without replacement always generates at least one DUPLICATE PERMUTATION every few 10s of thousands of iterations. Am I missing something?

I don’t think that you are missing anything. I see the same thing
with a similar script.

I will start a new thread with the details to highlight this bug you’ve
found.

[Edit: This is the new thread.]

Best.

K. Frank