Can someone explain random number generation?

[nishantp]

I know how to use Random number generation functions and all....but im wondering how those functions themselves work. I know the Rnd function in VB is based on the Timer, but if it does a fixed set of calculations then its not random. How does it come up with random numbers?

[Guv]

Computers do not generate random numbers. What they generate are called pseudo random numbers by experts in statistics and simulation technologies.

The VB Rnd Function can be used to generate the same series of numbers each time your program is used. This is desirable for some purposes. The Randomize Statement is used to make sure that a new series is generated each time your program is used. It is usual to supply no parameter to Randomize, in which case it uses the System Timer to generate a parameter and initialize the Rnd Function.

The system timer is not used by the Rnd Function. Most pseudo random number generators use some fairly simple function to generate a series of numbers. The last number generated is usually used as input to generate the next pseudo random number. In many cases, the function is linear like the following.

Next = A * Last + B, where A & B are constants.

For critical simulation projects, it is necessary to do some analysis or research to choose a pertinent generator. One size does not fit all.

There are various physical processes known (or considered) to be random processes. The statistics of the various processes are not the same. For example: Radioactive decay has Poisson Statistics (I think). Other processes have the statistics of a uniform distribution, which is what I think the VB Rnd generator simulates. I think that two normal distributions (each with a different mean and deviation) can be used to simulate dropping bombs from an airplane or hitting the green with a golf ball.

If you use the wrong generator to simulate some physical process, you will get erroneous results. The VB generator is fine for many purposes, but cannot be relied upon for critical applications. For example, it simulates casino craps to about 3-5 significant figures, but is not a precise simulator of that game.

[kedaman]

I know we have had this discussion earlier but

Originally posted by Guv
There are various physical processes known (or considered) to be random processes. The statistics of the various processes are not the same. For example: Radioactive decay has Poisson Statistics (I think). Other processes have the statistics of a uniform distribution, which is what I think the VB Rnd generator simulates. I think that two normal distributions (each with a different mean and deviation) can be used to simulate dropping bombs from an airplane or hitting the green with a golf ball.

Randomness could be defined as unpredictability, a subjective concept. Objectively that would mean that randomness is an illusion. From case to case, if something isn't predictable, then you might call it random but the effect is the same as if it was, but that doesn't make it definite.

[nishantp]

Originally posted by Guv

Next = A * Last + B, where A & B are constants.

Im assuming this is a simplified example...since if you know A and B you could easily find the next "random" number.
If that is correct...then the Random numbers are like encrypted text. Only that the Time they were encrypted matters, and they are seemingly random. Using that analogy...has VB's Rnd function been cracked?

[thinktank]

Originally posted by kedaman
I know we have had this discussion earlier but

Randomness could be defined as unpredictability, a subjective concept. Objectively that would mean that randomness is an illusion. From case to case, if something isn't predictable, then you might call it random but the effect is the same as if it was, but that doesn't make it definite.

kedaman oh...pleazz

let's keep philosophy out of mathematics for a second, nishantp is serious

[Guv]

Nishantp: Pseudo random numbers are not intended to be unpredictable. These generators are designed to produce a series of numbers which pass certain statistical tests. Their purpose is to provide a method of simulating physical processes known to produce statistical rather than analytical data.

If random number generators had been invented recently, the numbers produced would probably be called chaotic instead of pseudo random. If you know the algorithm and the initial seed, the output from a random number generator is completely predictable. Note that, while predictable, you cannot usually determine (for example) the thousandth number without doing the thousand cycle calculation.

Pseudo random numbers are sometimes used as part of an encryption algorithm, but that is not their intended purpose. Some Key encryption algorithms are almost identical to random number generators, and would not be secure if the key were known.

Functions like Next = A * Last + B are often used for generating pseudo random numbers, with A & B being constants. Other simple functions are also used. Arithmetic modulo 16^n or 10^n is usually used, which truncates the high order part of the products and sums.

