Liinear distribution of random numbers?

[petertwocakes]

Hi

Is there a way of creating a distribution of random numbers (using
random() or any otherwise) that approximates:

frequency = N-x (0<=x<=N)

or

frequency = N/(x+1) (0<=x<=N)


Thanks

Steve

 

[geo]

Is there a  way of creating a distribution  of random numbers (using
random() or any otherwise) that approximates:
frequency = N-x (0<=x<=N)
or
frequency = N/(x+1)  (0<=x<=N)
Thanks
Steve

Perhaps the fastest way to generate
such variates with exactly those (scaled)
frequencies---and with specific C programs---may
be found in a web-available article:
"Fast Generation of Discrete Random Variables",
Marsaglia, Tsang and Wang,
www.jstatsoft.org/v11/i03/paper

 

[Ben Bacarisse]

generate a uniform random number on 0-1 by

rand()/(RAND_MAX + 1.0)

Then log transform it

x = (int) (log(uniform() * (e-1) + 1.0) * N)

.... and you hope the C implementer of rand() has not joined your
campaign for 64 bit ints!

 

[petertwocakes]

Perhaps the fastest way to generate
such variates with exactly those (scaled)
frequencies---and with specific C programs---may
be found in a web-available article:
"Fast Generation of Discrete Random Variables",
 Marsaglia, Tsang and Wang,www.jstatsoft.org/v11/i03/paper

Thanks, interesting read.

 

[petertwocakes]

generate a uniform random number on 0-1 by

rand()/(RAND_MAX + 1.0)

Then log transform it

x = (int) (log(uniform()  * (e-1) + 1.0) * N)

