35

I tried some usual google search etc. but most of the answers I find are either somewhat ambiguous or language/library specific such as Python or C++ stdlib.h etc. I am looking for a language agnostic, mathematical answer, not the specifics of a library.

As an example, many say that the seed is a starting point of random number generator and the same seed always produces the same random number. What does it mean? Does it mean the output number is a deterministic function of a specific seed, and the randomness comes from the value of the seed? But if that is the case, then by supplying the seed, are not we, the programmers, creating the randomness instead of letting the machine do it?

Also, what does a starting point mean in this context? Is this a non-rigorous way of saying an element $x\in\mathfrak{X}$ of the domain of a map $f:\mathfrak{X}\rightarrow\mathfrak{Y}$? Or am I getting something wrong?

amoeba
  • 93,463
  • 28
  • 275
  • 317
Della
  • 453
  • 1
  • 4
  • 6
  • 7
    I don't feel qualified to write an answer, but you might find the Wikipedia article on the [Mersenne Twister](https://en.wikipedia.org/wiki/Mersenne_Twister) enlightening, especially the [section on initialization](https://en.wikipedia.org/wiki/Mersenne_Twister#Initialization). In short, a pseudorandom number generator like the Mersenne Twister will eventually repeat its output. In the case of the MT the period has length `2^19937 − 1`. The seed is the point of this extremely long sequence where the generator starts. So yes, it is deterministic. – IonicSolutions Jul 04 '18 at 05:26
  • 3
    A pseudo-random number generator is an endlessly repeating fixed list of numbers. Where does it start? *You get to say.* – whuber Jul 04 '18 at 10:44
  • 2
    @whuber I actually think your comment would be a great answer. – David Z Jul 04 '18 at 21:19

3 Answers3

35

Most pseudo-random number generators (PRNGs) are build on algorithms involving some kind of recursive method starting from a base value that is determined by an input called the "seed". The default PRNG in most statistical software (R, Python, Stata, etc.) is the Mersenne Twister algorithm MT19937, which is set out in Matsumoto and Nishimura (1998). This is a complicated algorithm, so it would be best to read the paper on it if you want to know how it works in detail. In this particular algorithm, there is a recurrence relation of degree $n$, and your input seed is an initial set of vectors $\mathbf{x}_0, \mathbf{x}_1, ..., \mathbf{x}_{n-1}$. The algorithm uses a linear recurrence relation that generates:

$$\mathbf{x}_{n+k} = f(\mathbf{x}_k, \mathbf{x}_{k+1}, \mathbf{x}_{k+m}, r, \mathbf{A}),$$

where $1 \leqslant m \leqslant n$ and $r$ and $\mathbf{A}$ are objects that can be specified as parameters in the algorithm. Since the seed gives the initial set of vectors (and given other fixed parameters for the algorithm), the series of pseudo-random numbers generated by the algorithm is fixed. If you change the seed then you change the initial vectors, which changes the pseudo-random numbers generated by the algorithm. This is, of course, the function of the seed.

Now, it is important to note that this is just one example, using the MT19937 algorithm. There are many PRNGs that can be used in statistical software, and they each involve different recursive methods, and so the seed means a different thing (in technical terms) in each of them. You can find a library of PRNGs for R in this documentation, which lists the available algorithms and the papers that describe these algorithms.

The purpose of the seed is to allow the user to "lock" the pseudo-random number generator, to allow replicable analysis. Some analysts like to set the seed using a true random-number generator (TRNG) which uses hardware inputs to generate an initial seed number, and then report this as a locked number. If the seed is set and reported by the original user then an auditor can repeat the analysis and obtain the same sequence of pseudo-random numbers as the original user. If the seed is not set then the algorithm will usually use some kind of default seed (e.g., from the system clock), and it will generally not be possible to replicate the randomisation.