Many years ago I was paid handsomely by a naive friend of mine who thought he had a method of beating casino craps and roulette. He paid me to simulate those games so he could test his ideas. While silly, it is a good example of the use of random number generators to simulate physical processes. I told him in advance that his schemes would not work, but he insisted and I took his money (in advance).

Oddly enough the random number generator built into the old Basic compiler I used was not usable for simulating craps. It actually made the game look unfavorable to the casino. I was forced to do some research to find a suitable random number generator. Since the Basic generator produced uniform distribution statistics, I think it might have done a decent job with roulette, but while I was doing the craps research, I found a generator recommended for roulette.

The Rnd Function in VB 6.0 does a reasonable job of simulating craps, but is not the best generator for that purpose. Problems with random number generators have often caused problems for naive users. Statistics and probability are far more subtle than you might expect if you do not have the pertinent background knowledge.

BTW: My former friend did not believe the results of the simulations and lost quite a bit at the casinos before he gave up.

[nishantp]

Thanks for your replies. I learnt a lot

[Guv]

Kedaman: From a previous post of yours

Randomness could be defined as unpredictability, a subjective concept. Objectively that would mean that randomness is an illusion. From case to case, if something isn't predictable, then you might call it random but the effect is the same as if it was, but that doesn't make it definite.

I cannot comment on the part of the above which I bolded because I just do not understand what you are trying to say.

In general, I do not understand many of your views. It might be due to our having fundamentally different world views. Many of your posts are clear, and I have no doubt that you are intelligent and knowledgable in many areas.

Yes, randomness could be defined as unpredictability, but it is not defined that way, except perhaps as one part of a dictionary definition. Predictability is not a central issue in and is hardly mentioned by the literature of probability and statistics.

The term random without a context is almost meaningless jargon. It is applied to data which corresponds to formally defined statistical distributions such as Poisson, binomial, uniform, Chi-Square, et cetera. Without the context of those distributions and the pertinent mathematics, the term is almost meaningless.

You seem to have some misgivings about so called random processes and statistical mathematics which I do not understand.

The mathematics of statistics and probability theory are as well founded as the mathematics of differential equations. If you quarrel with the mathematics, you are attacking formal logic, which is behind almost every mathematical discipline.

It is known that certain measurable phenomena are accurately modeled by the mathematics of statistics and probability. If you want to argue that the phenomena are illusions, that is a philosophical issue. If you want to argue that the mathematics does a bad job of modeling the phenomena, you are wrong, or perhaps unwilling to accept some well established methods of logic and science. If you want to claim that future developments will show that current beliefs are fundamentally flawed, you are being more subjective that the people (like me) who accept current science at face value.

If I were unwilling to accept current science at face value, I would find it difficult to trust my computer, my auto, the bridges I cross, all of the gadgets of modern technology. My belief in science and disbelief in various forms of nonsense might be a very subjective view of the world, but it seems to work for me.

[kedaman]

Guv

Originally posted by Guv
In general, I do not understand many of your views. It might be due to our having fundamentally different world views. Many of your posts are clear, and I have no doubt that you are intelligent and knowledgable in many areas.

The reason we get stuck in a lot of cases is on the definitions of several diffuse concepts, in full practice we could agree on most issues but somtimes we disagree just based on fundamental concepts that relies on subjectivity nature.

Randomness is a component you try to eliminate because of it's unpredictability. To define randomness I'll mention two versions:

Boolean randomness
R is a boolean variable which can theoretically be given either false or true but in practice will be assigned false or true as a moment of it's evaluation. R(i) is an array of random boolean values which will be assigned true or false independently.

Probability and statistics is derived from the existance of randomness (unpredictability) and experience of randomness in order to eliminate (or minimize) it in certain issues, that is introducing randomness as a subjective concept into the world of predictability - math, for there to be any practical use of probability and statistics.

ex.
lim x->+infinity (S(n=1 to x)R(n))/n = ½

