Timeline for C# Debiasing from Good PRNG
Current License: CC BY-SA 4.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 11, 2021 at 21:32 | comment | added | aepot | @harold exactly! | |
| Jun 11, 2021 at 21:18 | comment | added | user555045 | @aepot any method that does not reject some samples is biased for a fundamental reason: you cannot fairly spread N things over M buckets except in the special case that M divides N. How the spreading is done does not matter, no method can work. | |
| Jun 11, 2021 at 19:55 | comment | added | aepot |
OK, return (int)((long)maxnum * RNG.NextPositiveInt() / int.MaxValue)). Polling the RNG breaks the distribution profile, anyway. Because you're skipping output by the fixed scenario. That's causing a clamping method consequence appear in the genereated output. Benchmark it, get the stats, measure the distribution behavior. Reading books is good but testing is better.
|
|
| Jun 11, 2021 at 19:38 | comment | added | pepoluan | Finally, there's this video: channel9.msdn.com/Events/GoingNative/2013/… <== the speaker did not mince words and explicitly stated that scaling with FP results in hilariously non-uniform distribution, and he explicitly criticized "people on Stack Overflow recommending this method". | |
| Jun 11, 2021 at 19:37 | comment | added | pepoluan | Do bear in mind that my need is just to clamp the RNG. Another team is in charge of the generation, and their spec is that the resulting RNG must be uniformly-distributed. As long as they fulfill their specs, I am required to ensure that clamping does not change the uniform distribution. There are ... certain industries whose regulatory bodies require a formal proof of uniform distribution. The inaccuracy of FP will cause sawtooth pattern in the distribution, as numbers get shifted to the left or right when the FP cannot accurately represent the scaling. | |
| Jun 11, 2021 at 19:28 | comment | added | aepot | Ok, this makes some noise to RNG making state-based predictability somewhat more complicated (RNG security improvement?). Btw, you're not doing exact computations but random numbers generation. How much CPU time do you want to pay to avoid that noise? What it may affect? Here's no sense to stay in integers, it doesn't worth to introduce polling loop instead of simple FP division+multiplication. Or I'm missing something. | |
| Jun 11, 2021 at 19:19 | comment | added | pepoluan |
@aepot Although in theory that should work (scaling the range), in practice performing the floating point division will result in numbers 'not accurately representable' in floating point (e.g., 0.1 -- and integer multiples of -- cannot be represented in floating point accurately). This greatly complicates trying to prove that the scaling does not cause a bias, unlike the simple axiom of "truncating a uniform dist will result in a still-uniform dist". In short, I'd like to stay in the integer land when possible.
|
|
| Jun 11, 2021 at 19:02 | history | edited | pepoluan | CC BY-SA 4.0 |
Explain about "debiasing"
|
| Jun 11, 2021 at 18:58 | comment | added | aepot |
Ok, return (int)((double)maxnum / int.MaxValue * RNG.NextPositiveInt()) or you may initially generate double to reduce conversion complexity. Anyway this one faster than any of the optimistic scenarios applied to the initial solution.
|
|
| Jun 11, 2021 at 18:54 | comment | added | pepoluan | @aepot That will cause a biased output; the lower values will appear more often than the higher values. | |
| Jun 11, 2021 at 17:21 | comment | added | aepot |
Why not simply return RNG.NextPositiveInt() % maxnum?
|
|
| Jun 11, 2021 at 16:10 | history | asked | pepoluan | CC BY-SA 4.0 |