Algorithm to generate random numbers with constraints ?

Question

I don't understand the concept of generating random variables with constraints from Monte Carlo Methods. Can some one explain in simple language the concept behind it ?

Answer 1

The generation of random numbers is a very interesting part of computer science. After all, a program is deterministic, and it seems that generating random numbers is outside of a computer's reach.

There are a few simple ways to generate random numbers. A famous example is the middle-square method.

Choose a number $x_0$ (often from the current system time). Then define the sequence $x_n$ such that $x_i$ is the concatenated middle digits of the square of $x_{i-1}$.

As an example for this method, choose $x_0=53033$. This number is called the seed. With our example, we can calculate the next values of the sequence:

$$x_0=53033$$ $$x_0^2=281\textbf{24990}89$$ $$x_1=24990$$ $$x_1^2=62\textbf{45001}00$$ $$x_2=45001$$ $$\cdots$$

Seems pretty random to me. However, notice that this sequence is deterministic. If you were given the starting value, you could always find all the subsequent values. Plus, eventually we will get a value that we've seen before, and the sequence will wrap around. A quick Python program shows that this will take $20$ steps:

https://scicomp.stackexchange.com/questions/14237/calculating-periodicity-of-a-pseudo-random-number-generator-middle-square-metho

Since this is "somewhat" random but not truly random, programmers call such a generator pseudo-random.

Although these "pseudo-random" numbers may seem a little disingenuous, don't fret! Given large enough seeds they are quite random, sufficently so for most Monte-Carlo type analysis. Plus, if you have a determined "seed", you can recreate the same Monte-Carlo distribution by simply choosing the same seed. If you want to learn more about common pseudorandom number generators, one is the Mersenne Twister.

You also asked how generating the variables with constraints is done. A program such as the middle-square method, as shown, produces "random" values in the range $0<x_n<99999$.

Suppose, instead, we want a continuous variable $0<k_n<1$ for our Monte-Carlo distribution. Well, we could simply divide $x_n$ by $100000$ and have a pretty good approximation! Thus, when we are generating random variables with constraints, we typically use such methods to reduce a certain random number generator into our desired constraints.

Many programming languages already have built-in functions for this. For example, Python's random module has the functions "seed", which initializes the sequence to a specific value, "randrange", which finds a random integer in a range, and "random", which gives a random floating-point number in the range $[0,1)$, among many others.