Random Number Generators

Function that generates uniformly-distributed random numbers.

Remember — RNG functions implemented as computer programs aren’t truly random, only pseudo random. All computers are deterministic (same input always gives the same output).

Example: Why?

This is the lead-up to Monte Carlo algorithms; which are algorithms which use probability to solve complex problems.

If you get into algorithmics, you’ll find out this is very important. (e.g., search/optimization problems like traveling salesman are insanely difficult to do precisely, but imprecise solutions (introducing probability) can drastically speed things up.)

Aside — Chaotic Functions: Tiny changes in the input generate unpredictable changes in the output.
Chaotic functions can be deterministic, so don’t mix it up!

Example: Background

UNIX uses this pseudo RNG:

x_0 = \text{seed} \\ y = x_{n+1} = (Ax_n + B) \mod 2^{31}

You usually want to pick an A and B that are coprime (they don’t share any common factors), because TODO.

Note — Professor recommends using Random.org for randomness, because they tap into real physical processes for their randomness.

Monte Carlo Integration

Problem: Compute the integral.

Example: Derivation of Monte Carlo Integration

We previously approximated the integral using [\frac{(f(a) + f(b))(b-a)]}{2}

The whole point of f(a) + f(b) is to poorly estimate the height.

Instead, we can TODO ??? use random points somehow ??? TODO; which changes the approximation to

\frac{(\sum_i^n f(x_i)}{n}(b-a)

Aside — Randomness
It is SUPER important that you select these points (TODO which points?) random. Otherwise, you are introducing bias.
Remember — Every time you use bias, there is a way to fool the selection method you use.

Now, we increase accuracy by increasing the number of points, rather than increasing the number of trapezoids, which is less work.

Example: Problem

f(x) = x^2 + 3 + 1, \quad a=1, \quad b=2

Here are the random numbers we’ll use:

Note — We just generated this numbers with Random.org, by adding one to the floating points it gave us, to get it in range.

\int_1^2 f(x) dx = 8.75132501248

TODO then, written below was 7.8\overline{3}, why???

You’ll find out this is worse than Richardson’s for this simple problem. But, multi-variable ??? functions benefit greatly.

=== Professor now began talking about 3D area under a shape? ===

If you do this like the trapezoid problem, you’ll be doing a crapton more work computing tons of little prisms.

If you do this with Monte Carlo, the work stays the same.