In practice x will approach a certain value and there will be certain probabilities that the result is 0 or 1, which is definitely not what you call "random" therefore randomness is subjective and depends on in what context you need unpredictability and what is acceptable unpredictability. In the above case if x approaches a big enough value the result has to approach ½.


Analogue Randomness

r is a Real value 1>=r>=0. Can be derived from boolean randomness R:
lim x->infinity (S(n=1 to x)R(n)/(n+1)) = r

r is more close to the rnd() function we use in vb since it returns a floating point variable.

Anyways, my point is that "pseudo random" is a bad term. For a practical case, an equation that needs introduction of a random element, the element has to be unpredictable in the POV of the case, not nessesarily anything else. Say the programmer of an algoritm to calculate a empirical probability could as well have programmed the random number generator as well and be able to predict all numbers generated, but that wouldn't matter since in the result the effect of randomness will be close to eliminated. IN some cases the same random number generator might be flawed, producing unexpected results, simply due to that it is not random towards a certain aspect of the algoritm.

ex.
an algoritm producing 10101010101010101... would still be random to
lim x->+infinity (S(n=1 to x)R(n))/n
but not to
lim x->+infinity (S(n=1 to x)R(2n))/2n

usually you introduce more complexity into the random number generator for it to be appliable for most cases, but it doesn't eliminate the system behind it, and in some cases the algoritm would give flawed results due to interference with the guts of the random number generator.

You seem to have some misgivings about so called random processes and statistical mathematics which I do not understand.

No, you have misunderstood me. I only want to point out the subjectivity of randomness, and that it is based on unpredictability.

The mathematics of statistics and probability theory are as well founded as the mathematics of differential equations. If you quarrel with the mathematics, you are attacking formal logic, which is behind almost every mathematical discipline.

I don't qwestion their practical use.

It is known that certain measurable phenomena are accurately modeled by the mathematics of statistics and probability. If you want to argue that the phenomena are illusions, that is a philosophical issue.

That is correct, but I don't argue for no reason at all, you mentioned pseudo random and chaos, and in practice you enter the philosophical issue in terms of subjectivity.

If you want to argue that the mathematics does a bad job of modeling the phenomena, you are wrong, or perhaps unwilling to accept some well established methods of logic and science.

I use and rely on math and logic all the time, more than most people do, and I value them high as tools, but I don't involve any blind faith in any of them.

If you want to claim that future developments will show that current beliefs are fundamentally flawed, you are being more subjective that the people (like me) who accept current science at face value.

Here you take one step further into a philosophical argument, I didn't intend to go into. You responded agressively last time I argued that a fact is a belief, and flaw refers to a incorrectness of information based on a objective reality for you while it refers to useless information, a very subjective concept, for me.

If I were unwilling to accept current science at face value, I would find it difficult to trust my computer, my auto, the bridges I cross, all of the gadgets of modern technology. My belief in science and disbelief in various forms of nonsense might be a very subjective view of the world, but it seems to work for me.

Anyways as said, I agree with you for the practical use of science.

[kedaman]

Simon

Originally posted by simonm
Guv
In terms of mathematics, I have heard such things as (some) irrational numbers being described as random because there is no formula that can predict the nth digit for any given n.

If an algoritm can generate a irrational number, say pi, then you can predict the n'th digit as well using a formula based on the algoritm.

Whereas true randomness, such as quantum randomness, seems to elude any attempt to impose patterns of behavior on it. It is random independant of any particular perspective used or terminology employed.

Would you agree on the equivalency of true (quantum) randomness and unpredictability? Is there anything specific you want to point out with "true" other than that nobody have found a pattern yet?

[simonm]

Kedaman

I put it to you that, what you call "subjective randomness" is not truly randomness attall but merely uncertainty based on a lack of information. Your definition carries with it the implicit assumption that there is always some underlying order.

I do not agree that there is any "equivalency" between unpredictability and randomness.

