Physics 212, 2019: Lecture 19 - Revision history

Ilya at 13:06, 3 April 2019

2019-04-03T13:06:04Z

Ilya at 13:54, 1 April 2019

2019-04-01T13:54:47Z

Ilya at 13:30, 1 April 2019

2019-04-01T13:30:00Z

Ilya: Created page with "{{PHYS212-2019}} In today's lecture, we will study how to generate different types of random numbers using just a standard, uniformly distributed random number. If time permi..."

2019-04-01T13:29:34Z

Created page with "{{PHYS212-2019}} In today's lecture, we will study how to generate different types of random numbers using just a standard, uniformly distributed random number. If time permi..."

New page

{{PHYS212-2019}}

In today's lecture, we will study how to generate different types of random numbers using just a standard, uniformly distributed random number. If time permits, we will also study how random errors scale with the number of random trials.

==Different types of random numbers==
In the previous lecture, we discussed how a computer would generate pseudorandom floating point numbers, uniformly distributed between zero and one. How do we use these random numbers to generate other random number types?

===Uniform continuous random numbers===
The standard linear congruential generator allows us to generate a uniform pseudo-random floating point number between 0 and 1, called the ''standard'' uniform random number. How do we then generate a number between, say, <math>a</math> and <math>b</math>? For this, we only need to scale and shift the standard number. That is, if we say that <math>y=a + (b-a)*x</math>, where <math>x</math> is the standard uniform number, then <math>y</math> is the uniform random number between the two required limits.

===Multinomial random number===
A dice is an example of a multinomial random number with six equally probable outcomes. In general, a multinomial random variable is a random variable that can have a finite, discrete set of values, with a given probability of each of these values. We generate these random numbers by sub-dividing the interval between zero and one into subintervals. The number of the sub-intervals is equal to the number of possible outcomes of the multinomial variable, and the length of each sub-interval is equal to the probability of each outcome. We then generate a uniform floating point number between zero and one and check which of the sub-intervals it fell into. The index of the subinterval is then the generated multinomial number. See the code in the script uploaded for this module.

===Exponential random number===
Real-valued variables that have an exponential distribution are also very common. For example, the time between two subsequent nuclear decays, or the time between two nearby spikes in the simplest models of neuronal dynamics is exponentially distributed. Why is that? Nuclear decay has a finite probability <math>\rho dt</math> of happening in any interval of time <math>dt</math>. For the next event to happen at time <math>T</math>, it must not happen in all of the <math>T/dt</math> previous windows of the width <math>dt</math>, and then it should happen in the window <math>(T,T+dt)</math>. Combining this, we get <math>P(T,T+dt)=(1-\rho dt)^{T/dt}\rho dt\to e^{-\rho T}\rho dt</math>, so that the probability density is <math>P(T)=e^{-\rho T} \rho</math>. More generally, a random variable <math>x</math> is called exponentially distributed with the mean <math>x_0</math> if the probability density function for this variable obeys <math>P(x)=1/x_0 \exp(-x/x_0)</math>. The distribution with <math>x_0=1</math> is called the ''standard'' exponential distribution. Generation of exponential random numbers illustrates a few important properties of probability distributions. First of all, if we have an access to a standard exponential pseudo-random number, then by just multiplying it by <math>x_0</math> we will get the exponentially distributed number with a mean of <math>x_0</math>. This means that we only need to figure out how to generate standard numbers.

For this, let's go back to our definition of continuous random numbers as a limit of an ever-finer discretization of the real axis. Suppose we have a real valued variable <math>x</math>, which is distributed according to <math>P(x)</math>. This means that the probability of having a sample land in the interval <math>[x,x+\Delta x)</math> tends to <math>P(x)\Delta x</math>. Suppose now we have defined a new variable <math>y=y(x)</math>, or, alternatively, <math>x=x(y)</math>, where <math>x(y)</math> is the inverse function to <math>y(x)</math> (note that we are now assuming that such inverse exists!) Of course, <math>y</math> is also a random variable. How is it distributed? We note that the probability of a sample to land in our interval should not depend on whether we marked its end points as <math>[x,x+\Delta x)</math>, or as <math>[y(x),y(x+\Delta x))\approx [y(x),y(x) + dy/dx \Delta x)</math>. In other words, <math>P(x)|\Delta x|=P(y)|\Delta y|</math>, where we added the absolute value signs to ensure that, even if an interval is negative (read from right to left), the probability is still positive. This gives, in the limit of small <math>\Delta x</math>, <math>P(y) = P(x(y))\left|\frac{dx}{dy}\right|</math>.

