Comment by asxd
4 years ago
Out of curiosity, why do you think having a good random number generator is problematic? It seems like it's easy enough to access one in most situations.
4 years ago
Out of curiosity, why do you think having a good random number generator is problematic? It seems like it's easy enough to access one in most situations.
Yes, exactly. There are so many to choose from. ;)
There are several discussions here in HN about PRNGs of different kinds and people still want to invent new ones. Why? Because old ones do not satisfy them in full.
Returning to the problem at hand. How many consecutive ties do we expect? This would helps us to define how many bits should we extract from state - for N expected consecutive ties we should extract 2log_2(N) bits or more (birthday paradox). For 64K ties we need 32 bits, which is fair amount of state, 1/8 of typical PRNG discussed here.
Most PRNGs are splittable and this also brings the question "how does splitting affect bits generated?" Will these bits be correlated between splitted generators?
I definitely do not want correlation coefficient computation that produces close results for provably different sets due to correlation between tie-breaked sections filled with random numbers.
> Yes, exactly. There are so many to choose from. ;)
Just use a good PRNG to pick one of them :D
how do you sample from an arbitrary probability distribution? it is not a trivial problem at all
Why do you need an arbitrary distribution? We are talking about breaking ties, just use uniform. You can probably just use RDRAND.
They are equivalent. Generating an arbitrary distribution from a uniform one is trivial.
1 reply →
i agree. to break ties uniform distribution should be sufficient
I guess I assumed the operative word was "good". The term "random number generator" almost always refers to a generator that intends to produce a uniform distribution.
If you can sample from a uniform distribution, it is trivial to turn that into any arbitrary distribution.