Is there anything specific you want to point out with "true" other than that nobody have found a pattern yet?

It is the assertion of (most) quantum physisists that there is an "irreducable" randomness in the behaviour of sub atomic particles. It is unpredictable, not because there they are unable to discern the underlying patterns, but becasue there are no underlying patterns to discern.

Imagine a quantum experiement whereby an electron might have a 50/50 chance of going one way or the other. In such a case, you cannot find any underlying "rules" that will tell you, in any indivual case, whether the electron will go either way. It is probabalistic, not because the observer doesn't have the information necessary to make such a judgement, but becasue there is no further information to discern.

If an algoritm can generate a irrational number, say pi, then you can predict the n'th digit as well using a formula based on the algoritm.

An iterative method of finding the nth digit of Pi does not make Pi finitely describable. A formular such that you put in n and the nth digit of Pi fell out the other end would be a finite way of describing Pi. Such a formula doesn't exist and therefore, mathematically, Pi is considered random.

[kedaman]

Simon

Originally posted by simonm
Kedaman
I put it to you that, what you call "subjective randomness" is not truly randomness attall but merely uncertainty based on a lack of information. Your definition carries with it the implicit assumption that there is always some underlying order.

I do not agree that there is any "equivalency" between unpredictability and randomness.

Then you disagree with me at a more fundamental level. More specifically what information is. I think there are basically two types of information, conscious and subconscious. If you apply this to a system which can't be described as "conscious" the information within the system is conscious while the information outside the system is unconsious. I am assuming that information is (1) elemental in nature and (2) unbound to external processes. In fact my world view doesn't contain any external processes, only pure reliable information. If that sounds unreasonable, I can explain any phenomena based on my world view as well, if you want.

Quantum randomness is in my eyes unconscious information, therefore unpredictable, and there is bound to be a pattern behind it as it is definitive elemental information.

It is the assertion of (most) quantum physisists that there is an "irreducable" randomness in the behaviour of sub atomic particles. It is unpredictable, not because there they are unable to discern the underlying patterns, but becasue there are no underlying patterns to discern.

I question the bold part, and the validity of the intuition those physisists use to conclude that information.

Imagine a quantum experiement whereby an electron might have a 50/50 chance of going one way or the other. In such a case, you cannot find any underlying "rules" that will tell you, in any indivual case, whether the electron will go either way. It is probabalistic, not because the observer doesn't have the information necessary to make such a judgement, but becasue there is no further information to discern.

I don't believe, and I think it is unreasonable that the phenomena (also information) can derive from "anything else" than information, QM doesn't explicitely mention what that "anything else" is and I would want to call that belief in the mystic that Guv once said. In other words "True" Randomness is equivalent to say something supernatural like magic.

An iterative method of finding the nth digit of Pi does not make Pi finitely describable. A formular such that you put in n and the nth digit of Pi fell out the other end would be a finite way of describing Pi. Such a formula doesn't exist and therefore, mathematically, Pi is considered random. [/B]

In practice it's possible to describe pi to the n'th digit, but not all digits since there isn't resources enough (say time, pens and paper) and more important, the need of all the digits. I have to disagree though, Pi is elemental information as well as all the digits, which is parts of my unconsious information.

[simonm]

Kedaman

In fact my world view doesn't contain any external processes, only pure reliable information. If that sounds unreasonable, I can explain any phenomena based on my world view as well, if you want.

Yes, I would like further explanation as I fail to understand the implications of it. But, it seems to me that this discussion is starting to get beyond the scope of the Maths forum so I have started a new thread here: http://www.vbforums.com/showthread.p...hreadid=107729

As for Pi though,

In practice it's possible to describe pi to the n'th digit, but not all digits since there isn't resources enough (say time, pens and paper) and more important, the need of all the digits. I have to disagree though, Pi is elemental information as well as all the digits, which is parts of my unconsious information.