(e is Euler's number to put your random number into the range 0-N-1).

You can also square root transform it, or use a cosine transform.

I am not sure what the best approximation to a linearly increasing density
function actually is. If you do several thousand of them and plot out the
histogram you can see what is acceptable.

x = (int) (log(uniform() * (e-1) + 1.0) * N)

With a million samples, that gives something almost linear with just a
bit of sag(?); not sure what's happening yet, but it's a good starting
point for further exploration.

So far, this gives a reasonable linear:
r = random()% (int)sqrt(random()%((N*N)-1) +1);
and reciprocal:
r = random()%(random()%(N-1)+1);

Not very efficient though.

Steve

 

[Walter Banks]

Perhaps the fastest way to generate
such variates with exactly those (scaled)
frequencies---and with specific C programs---may
be found in a web-available article:
"Fast Generation of Discrete Random Variables",
Marsaglia, Tsang and Wang,
www.jstatsoft.org/v11/i03/paper

A very good practical reference I use for generating random
numbers with various distributions is,

"Statistical Distributions" N.A.J. Hastings and J.B.Peacock
ISBN 0-470-35889-0 QA273.6.H37
Halstead Press
Distributed by Wiley 1974

There are later editions. This book is worth tracking down
for anyone who needs good random number generators.


Regards,


--
Walter Banks
Byte Craft Limited
1 519 888 6911
http://bytecraft.com
(e-mail address removed)

 

[Ben Bacarisse]

Is there a way of creating a distribution of random numbers (using
random() or any otherwise) that approximates:

frequency = N-x (0<=x<=N)

The function you want is pow(rand_in_0_1(), 0.5) * N though the
suggestion to use a table (as in the Marsaglia, Tsang and Wang paper)
may well be faster.

frequency = N/(x+1) (0<=x<=N)

I think this one is pow(rand_in_0_1(), 2.0) * N. It may be too late
now, but I have found this a very useful reference:

http://ftp.arl.mil/random/random.pdf

 

[CBFalconer]

.... snip ...

A very good practical reference I use for generating random
numbers with various distributions is,

"Statistical Distributions" N.A.J. Hastings and J.B.Peacock
ISBN 0-470-35889-0 QA273.6.H37
Halstead Press
Distributed by Wiley 1974

There are later editions. This book is worth tracking down
for anyone who needs good random number generators.

Huh? How can you consider a 'random sequence' with 'controlled
distribution' to be a random number sequence? Or do those phrases
not mean what I attribute to them?

 

[osmium]

Huh? How can you consider a 'random sequence' with 'controlled
distribution' to be a random number sequence? Or do those phrases
not mean what I attribute to them?

They are random drawings from a specified distribution. For a normal
distribution centered on zero, numbers near zero are more likely than
numbers two or three sigma away from zero.

 

[Ben Bacarisse]

Huh? How can you consider a 'random sequence' with 'controlled
distribution' to be a random number sequence?

The numbers that result from calling rand() are usually a good
approximation to sampling from a discrete uniform distribution over
[O, RAND_MAX]. By computing some function of the these numbers it is
possible to approximate other distributions. For example,

int bin(void)
{
int r = rand();
return !(r & 1) + !(r & 2) + !(r & 4) + !(r & 8) + !(r & 16);
}

will return a pseudo-random number with a binomial distribution.
Controlling the distribution to some extent does not prevent the
sequence from being pseudo-random.

Or do those phrases
not mean what I attribute to them?

If you said what you mean by them we'd know!

 

[Ben Pfaff]

The numbers that result from calling rand() are usually a good
approximation to sampling from a discrete uniform distribution over
[O, RAND_MAX].

That's only true if the value of O is 0

The FAQ claims that "the low-order bits of many random number
generators are distressingly *non*-random," by the way.

 

[Nate Eldredge]

Huh? How can you consider a 'random sequence' with 'controlled
distribution' to be a random number sequence? Or do those phrases
not mean what I attribute to them?

"Random" to a mathematician means a quantity whose value is not
completely predictable, and is influenced by chance. It is possible
that some values are more or less likely than others; this information
is expressed by the "distribution" of the quantity, which specifies the
probabilities of the possible outcomes. If every outcome is equally
likely, the distribution is said to be "uniform"; this is what
laypeople often have in mind when they use the word "random".

Rolling a die produces a random number between 1 and 6, distributed
uniformly. Rolling a pair of dice produces a random number between 2
and 12 whose distribution is not uniform (7 is six times more likely
than 2).

The OP wants to generate a random number such that the probability of
the value being x is given by some function f(x). f here would
technically be called a probability mass function.

The antonym of "random" is "deterministic".

 

[Ben Bacarisse]

The numbers that result from calling rand() are usually a good
approximation to sampling from a discrete uniform distribution over
[O, RAND_MAX].

That's only true if the value of O is 0

Ha! :-(

The FAQ claims that "the low-order bits of many random number
generators are distressingly *non*-random," by the way.

Yes, it probably needs to be said every time rand() crops up though
the result might still be considered a "good approximation" to a
uniform distribution. For example, in the context to this thread
where we compute f(rand() / (RAND_MAX + 1.0)) the bottom bits hardly
matter (unless f is really odd and looks at the representation of its
floating argument!).

 

[Walter Banks]

I think this one is pow(rand_in_0_1(), 2.0) * N. It may be too late
now, but I have found this a very useful reference:

http://ftp.arl.mil/random/random.pdf

This is a very useful reference complete with simple example code
for each of the random distribution algorithms. Similar in them to the
reference I detailed, this is a collection of algorithms to produce
random numbers with know statistical distributions starting with a
random number generator with a a linear random distribution.

These are extremely useful for Monte Carlo simulation and
communication simulation applications.

Nice Find

Regards,

 

[lawrence.jones]

The FAQ claims that "the low-order bits of many random number
generators are distressingly *non*-random," by the way.

Which overstates the issue. The low-order bits of *most* random number
generators, including the example one in the C standard, are just fine.
As far as I know, there was only *one* reasonably wide spread random
number generator whose low-order bits could be accurately described that
way. Unfortunately, it was *very* wide spread. Fortunately, it's
mostly gone now and it's very easy to detect (the generated sequence
strictly alternates between even and odd numbers).

 

[Phil Carmody]

Huh? How can you consider a 'random sequence' with 'controlled
distribution' to be a random number sequence? Or do those phrases
not mean what I attribute to them?

Almost certainly the latter.

Go to sci.math and ask "how can you consider a sequence of 'random
variables' with a 'probability density function' to be random?".
Then translate the answer you get back into the computing domain.

Phil

 

[Phil Carmody]

The numbers that result from calling rand() are usually a good
approximation to sampling from a discrete uniform distribution over
[O, RAND_MAX].

That's only true if the value of O is 0

The FAQ claims that "the low-order bits of many random number
generators are distressingly *non*-random," by the way.

The FAQ needs updating. Very few c libraries have the dismal
properties that many did back when that FAQ answer was written.
Probably only one (and if so, yes, it's just a shame it's
installed on a billion computers owned by people who don't
care whether or not its c library is crap or not).

Phil

 

[Phil Carmody]

Which overstates the issue. The low-order bits of *most* random number
generators, including the example one in the C standard, are just fine.
As far as I know, there was only *one* reasonably wide spread random
number generator whose low-order bits could be accurately described that
way. Unfortunately, it was *very* wide spread. Fortunately, it's
mostly gone now and it's very easy to detect (the generated sequence
strictly alternates between even and odd numbers).

MS have, for instance, used the quite depressingly, but predictably,
pitiful n' = (n*a+c)%m with a=16598013, c=2820163 and m=2^24.
I wouldn't call stuff from, or at least yclept, 2003 'mostly gone'.

Phil

 

[lawrence.jones]

MS have, for instance, used the quite depressingly, but predictably,
pitiful n' = (n*a+c)%m with a=16598013, c=2820163 and m=2^24.
I wouldn't call stuff from, or at least yclept, 2003 'mostly gone'.

Precisely where did you find that generator? My MS Visual Studio 6
(circa 1998) source has:

seed' = seed * 214013 + 2531011
n' = (seed' / 65536) % 32768

which may not be stellar, but it's certainly not depressing or pitiful.
(And it appears VS 8 is still using the same generator.)

 

[Ben Pfaff]

As far as I know, there was only *one* reasonably wide spread random
number generator whose low-order bits could be accurately described that
way. Unfortunately, it was *very* wide spread.

Which one?