I know that most of you came from my video about Dream, and thanks so much for the overwhelming
support, but this video will be a continuation of the series I’ve started before that,
so if you haven’t watched it, please do, but here is a quick recap. Throughout the series,
we will be looking at the average distance between any two points in a unit disc. Even though I
already said that it is 128/45pi, we of course want to know how we came up with the answer.
By defining the terms probability density and average of a function more precisely, we find that
the question is basically evaluating either of these two quadruple integrals. Don’t worry, we are
not going to do that directly, and in this video we are going to do a numerical simulation instead.
We randomly sample a pair of points, then calculate the distance between them.
Repeat this, say 1000 times, and then we take the average of these distances,
but now there are two questions: (1) how do we sample the points? And once
we have sampled them, (2) how do we calculate the distance? Let’s focus on the first one for now.
Since there is circular symmetry involved, it is natural to introduce polar coordinates to
our picture. So to specify a point, we need to generate two pieces of information: r,
the distance from the origin, ranging from 0 to 1; and theta, the polar angle, ranging from 0
to 2 pi radians. So to sample a point, we simply select the value of r from 0 to 1 at random, and
theta from 0 to 2 pi at random. Let’s say we have chosen the values r_1 and theta_1 respectively;
And repeat this to choose a second point. Then from the law of cosines, we can calculate the
distance using the formula. So we are ready to perform a numerical simulation - there is a
spreadsheet in the description for this. And… we get this average from the numerical simulation!
The exact answer should be 128/45 pi, which is around 0.9054, but that is quite far away from
the answer we obtained. It is *theoretically* possible that we just happened to pick pairs
of points close together, but we need to have incredible “luck” to lower the average
that much. We are going to calculate this “luck” later on in the video, but anyway, that means
either (1) this exact answer is wrong, or (2) we have done something wrong in our simulation.
It is very clear which one it is when we plot the points that we just randomly picked.
The points are more concentrated near the origin than towards the rim of the circle,
and so the simulation has gone wrong somewhere. The reason is that when we randomly generate
a number for r, half of the time it returns something less than 1/2. However, for the disc,
the inner half only occupies an area of pi / 4, and the area of the whole disc is pi,
and so the ratio is a quarter, or equivalently, we should only have
a quarter chance of picking r to be less than 1/2. But how do we address this discrepancy?
Let’s denote X as the value of r IF we simulated correctly; and Y as the value of r generated
by the computer. As discussed before, the probability that X is less than 1/2 is a quarter,
and that Y is less than 1/2 is 1/2. More generally, the probability that X is less than r
is the area of this inner disc, pi r^2, divided by that of the whole disc pi, so the probability of X
less than r is r^2. And if we again consider the same probability but for Y,
it will be the proportion of the smaller interval, which is simply r. Here, r can be anything really,
so as long as we put the same numbers here, this equality still holds. We want this probability to
be r^2, because it will then match the probability for X. To do that, we can simply change this r to
be r^2, so that we have the same numbers in the two boxes. So now, we have this equality.
However, saying that Y is less than r^2 is the same as saying square root of Y is less than r,
because everything here is nonnegative. Comparing these two statements, since they are true for all
values of r, X and sqrt(Y) have exactly the same distribution. Intuitively speaking, if I have two
computers generating X and sqrt(Y) respectively, nothing can tell the difference. X is what we
want, while sqrt(Y) is what we can do, but since there isn’t any difference, we can use sqrt(Y)
to model X. In other words, we use the normal computer-generated value, then square root it.
So in the numerical simulation, for r1 and r2, we generate a random number then square root it. What
about theta_1 and theta_2? Do we need to do anything to it? No. If we similarly denote X to be
the correctly simulated value of theta, and Y the value of theta just from random number generators,
the probability of X less than theta is the proportion of the area of the sector,
which is theta / 2pi; and for Y, the probability is the proportion of the length of the interval,
which is also theta / 2pi. So X and Y are already the same in distribution. That means,
we need the square root adjustment for r’s, and nothing for theta’s. If we really run this,
the approximation is much closer to the exact answer.
More generally, if the probability that X is less than x is some function F(x),
we can similarly consider the probability that Y is less than F(x), which is again F(x).
This time, we apply the inverse of F on both sides, so we have F^(-1)(Y) smaller than x. Again,
comparing these two statements, X and F^(-1)(Y) are the same in distribution.
In the previous example, F(x) is x^2, and so F^(-1) is simply the square root. In practice,
we sample Y from a built-in random number generator, then transform it using F^(-1),
which is why this technique is known as inverse transform sampling. The good thing is that X can
be anything you want, so you can simulate ANY distribution. But this technique is only useful
if F^(-1) is easy to calculate. For example, if you want to simulate the normal distribution,
F is already pretty complicated, let alone F^(-1). In those cases, it’s
better to use other methods like the Box-Muller transform, which isn’t the focus of the video.
That’s all well and good, but let’s say we don’t really know this exact value.
Of course the numerical answer should be close to the exact answer, but how close?
What I am about to say is the big picture, otherwise the video will
be unbearably long. There will be links in the description for more of these details.
In the numerical simulation, we have this distribution of the distances. In particular,
we want to find the standard deviation, a sort-of-average deviation from the average,
or mean in statistical terms. If the standard deviation we calculated is s_N, then our estimate
of the actual standard deviation is s, which is s_N, but adding a correction factor in front.
It is possible to have picked points very close or far away from each other, but these
extremes should cancel out when we consider the average. So the average should behave nicely.
Indeed, by the Central Limit Theorem, if the actual mean is mu, and actual standard deviation
is sigma, then the average of the samples taken should approach normal distribution with mean mu
and standard deviation sigma/sqrt(n), where n is the number of samples taken. So graphically, this
is how the sample mean should be distributed, with mean mu, and standard deviation sigma/sqrt(n).
Equivalently, if we consider sample mean minus mu, we only shift everything by mu,
and so the peak moves to 0 but everything else stays unchanged. It is entirely reasonable that
the difference between sample mean and mu ends up here, but it’s extremely unlikely for them to be
that far apart. So we can be reasonably sure that the difference is somewhere here.
More precisely, the probability that the difference is here is the area of the region,
so if the area is 0.99, then we are 99% sure the difference ends up somewhere here,
so this interval is known as 99% confidence interval. All this is to say that not only
can we approximate the average, we can also in a way approximate the maximum error. But there
is a caveat. In the Central Limit Theorem, we need to have the actual standard deviation,
but we can only *estimate* with this correction factor. So to be more accurate,
we should use the t-distribution with (n-1) degrees of freedom, but if n is very large,
there isn’t any difference with using normal distribution anyway.
Now in the first half of the video, I said we would calculate the so-called “luck” that
we get the average that low if there is nothing wrong with our simulation nor the exact answer.
The above discussion works here as well, but this time
the difference is really really large. We can calculate the probability that it is
at least that extreme, and it turns out to be in the order of 10^(-39), or if you want, 1 in 141
undecillion, 141 followed by 36 0’s, which is so low that it is much more reasonable to conclude
that one of these is wrong. What I have just described briefly is called a single-sample
t-test, and as said before, there are links in the description if you want to learn more.
The next video will be a concept called the Jacobian. This will be the prerequisite for
the final video finally explaining how to solve this problem exactly. However,
I am sorry that it will take a long time for the next upload,
but hopefully it should be worth the wait. If you enjoyed this video, please click the like button,
subscribe with notifications on, as well as commenting on it. See you next time!