The point is with Pi, you can't work out the nth digit of Pi without first working out all the preceeding digits of Pi. If you could work out the nth digit of Pi without first working out all those that preceed it, it would be considered finitely describable and consequantly, not random (in a mathematical sense).

I would appreciate a little support here from Guv as he could probably express this a little more soundly that I can. He would know what I'm talking about (I think)!

[kedaman]

Simon
funny, that you want Guv's confirmation on what you say
I don't think it is essential to know the preceding digits. The algoritms that approximates pi are naturally independent from any numbering system, so as a certain precision is met on the result, you can say for sure if the n'th digit in a numbering system with radix 10.

[simonm]

The algoritms that approximates pi are naturally independent from any numbering system, so as a certain precision is met on the result, you can say for sure if the n'th digit in a numbering system with radix 10.

You've summed it up. All we can do is make successive approximations at Pi and we cannot finitely describe it.

funny, that you want Guv's confirmation on what you say

I know, , but at the end of the day, I defer to Guv's superior understanding and articulation of mathematical concepts.

[kedaman]

Cannot finitely describe it?
Hmmm... The infinite predictable string of digits produced by such an algoritm is enough verification that it is not random. And if you want a better description on pi, the algoritm in a finite amount of steps describes pi as well, the diameter divided by the perimeter of a circle does that as well

[simonm]

And if you want a better description on pi, the algoritm in a finite amount of steps describes pi as well

The algorithm only achevies an approximations after a finite number of steps.

the diameter divided by the perimeter of a circle does that as well

True, but if you had a diametre of 6 cm, can you finitely describe the circumferance of that circle?

[Judd]

You can calculate the nth digit of Pi.


http://www.mathsoft.com/asolve/plouffe/plouffe.html

[simonm]

So someone has found a way of extracting the nth digit of Pi.

Whatever next?

It is interesting to note, however:

the formula allows us to do this if we agree to write numbers in base 16 rather than base 10. It's curious that a similar formula for base 10 is unknown.

Does this mean, then, that Pi does not yield an unpredictable sequence of numbers?

[kedaman]

I am surprised as well that it could be done that elegantly

Does this mean, then, that Pi does not yield an unpredictable sequence of numbers?

Suppose man had 16 fingers, or why not 4 or even 2, what would the standard numbering system look like then?

I want to express 1/3 in a finite number of digits, how do i do? I write in trinary: 0.1

Anyways i'm not at all sure if this is relevant, the approximation to n'th digit can be done in any base

[jim mcnamara]

It's interesting - none your posts discuss non-linear dynamics.
Fractals, dragons, and Julia sets. Oh my!

Turbulence, cloud formation and shapes, shorelines, watercourses - can all be modelled with these kinds of techniques. Modelled in the sense of generation. Not duplication.
Plus, you can't persist the data at midpoint in the generation process and get the same end result as working through with no persistence.

As of my last brush with Fractint, none of these processes were proved to be reversible; --backwardly reproducible. ie,. you can't work backwards from a known shape (iteration) and create the starting conditions for the generation process and prove that they were the starting conditions. In other words, you can't start with the finished product like a cloud and work backwards to a definitive, provable starting point at iteration 0.

If anything in mathematics verges into unpredictability, fractal generation leads the list. IMO. Randomness can be and is definable.

On the other hand - If one of a pair of infinitely close points on a complex plane is in the MSET: is it possible to prove that the other adjacent point is in or out of the Mandelbrot set? This has not been established. Peiter DeVries was working on a theorem that it is in fact unprovable. Interesting. Dunno if he published it or if he got a decent partial solution.