Ben
  • 91,027
  • 3
  • 150
  • 376
  • +1. It would be good to add what (usually) happens if one does not explicitly provide the seed. – amoeba Jul 04 '18 at 12:40
  • 1
    @amoeba: The 4th paragraph of my Answer, discusses this briefly. – BruceET Jul 04 '18 at 15:35
  • 1
    While this answers the basics of the question.it does not touch the fact why we need this in simulations. It is very hard to produce TRUE randomness - and when you have that you can not reproduce the original answer! Enter the PNRG... with all its problems. – Paul Palmpje Jul 04 '18 at 21:18
  • @amoeba: As requested, I have added an additional paragraph to flesh this out. – Ben Jul 06 '18 at 04:33
  • 1
    Thanks. "Default seed" sounds a bit like it's always the same default value of seed; what I meant is that usually the seed is taken from the system clock. This I think is good to know. – amoeba Jul 06 '18 at 20:54
  • Edited further to specify this. – Ben Jul 07 '18 at 00:03
  • Some generators do not provide all of x_i to the user, e.g. a part of x_i may be a counter. – Joachim Wagner Dec 28 '21 at 15:24
  • The x_i may not directly align to the numbers returned, e.g. x_i may have 64 bit each but double-precision floats in 0-1 range only need 52 bit, allowing 16 numbers to be produced from x_1, ..., x_13 (52/64 = 13/16). – Joachim Wagner Dec 28 '21 at 15:29
19

First, there is no true randomness in today's computer-generated "random numbers." All pseudorandom generators use deterministic methods. (Possibly, quantum computers will change that.)

The difficult task is to contrive algorithms that produce output that cannot meaningfully be distinguished from data coming from a truly random source.

You are right that setting a seed starts you at a particular known starting point in a long list of pseudorandom numbers. For the generators implemented in R, Python, and so on, the list is hugely long. Long enough that not even the largest feasible simulation project will exceed the 'period' of the generator so that values begin to re-cycle.

In many ordinary applications, people do not set a seed. Then an unpredictable seed is picked automatically (for example, from the microseconds on the operating system clock). Pseudorandom generators in general use have been subjected to batteries of tests, largely consisting of problems that have proved to be difficult to simulate with earlier unsatisfactory generators.

Usually, the output of a generator consists of values that are not, for practical purposes, distinguishable from numbers chosen truly at random form the uniform distribution on $(0,1).$ Then those pseudorandom numbers are manipulated to match what one would get sampling at random from other distributions such as binomial, Poisson, normal, exponential, etc.

One test of a generator is to see if its successive pairs in 'observations' simulated as $\mathsf{Unif}(0,1)$ actually look like they are filling the unit square at random. (Done twice below.) The slightly marbled look is a result of inherent variability. It would be very suspicious to get a plot that looked perfectly uniformly grey. [At some resolutions, there may be a regular moire pattern; please change the magnification up or down to get rid of that bogus effect if it occurs.]

set.seed(1776);  m = 50000
par(mfrow=c(1,2))
  u = runif(m);  plot(u[1:(m-1)], u[2:m], pch=".")
  u = runif(m);  plot(u[1:(m-1)], u[2:m], pch=".")
par(mfrow=c(1,1))

enter image description here

It is sometimes useful to set a seed. Some such uses are as follows:

  1. When programming and debugging it is convenient to have predictable output. So many programmers put a set.seed statement at the start of a program until writing and debugging are done.

  2. When teaching about simulation. If I want to show students that I can simulate rolls of a fair die using the sample function in R, I could cheat, running many simulations, and picking the one that comes closest to a target theoretical value. But that would give an unrealistic impression of how simulation really works.

If I set a seed at the start, the simulation will get the same result every time. Students can proofread their copy of my program to make sure it gives the intended results. Then they can run their own simulations, either with their own seeds or by letting the program pick its own starting place.

For example, the probability of getting the total 10 when rolling two fair dice is $$3/36 = 1/12 = 0.08333333.$$ With a million 2-dice experiments I should get about two or three-place accuracy. The 95% margin of simulation error is about $$2\sqrt{(1/12)(11/12)/10^6} = 0.00055.$$

    set.seed(703);  m = 10^6
    s = replicate( m, sum(sample(1:6, 2, rep=T)) )
    mean(s == 10)
    [1] 0.083456         # aprx 1/12 = 0.0833
    2*sd(s == 10)/sqrt(m)
    [1] 0.0005531408     # aprx 95% marg of sim err.

  1. When sharing statistical analyses that involve simulation. Nowadays many statistical analyses involve some simulation, for example a permutation test or a Gibbs sampler. By showing the seed, you enable people who read the analysis to replicate the results exactly, if they wish.

  2. When writing academic articles involving randomization. Academic articles usually go through multiple rounds of peer review. A plot may use, e.g., randomly jittered points to reduce overplotting. If the analyses need to be slightly changed in response to reviewer comments, it is good if a particular unrelated jittering does not change between review rounds, which might be disconcerting to particularly nitpicky reviewers, so you set a seed before jittering.

