[Tutor] random number equations . . .

[Danny Yoo]

On Fri, 4 Jun 2004 rantek at pacific.net.sg wrote:

> Wouldn't using fixed point representation (32bit) improve the accuracy?


Hi Bill,


Fixed point representation would make the calculations more exact, but
numeric accuracy isn't the reason for the bias in the old
gimmeRandomInRange() function.


For reference, here's the definition of gimmeRandomInRange() again:

###
def gimmeRandomInRange(n):
    """Returns a random number between 0 and n, inclusive."""
    return int(round(random.random() * n))
###

Ideally, we'd like to get all numbers between '0' and 'n'.  I'm assuming,
that we want every number to be equally likely to be chosen.


We can visualize the expression "random.random() * n" almost as a function
that randomly chooses a point on the number line.  I like concrete
examples, so let's do this for n=2 again.

             (------------------------------------)
             0                                    2


The round()ing function take a number on the number line, and forces it
either up or down into an integer.  Here's another small diagram of how
round divides the number line into regions from 0 to 2.


                [0]            [1]          [2]
             (--------)(----------------)(--------)
             0        0.5       1       1.5       2


The bias comes from the observation that the region for [0] and the region
for [2] is simply smaller than the region for [1].  If we start choosing
random points on this line, we're more likely to fall into region [1] than
the other regions.



If we don't do the rounding, and just do the truncation, then we're
splitting the number line into something like this:

                     [0]                [1]
             (-----------------)(-----------------)
             0                  1                 2

The regions are of equal size, and so it's more uniform.  But there are
only two regions now.


That's why Glen modified the expression to:

    int(random.random() * (n + 1))

                     [0]                [1]                [2]
             (-----------------)(-----------------)(-----------------)
             0                  1                 2                  3



> >   I guess my ``teach the basics first'' philosophy shows through in a
> > bad way sometimes.

No, no, basics are fine.  And it's great that we're having this
discussion, since I'm sure folks wanted to see how random.random(), and
multiplication can be used to get random numbers.

I'm just trying to make sure folks see why using round() causes a slight
nonuniformity around the edges.  *grin*


Hope this helps!