I believe it has been has established that there are uncountably many (Cantor's R) sets of points on either side (in/out pick one) adjacent to the MSET boundary, but no points that ARE on the boundary. In simple English - no boundary exists. I love it.

[jim mcnamara]

I meant to post this. This is code for A prng (pseudo-random number generator). There are loads of them.

Public  CurrentSeed as Integer

Sub randomize( Seed as Integer)  
          if Seed > 8191 then Seed = Seed Mod 8191
         CurrentSeed = Seed;
End Sub

Function rnd() as Integer 
   CurrentSeed = (CurrentSeed * 214013 )+ 2531011 
   CurrentSeed = (CurrentSeed and &H7FFF)
   rnd = CurrentSeed
End Function


usage:
Seed = somenumber
randomize(seed)
for i = 1 to 10
   debug.print rnd()
next

[blindlizard]

I find the best way to generate a true random number is to trim the seconds from the CPU clock

[MoMad]

Originally posted by blindlizard
I find the best way to generate a true random number is to trim the seconds from the CPU clock

And its faster (:thumbsup

[blindlizard]

.

[Destined Soul]

Egads, guys.. That was a little long.

Jim M. was right in that for complex systems, the outcome becomes random, for even slightly different initial conditions.

I think the best random number generators are ones that do thousands (or more!) of iterations to generate one number. Each iteration has enough "real-world randomness" (such as computer voltages, variance in the execution time for one iteration, etc) That way, even if the original seed was the same, the outcome SHOULD be different.

A decent example involving the triming of the seconds from the CPU clock is where you have multiple tasks/programs running at the same time as your program - as long as they can interfere with the running time with your program, your output should be (if done right) "random."

Ah.. I'm beginning to babble. Too many ideas, not enough ability to tell them.

Destined

[Guv]

It is astonishing that it is possible to determine the nth digit of Pi without calculating the preceding digits. Even after checking the article cited, I am not sure I believe it. I will lean toward belief , but not bet big money on it without further research. There have been hoaxes on the internet.

Random is a more subtle concept that you might imagine.

There is an interesting question about the probability of a random chord being longer than the side of an equilateral triangle inscribed in a sphere. It can be proven that the probability is 1/4, 1/3, or 1/4, which seems absurd. The apparent paradox is due to there being three random processes which can be used to generate a chord. The term random chord is ambiguous. In a similar sense, random number is an ambiguous term.

There are processes known (or believed) to be random. Radioactive decay, other quantum world phenomena, throwing dice, flipping coins, roulette, dealing cards, et cetera. If there are numbers associated with a random process, the numbers are called random numbers or random sequences.

It is not quite valid to talk about random numbers. It is the processes which are random.

A particular sequence of number generated by a random process might not seem to be random. It is possible to get a series of dice totals like 6, 7, 6, 7, 6, 7, 6, 7 which does not look random.

As previously posted, computer software generates pseudo random sequences of numbers that conform to various statistical tests. In general, the computer generated sequences are predictable.

It is important to know that there is no such thing as a universally applicable sequence of random numbers. The random processes differ in very fundamental properties, and therefore the numbers associated with them differ.

For noncritical applications, sampling the CPU clock might be reasonable, but I doubt that the resulting sequence of numbers could be considered random for any critical simulation of a real world random process.

Complex generators are not necessary, and are generally not desirable. The goal of a random number generator is the production of a sequence of numbers which pass some statistical test. If you want to simulate radioactive decay, the numbers must conform to Poisson statistics. For simulating roulette, you need a uniform distribution over a range of 38 numbers for an American wheel and a range of 0-36 for a European wheel.

If the generator is complex, it is difficult toverify that it produces numbers which will pass the required statistical tests.

When a mathematicians claims that the digits of Pi are random, he is using shorthand jargon for a statement like the following.

An analysis of 50,000 digits of Pi resulted in a 99% confidence level that Chi-Square statistics are applicable.

I am not sure, but I think that Chi-square analysis checks pairs/triplets of consecutive digits and verifies that no pair/triplet occurs more or less frequently than expected. I think this is a property of a uniform distribution, which is usually what is generated by computer algorithms. With only 20,000 digits, such an analysis might allow some triplets to be omitted and others to occur 3-4 times (Note that the average is two occurrences), while an omitted triplet for 50,000 (average 5) digits might drop the confidence level below 99%.