The exponential function can be written in this infinite series. But if we were to actually
compute the exponential function, we can’t really add up an infinite number of terms.
Instead, we have to stop computing the terms somewhere, and ignore the terms later on in
the series, hoping that all the terms thereafter are so small that it doesn’t really affect
the result much. However, where should we stop in this series? How many terms do we
really need? Now this question is still a bit vague, so let’s say we want the terms
we computed to be like 99% of the answer, and the terms we ignored occupy only 1% of
the answer. You can of course not be satisfied with just 99% accuracy, but for now, let’s
just settle for 99%. So our problem is when will we have 99% of the answer when adding
the terms in this series? In this video, we focus on the case when x is a very large integer.
We could start investigating by constructing some sort of histogram. For example, the 0th
term is represented by the leftmost bar, which would have the value of 1, or x^0 / 0!. In
general, we want to draw the kth term in the series for the histogram. If we in addition
make the width of each bar to be 1, then the area of each bar is x^k / k!. So if we add
up all the areas of the bars, the total area is e^x. The histogram shows roughly where
we should stop computing: for the terms on the far right, the contribution is negligible,
and we could just stop around here. However, if we insist on this being the height of each
bar, without any normalisation, then by increasing the value of x, there is going to be a huge
problem. As we increase x, the bars quickly go beyond the scale, and we could not really
see a lot.
Okay, so we go back to the original histogram, and now just scale everything so that the
highest bar is capped here. What will happen as we crank up the value of x? Well now we
have run into another problem - the peak moves and we can’t see very well again. Well ok,
let’s go back to the original histogram again, and try to not only limit the height,
but also scale the width of the bars on screen to fix the peak of the histogram. Surely this
will work now as we increase the value of x. And it does work. But have you noticed
the pattern as x grows? This is now a bell curve, which is the characteristic of a normal
distribution. Hang on, what is normal distribution doing here? Let’s see how.
We now go back to this original problem. We want the terms we computed to occupy the vast
majority of the answer. One approach is to see the proportion that each term contributes
to the series. For the kth term in the series, the proportional contribution is x^k / k!
out of the full e^x. This can be written as e^(-x) x^k / k!. Does this expression look
familiar? If you watched my previous video, you will notice that these terms form the
Poisson distribution. It is used to describe the probability that if on average there is
a rate of lambda customers coming in, where the customer arrivals are independent from
each other, then the probability of exactly k customers is e^(-lambda)*lambda^k/k!. From
the connection with the Poisson distribution, we can rephrase our problem as when we consider
the possibility of more and more customers coming in, at which point would the cumulative
probability be larger than 99%. Because of the connection with probability, the previous
observation of the bell curve or normal distribution might make you scream: CENTRAL LIMIT THEOREM!!!
Yes, that’s related, but we have to be careful in *how* it’s related.
The statement of the central limit theorem is that if we have n independent copies of
the same random variable, all with the same mean mu and variance sigma^2, then there is
this statement, which means that we first consider the difference between the empirical
average and the theoretical average. After we scale the difference by multiplying by
sqrt n, then for large n, this scaled difference follows a normal distribution. But let’s
forget the final result for a minute. If we want to use the central limit theorem, we
have to first create these copies. How can we do it? What we have is just 1 Poisson variable
that follows the Poisson distribution. However, if the probabilities correspond to the arrival
process of customers at a rate of lambda, it is possible to split it up into several
independent ones, and as long as the arrival rates sum to lambda, the total number of customers
in the system would have the same distribution as the original unsplit one.
Another way to look at it is that let’s say we have customers arriving at a large
store at a rate of n per hour, with n being an integer. An alternative way that this can
be achieved is that there are n different departments in the store, and the customers
arrive at each department at a rate of 1 per hour. If we denote X as the total number of
customers going into the store in an hour, then X follows that Poisson distribution with
rate n, giving probabilities e^(-n) * n^k / k!. And if we denote X_i as the number of
customers arriving at the ith department in an hour, then these X_i’s will also follow
the Poisson distribution, but with rate 1, giving the probabilities as e^(-1) * 1^k / k!.
Now the argument that we can split this up into n different arrival processes means that
the X and the (sum of) X_i’s have the same distribution. In other words, the probability
that X equals a certain number m is the same as the sum of these X_i’s attaining m.
This argument is quite intuitive, but might not be completely convincing to some people,
and that’s completely understandable. After all, these two situations are not entirely
equivalent. We can prove this more precisely. More generally, if we have two Poisson processes
with rates lambda and mu respectively, and denote X and Y to be the number of customers
for the respective processes. Then the probability that the sum of these two being n can be computed
by summing all the possibilities of X and Y. If one of them is i, then in order for
the sum to be n, the other process has (n - i) customers coming in. The next step is
to substitute the Poisson distribution formulas for X and Y, and then try to sum these up.
The penultimate step involves just a little rearranging the expression inside the summation.
The exponential parts get combined together, and we add one n! in the numerator and one
in the denominator. And then finally, we can use the binomial theorem to conclude that
the boxed expression is (lambda + mu)^n. But now, the final result again follows the Poisson
distribution, just that this time, the rate of arrivals is lambda + mu. This means that
the overall process is really the Poisson process with the combined rate. So hopefully
the calculation makes it much more convincing, albeit a little tedious.
In any case, the idea is that if we want to use the central limit theorem, we can split
up this high rate of customer arrivals, into n different arrival processes, each with a
rate of 1 customer per hour. And with that, let’s go back to the statement of the central
limit theorem. In this case, we want the identical copies to be the Poisson processes with rate
1. They will follow the Poisson distribution with both mean and variance being 1. The mu
and sigma squared can be substituted into the final statement of the theorem. But what
does this statement translate to? This means that the probability that the quantity is
smaller than m, becomes more and more similar to what a standard normal random variable
does.
Our next task is to massage the expression inside the probability. (Wait 8 sec) Remember
that each of these X_i’s represent customer arrivals at a rate of 1, and we said that
the sum is equivalent to the arrival process with rate n. So as n tends to infinity, we
have this statement about the Poisson distribution only because we can split it up into n different
small arrival processes. Now Poisson distribution tells us that the left hand side is the proportional
contribution of the first m sqrt n + n terms in the exponential series. So if you want
these terms to contribute 99% of the exponential series, then we just need to find the m to
be in the top percentile of the standard normal distribution. In general, there is no closed-form
formula to find that out, and we have to do this numerically. In this case, we need the
m to be around 2.33, so that we get a 99% cumulative probability.
That means for the probability to reach 99%, we need m to be about 2.33. This in turn means
that for large n, we need roughly n + 2.33 sqrt n terms in the series to reach 99% accuracy.
So what we have demonstrated here is that if you want 99% accuracy, then n + 2.33 sqrt
n terms are required in the series. And if you want even higher accuracy, then you will
need more terms, but the number of terms required is also similar like n + something times sqrt
n. To put this to scale, let’s say we want to compute the exponential of 1000. The number
of terms required are roughly in the order of 1100. And that’s quite a lot of terms
required already. But what’s more, during the exponential series, each term is very
difficult to compute. The numerator is totally fine. It will just be 1 with a bunch of zeros,
but the denominator is really difficult to compute. So if you want to compute the exponential
of a large number, adding up terms in the series is very, very inefficient.
So, how do computers actually compute the exponential function? You can head over to
Oscar’s channel to find out - he does a lot of different videos on numerical methods,
or you can click the card above. In any case, if you enjoyed this video, please like and
subscribe with notifications on, comment and share the video. It will help a lot. See you
next time!