George Hawkins
  • 103
  • 2
BruceET
  • 47,896
  • 2
  • 28
  • 76
  • 1
    So do you mean a pseudorandrom number generator basically stores a periodic sequence of random number (uniformly distributed in [0, 1]) and a seed is merely an index to the sequence? So does it mean the random number generated is a deterministic function of the seed? – Della Jul 04 '18 at 07:31
  • 11
    You don't need quantum computer to use quantum phenomena to have a random generator (https://en.wikipedia.org/wiki/Hardware_random_number_generator) – Guiroux Jul 04 '18 at 08:14
  • 2
    @Della. You have essentially the right idea. But please understand that in practice the 'period' has to be really huge. (No matter how large your simulation project, you don't want it to repeat.) For example, IonicSolutions comments after the Q that the Mersenne Twilster generator has period $2^{19937}-1,$ somewhat larger than I can easily visualize. // If you know the seed, you can produce the pseudorandom seq from there. // Generators have been used to encrypt messages. But standards for secure generators for encryption are different from standards for generators for probability simulation. – BruceET Jul 04 '18 at 18:56
  • 1
    @Guiroux. The possibility I was trying to mention re quantum computers was to have true random number generators as fast as today's pseudorandom generators. In the 1950s sources of 'true' random numbers were used for randomization in experimental design and for (slow, limited) prob simulations. Perhaps see [Million Random Digits](https://en.wikipedia.org/wiki/A_Million_Random_Digits_with_100,000_Normal_Deviates). – BruceET Jul 04 '18 at 19:09
  • 1
    @BruceET Albeit you can achieve a good (fast) middle ground by combining the two approaches - using the true random number generator as the seed to the pseudorandom generator which at least removes the possibility of an attacker determining the sequence by targeting knowledge of the seed. – JBentley Jul 05 '18 at 03:29
  • In the last millennium, I stumbled upon a seed for the Commodore 128/64 RND function that lead to a sequence of exactly six random numbers before the sequence repeated... (Commodore BASIC written by Microsoft) – DJohnM Jul 05 '18 at 05:01
1

TL;DR;

A seed usually enables you to reproduce the sequence of random numbers. In that sense they are not true random numbers but "pseudo random numbers", hence a PNR Generator (PNRG). These are a real help in real life!

A bit more detail:

Virtually all "random" number generators implemented in computer languages are pseudo random number generators. This is because given a starting value (===> the seed) they will always provide the same sequence of pseudo random results. A good generator will produce a sequence that can not be distinguished - in statistical terms - from a true random sequence (throw a true die, true coin, etc).

In many simulation cases you want to have a true "random" experience. However, you also want to be able to reproduce your results. Why? Well, at least regulators are interested in that peculiar thing.

There's a lot to dive in to. People even do analysis into the "best" random seed. In my opinion this invalidates their model as they can't handle "true" random behavior - or their PRNG is not fit for their implementation. Most of the time they just don't do enough simulations - but they take time.

Now imagine a "true" RNG. One could implement this based on a kind of randomness in the machine. If you only take a random seed (e.g. time now) you create kind of a random starting point but the randomness of the sequence still depends on the algorithm to determine the next numbers. This is more important than the starting point in most cases as the distribution of results determines the actual "result". If your sequence should be truly random, how would you implement this? Clock ticks of a computer can be said to be deterministic and otherwise probably will show a lot of auto-correlation. So what can you do? The best bet so-far is to implement a solid PNRG.

Quantum Computing? I'm not sure that will fix it.

Paul Palmpje
  • 111
  • 2