Jump to content


Photo

Non-linear random number generators


  • Please log in to reply
12 replies to this topic

#1 Yal

Yal

    Gun Princess

  • Global Moderators
  • 5813 posts
  • Version:GM8.1

Posted 22 May 2012 - 01:28 PM

On the train today I was thinking about something I read a while ago, which I might condense to a single statement along these lines:

"All random generators used in computers today have the form xn+1 = a(xn + B) mod c"

Notice how the generator generates numbers with a linear formula (if we ignore the modulus part)? I was thinking a bit about what would happen if one would instead make a random generator that worked along the lines of, say,

xn+1 = a(xn2 + B) mod c

or maybe using trigonometric, logarithmic or other functions. One instantly realize that the numbers won't get evenly distributed anymore, but perhaps for some applications that's desireable. (For instance, Gaussian randomness isn't evenly distributed, nor is Mandelbrotian).


What's your view on this? Do you instantly realize some potent flaw I've missed? Is it an interesting subject? Any application for it striking your mind?
  • 0

#2 chance

chance

    GMC Member

  • Reviewer
  • 5758 posts
  • Version:GM:Studio

Posted 22 May 2012 - 11:48 PM

I was thinking a bit about what would happen if one would instead make a random generator that worked along the lines of, say,

xn+1 = a(xn2 + B) mod c

or maybe using trigonometric, logarithmic or other functions.

Interesting... so show us. What does your distribution look like?


One instantly realize that the numbers won't get evenly distributed anymore, but perhaps for some applications that's desireable. (For instance, Gaussian randomness isn't evenly distributed...

Yes, non-uniform distributions are very useful for certain applications and simulations. But the usual way to generate them is through a transform (like Box-Muller, for example... although that can be slow). Or more commonly through transform sampling, where you compute the CDF of whatever distribution you want ahead of time, then use the uniform random numbers to "index" your way into that sample.

That way, you can easily specify the mean and variance of the non-uniform distribution.
  • 0

#3 Yal

Yal

    Gun Princess

  • Global Moderators
  • 5813 posts
  • Version:GM8.1

Posted 23 May 2012 - 07:18 AM

Interesting... so show us. What does your distribution look like?

I was onto the subject of "all non-linear RNGs" rather than a specific one, but I could settle down on that example and run a simulation. Gimme a sec...

*starts up MATLAB*

Okay, I've run a modest simulation using the following formula:

xn+1 = 17(xn3 + sin(xn2) + 3) mod 177
Init seed: 1337

The result was something like this:

Posted Image
The distribution makes a select few points get a vast majority of the samples (but pretty evenly distributed among them!), so I guess my idea is flawed. It might be because modulo works best with linear distributions, or perhaps it's just me picking bad values to use (some random, small primes)... or it's just the method that's bad. I sorta imagined I'd get an inverted bell curve.

Here's my code if you're interested:
Spoiler

  • 0

#4 paul23

paul23

    GMC Member

  • Global Moderators
  • 3355 posts
  • Version:GM8

Posted 23 May 2012 - 10:24 AM

It's not "guess work" at all. - One could easily create a given distribution; simply by feeding a uniform random number to the inverse of the integral of the function you wish to use. (As long as the function is continuous and integrable). For example to create a linear distribution simply take the square root of the number.


this topic covers the subject quite well.. Now obviously for certain distributions one can't calculate the inverse integral, notable example is the normal distribution. In such cases different methods should be used.


These things can/are very usefull in gamse; looking at the normal distribution one could use that to create random numbers which are "close" to the original base yet can be everything.



All applications I know first create a uniform distributed random number.. And then modify that number.
  • 0

#5 Yal

Yal

    Gun Princess

  • Global Moderators
  • 5813 posts
  • Version:GM8.1

Posted 23 May 2012 - 10:53 AM

Mmm... I guess my approach was a little naïve; "I got a nice idea nobody else has thought up before! I gotta test it!".
  • 0

#6 Yourself

Yourself

    The Ultimate Pronoun

  • Retired Staff
  • 7341 posts
  • Version:Unknown

Posted 24 May 2012 - 03:16 AM

"All random generators used in computers today have the form xn+1 = a(xn + B) mod c"


Be careful with that word "all". There's actually a lot of generators that don't fit quite so simply into that form.

You might find this one interesting.

One thing you have to be careful of is the period of these sequences. In fact, the generator you tested has a very short period, it'll generate this:

52, 15, 62, 80, 66, 175, 103, 85, 174, 115, 166, 64, 159, 17, 27, 134, 164, 36, 82, 109, 98, 43, 114, 95, 19

And then will repeat the bold section over and over, so every 24 numbers, the sequence repeats. Now, since your generator is stateless (the next value depends only on the previous one), the best period you could get is 177 (because that's the number of different inputs you can produce, no matter what one of them would have to repeat after that).
  • 0

#7 Yal

Yal

    Gun Princess

  • Global Moderators
  • 5813 posts
  • Version:GM8.1

Posted 29 May 2012 - 08:41 AM

Be careful with that word "all". There's actually a lot of generators that don't fit quite so simply into that form.

I wrote,

...I was thinking about something I read a while ago, which I might condense to a single statement along these lines...

I wasn't so clear with the disclaimer, but I meant that the statement I read stated that, not that I did. Actually, it was me doubting it that led me to that idea.

In fact, the generator you tested has a very short period, it'll generate this:

That explains why all the values have exactly the same absolute frequency.


It was an interesting read; I think that next time I get an idea like this I should probably look it up on Wikipedia instead of making a topic here and wasting everybody's time.
  • 0

#8 Yourself

Yourself

    The Ultimate Pronoun

  • Retired Staff
  • 7341 posts
  • Version:Unknown

Posted 29 May 2012 - 05:31 PM

It was an interesting read; I think that next time I get an idea like this I should probably look it up on Wikipedia instead of making a topic here and wasting everybody's time.


It's not a waste of time. It got me interested enough to respond and that's pretty rare nowadays.
  • 3

#9 icuurd12b42

icuurd12b42

    Self Formed Sentient

  • Global Moderators
  • 14384 posts
  • Version:GM:Studio

Posted 30 May 2012 - 07:41 AM

I saw this show about various heists a while back. So this guy figured out the random generator for Kino games played at various Casinos. Made a program for his computer where he would feed the numbers in his room with a partner via radio while he was on the floor. Eventually the sequence would be determined, he'd play the sequence and win a bundle.
  • 0

#10 masterofhisowndomain

masterofhisowndomain

    The Designer

  • GMC Member
  • 3639 posts
  • Version:GM8.1

Posted 30 May 2012 - 05:36 PM

The following are the thoughts of someone who studied mathematics up to the age of sixteen. I take no responsibility for any stress caused by reading the proceeding statements ...

My first response to this was "what about using pi as a random number generator?", i.e., gathering a sequence of the digits in the decimal expansion of the number. So I looked into it, and there are some interesting conclusions about using pi for this:

Physicists Fischbach and Tu conducted a study into the randomness of pi, with comparisons to other Random Number Generators (RNGs) and concluded: "Our work showed no correlations or patterns in pi's number set – in short, pi is indeed a good source of randomness," Fischbach said. "However, there were times when pi's performance was outdone by the RNGs."
- Source: http://news.uns.purd...schbach.pi.html

Marsaglia's "On the Randomness of Pi and Other Decimal Expansions" is another interesting article on the topic (presumably, the maths goes soaring over my head ...), and he says the pertinent:
  • The digits in the expansion of irrationals such as π, e and √2, as well as those of rationals k/p for large primes p, seem to behave as though they were the output of a sequence of independent identically distributed (iid) random variables.
The 15 tests for randomness he describes in the Appendix are absolutely fascinating, but I'll let you decide how relevant they are.
- Source: http://interstat.sta...les/0510005.pdf

But (and I'm cautious of derailing the topic -- but I don't have the answers or the know-how to even begin to answer them), is pi an example of randomness or pseudorandomness? Or does this depend on our definition of randomness (uniform, pseudo, Kolmogorov)?

Edited by masterofhisowndomain, 30 May 2012 - 06:13 PM.

  • 0

#11 Zesterer

Zesterer

    Professor of Articul

  • GMC Member
  • 1018 posts
  • Version:GM8

Posted 10 July 2012 - 05:54 PM

Sorry if I'm bumping in on this very old conversation, and with such an irrelevant or inexperienced topic... But if I wish to skew my random numbers up, I use:
x=random(random(1))
Or if I wish to skew it downwards, I do:
x=1-(random(random(1)))

Is what I just said totally irrelevant, or does it have a point?

Zesterer
  • 0

#12 Yourself

Yourself

    The Ultimate Pronoun

  • Retired Staff
  • 7341 posts
  • Version:Unknown

Posted 10 July 2012 - 11:41 PM

Sorry if I'm bumping in on this very old conversation, and with such an irrelevant or inexperienced topic... But if I wish to skew my random numbers up, I use:

x=random(random(1))
Or if I wish to skew it downwards, I do:
x=1-(random(random(1)))

Is what I just said totally irrelevant, or does it have a point?

Zesterer


One problem I see pop up a lot is this idea people get that something is "more" random. You're not actually making your numbers "more" random because that doesn't really make sense. You are, however, altering the distribution. Now, random(random(1)) is the same thing as random(1) * random(1). We can analyze the distribution of this. Let X and Y be independent identically distributed random variables with a uniform distribution in the range [0, 1).

Now, we can introduce a random variable Z = X Y. Let's figure out what the distribution of this variable is. We'll start with the CDF because that's easier to work with. So, by definition:



Where P(Z <= z) denotes the probability that Z is less than or equal to z. We can replace Z with its definition:



Now, we can compute this probability by figuring out the area of the region bounded by 0 < x < 1, 0 < y < 1, and x y < z. We can actually turn this into an integral with respect to x. First, we note that the curve y = z / x intersects y = 1 at x = z. So we can split the area of the region into two parts. The first part is for x < z, in that case we just have a rectangle whose height is 1 and whose width is z, and the area of that is just 1*z = z. The area of the portion for x > z is given by this integral:



Adding these together we get the following:



Which looks like this:

http://www.wolframalpha.com/input/?i=plot+z+-+z+ln+z+from+0+to+1

We can find the PDF by taking the derivative of this:



Now, the pdf of a uniform random variable in the range [0, 1) is just 1 (in that range, 0 elsewhere). So you can see how you're skewing the distribution by comparing them:

http://www.wolframalpha.com/input/?i=plot+-ln+z+and+1+from+0+to+1

So you're making it more likely for numbers less than about 0.368 to show up while making numbers greater than that less likely to show up.

Now, I don't want to give them impression that this is "wrong" it's not. If this is the kind of distribution you want, then it's perfectly okay. I just want to make sure that people really understand what it is that they're doing.
  • 1

#13 Yal

Yal

    Gun Princess

  • Global Moderators
  • 5813 posts
  • Version:GM8.1

Posted 05 October 2012 - 11:09 AM

I'd forgotten all about this topic. Interesting part with the random(random(1)) bit. Will remember that.

Pondering the "more random" fallacy is quite interesting, too. You're outputting a random number on a set interval, but with a random upper cap (determined by the inner call). All numbers of the inner call are possible outputs of the outer call, but lower numbers get more likely since low numbers can be the result no matter if the cap set by the inner call is high or low, but high numbers can only result when the cap is high.
  • 0




0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users