How does this help with generating exponential numbers? Suppose that <math>x</math> is a standard uniform number, so that <math>P(x)=1</math>. Let's choose <math>y=-\log x</math>, and then <math>x= e^{-y}</math>. Then <math>P(y)=P(x(y))\left|\frac{d e^{-y}}{dy}\right|=e^{-y}</math>. In other words, the variable <math>y</math> is a pseudo-random standard exponential variable! So generating samples of such random variables is easy -- just generate standard uniform pseudo-random variables and take the negative log of them. The script that goes with this module shows that built-in functions for generation of exponential random samples (''nprnd.exponential()'') generate output that is indistinguishable from our approach of taking the negative log.

===Uniform random number in a square===
I hope you see that this is easy -- just generate a random <math>x</math> and a random <math>y</math> coordinates using the uniform pseudo-random number, and the job is done.

==Your work==
===Uniform random number in a circle===
Let's suppose we need a uniform random number in a circle around <math>(0,0)</math> with a radius of 1. '''You work: of the following methods that might seem to generate such a random number in a circle, choose the one that you think will be the most accurate and the fastest and implement it. Or create your own method and implement it. Generate a 1000 such random points and plot them. Do you see what you expected to see?'''

;Random angle / random scale: Generate a random pair <math>(x,y)</math> between -1 and 1. The pair defines a ray from zero to this point. Now generate a random distance between 0 and 1, and then scale the point to be this random distance from zero on the ray.

;Random radius / random angle: Generate a random angle between 0 and <math>2\pi</math> and a random radius between 0 and 1. The point will be at this angle and this radius.

;Random radius-squared / random angle: Generate a random angle between 0 and <math>2\pi</math> and a random radius-squared between 0 and 1. Take a square root of the second number to get the random radius. The point will be at this angle and this radius.

;Rejection method: Generate a random pair <math>(x,y)</math> between -1 and 1. Verify that the pair landed within a circle. Reject it if it's outside and accept otherwise. Note that you will need to generate more than <math>N</math> such random pairs to generate <math>N</math> points inside the circle.

Once you do these, you will see that some of these methods will generate too many points at the center of the circle compared to the edges. Those of you who know multivariate calculus should extend the calculation we did for generation of exponential random numbers to the multivariate case and relate the higher density of points near the center of the circle to the Jacobian of the transformation we make when we generate such two-dimensional random numbers from uniform standard numbers.

The notebook uploaded with this module demonstrate these methods. Which one of the ones that work would be the fastest? Why? Verify your guess yourself and explain what you see.

===Gaussian random variables===
A Gaussian (or normal) random variable is a variable with the probability density function <math>P(x) = \frac{1}{\sqrt{2\pi\sigma^2}}\exp \left[-\frac{(x-\mu)^2}{2\sigma^2}\right]</math>. <math>\mu</math> is called the mean, and <math>\sigma</math> is called the standard deviation. This is the familiar bell-shaped distribution centered around <math>\mu</math> with the width of </math>\sigma</math>. The standard normal distribution has <math>\mu=0</math> and <\math>\sigma^2=1</math>. Clearly, if one can generate a standard normal random variable, one can get a more general normal variable from it by multiplying by <math>\sigma</math> and shifting by <math>\mu</math>. So we only need to figure out how to generate a standard normal variable.

While we will skip the details, the generation of a random variable on a circle hints how to generate such standard random variables easily. First, imagine that I generate not one, but a pair of standard random normal variables <math>(x,y)</math>. Then <math>r^2=x^2+y^2</math>, and <math>P(x,y)= \frac{1}{2\pi}\exp \left(-\frac{x^2+y^2}{2}\right)=\frac{1}{2\pi}\exp \left(-\frac{r^2}{2}\right)</math>. Thus the radius-squared is exponentially distributed. So maybe if one should generate a random angle <math>\phi</math> between 0 and <math>2\pi</math> and a random exponentially distributed variable, which one views as <math>r^2</math>. Then taking it's square root and choosing <math>x=\sqrt{r^2}\cos \phi</math> and <math>y=\sqrt{r^2}\sin \phi</math> generates a pair of random standard normal samples. The code uploaded with this module compares this method against the built-in ''nprnd.randn()'' function provided by Python for generation of Gaussian numbers.

==Uses of random numbers==
We use random numbers to perform computations that are fundamentally random, and we will focus on those in the upcoming weeks. However, there are computations that are fundamentally deterministic, but may be easier to perform with random numbers. Suppose we want to calculate an integral under a curve <math>y=y(x)</math>, with the limits <math>x\in [a,b]</math>. We can, of course, do it analytically for some functions <math>y</math> or numerically by subdividing the interval of <math>x</math> into small segments <math>\Delta x</math> and adding up the areas of all small rectangles, <math>y(x)\times \Delta x</math>. An alternative way is as follows. Suppose we know that <math>y(x)</math> is positive and smaller than <math>f_{\rm max}</math>. Then the area under the curve can be written down as <math>(b-a)f_{\rm max}*\alpha</math>, where <math>\alpha</math> is the fraction of the square <math>b-a</math> by <math>f_{\rm max}</math> that is actually under the curve. How do we estimate this fraction? Suppose I generate random points (dart throws), uniformly distributed over the square <math>b-a</math> by <math>f_{\rm max}</math>. The fraction of those that end up under the curve (and it's easy to check which one does!) is an estimate of <math>\alpha</math>. The provided script performs such calculation for an arbitrary <math>y=y(x)</math>. This is called Monte-Carlo integration. Note that our implementation is incomplete -- we don't check if the function ever is below 0 or ever is above <math>f_{\rm max}</math>, which a better implementation should do.

A problem, of course, is that such calculation is probabilistic -- every time we perform it, the results are different. But how different? We can verify, first of all, that our probabilistic estimate of the area converges to to true one, where true is known, e.g, when we integrate a function <math>x^2</math>. We can also show the distribution of the estimates of the area when we perform the are estimate with <math>N</math> dart throws. We see that the larger <math>N</math> is, the more concentrated the estimates are. To quantify this, we use the provided script to calculate the standard deviation of the estimates as a function of <math>N</math>. We find that <math>\sigma^2 = A/N</math>, where <math>A</math> is some constant. The claim is that the general <math>1/N</math> law holds true for essentially any function being integrated. It's only the constant that changes -- and we can verify this by integrating other functions.

@@ Line 44: / Line 44: @@
 While we will skip the details, the generation of a random variable on a circle hints how to generate such standard random variables easily. First, imagine that I generate not one, but a pair of standard random normal variables <math>(x,y)</math>. Then <math>r^2=x^2+y^2</math>, and <math>P(x,y)=  \frac{1}{2\pi}\exp \left(-\frac{x^2+y^2}{2}\right)=\frac{1}{2\pi}\exp \left(-\frac{r^2}{2}\right)</math>. Thus the radius-squared is exponentially distributed. So maybe if one should generate a random angle <math>\phi</math> between 0 and <math>2\pi</math> and a random exponentially distributed variable, which one views as <math>r^2</math>. Then taking it's square root and choosing <math>x=\sqrt{r^2}\cos \phi</math> and <math>y=\sqrt{r^2}\sin \phi</math> generates a pair of random standard normal samples. The code uploaded with this module compares this method against the built-in ''nprnd.randn()'' function provided by Python for generation of Gaussian numbers.
 ==Scripts==
 [[media:RandomNumbers.txt | Random Numbers]] -- the Random Numbers notebook, which we will be exploring over multiple lectures.

@@ Line 2: / Line 2: @@
 In today's lecture, we will study how to generate different types of random numbers using just a standard, uniformly distributed random number. If time permits, we will also study how random errors scale with the number of random trials.
 ==Different types of random numbers==
@@ Line 47: / Line 49: @@
 A problem, of course, is that such calculation is probabilistic -- every time we perform it, the results are different. But how different? We can verify, first of all, that our probabilistic estimate of the area converges to to true one, where true is known, e.g, when we integrate a function <math>x^2</math>. We can also show the distribution of the estimates of the area when we perform the are estimate with <math>N</math> dart throws. We see that the larger <math>N</math> is, the more concentrated the estimates are. To quantify this, we use the provided script to calculate the standard deviation of the estimates as a function of <math>N</math>. We find that <math>\sigma^2 = A/N</math>, where <math>A</math> is some constant. The claim is that the general <math>1/N</math> law holds true for essentially any function being integrated. It's only the constant that changes -- and we can verify this by integrating other functions.

@@ Line 38: / Line 38: @@
 The notebook uploaded with this module demonstrate these methods. Which one of the ones that work would be the fastest? Why? Verify your guess yourself and explain what you see.
-===Gaussian random variables===
+==Gaussian random variables==
 A Gaussian (or normal) random variable is a variable with the probability density function <math>P(x) = \frac{1}{\sqrt{2\pi\sigma^2}}\exp \left[-\frac{(x-\mu)^2}{2\sigma^2}\right]</math>. <math>\mu</math> is called the mean, and <math>\sigma</math> is called the standard deviation. This is the familiar bell-shaped distribution centered around <math>\mu</math> with the width of </math>\sigma</math>. The standard normal distribution has <math>\mu=0</math> and <\math>\sigma^2=1</math>. Clearly, if one can generate a standard normal random variable, one can get a more general normal variable from it by multiplying by <math>\sigma</math> and shifting by <math>\mu</math>. So we only need to figure out how to generate a standard normal variable.