[Octave-bug-tracker] [bug #54619] randi() is biased

[anonymous]

Follow-up Comment #11, bug #54619 (project octave):

The code below to try to quantify the bias is pointless, sorry. Verifying
correctness of a PRNG is a very complicated thing and nobody knows how to do
it right. You need to look at this issue from first principles: compute the
probability for each output value.

Here's a quick explanation of the problem with a extreme example:

Assume you have a 2-bit RNG (generates values in the range [0,3]. You want to
generate integers in the range [1,3]. You use Octave's method:


double x = RNG / 4
    # x = 0.00 -- 25%
    # x = 0.25 -- 25%
    # x = 0.50 -- 25%
    # x = 0.75 -- 25%
int n = floor(x * 3) + 1
    # x = 0.00 -> n = 1
    # x = 0.25 -> n = 1
    # x = 0.50 -> n = 2
    # x = 0.75 -> n = 3


You are now mapping 4 possible values into 3 bins. 2 of these bins will have a
25% chance of being hit, 1 bin will have a 50% chance. You can do the mapping
however else you want, the outcome will always have this bias. The only
solution is to reject 1 in 4 results of the RNG.

With a 53-bit RNG as Octave uses, this effect is much, much smaller, but it is
still there.

I hope this example clarifies the problem.

I suggested earlier to "throwing away randmtzig.cc and replacing that with
stuff from the Standard Library", but what I really meant was to replace the
`randi` M-file with a call to the Standard Library. The random number
generator you use is OK, and it might even be possible to use
`std::uniform_int_distribution` with it. I would recommend replacing that
also, just because it's less code to maintain, but if you need to keep the old
behaviour intact, maybe make the fewest changes that fix `randi`.

    _______________________________________________________

Reply to this item at:

  <https://savannah.gnu.org/bugs/?54619>

_______________________________________________
  Message sent via Savannah
  https://savannah.gnu.org/