I thought I'd talk to you about factorials. Let me give an example so we know what we're talking
about: 3 factorial is just a product of 1 times 2 times 3. Now of course I didn't need to write the
1, because 1 times whatever comes after is still just whatever comes after but this is 6. Everybody
probably remembers the factorial in general is the product of all of the integers between 1
and whatever number you write last. So the second example - I'm going to skip 4 - and go straight to
5 factorial which is 1 times 2 times 3 times 4 times 5 and that, after you multiply it all out,
is actually 120. Probably a lot of us have encountered the factorial and had to figure
out what is, you know, 7 factorial? What is 8 factorial? And what you- you know,
you remember what you do, you you figure out what the previous factorial is and multiply by the next
number. Or you just have to do a whole bunch of multiplications which is, let's face it not not
everybody's favorite thing to do. What I want to tell you about actually is not just the factorial
but I want to tell you about a great approximation - maybe you can think of it as a function,
a machine, something that simplifies the- the description of the factorial function
at a at a cost, and the cost is sort of accuracy. It goes by the name of Stirling's approximation.
And so in order to talk about Stirling's approximation I have to introduce a letter
which will be a large number. So I'm going to use capital N, and say capital N factorial,
that is now- if N is 5 that is the number 120. If N is 3 that is the number 6. So I want to ask
how does this factorial function, how does it behave if N gets larger and larger and larger,
okay? I mean just as an example, you could imagine asking what's a 100 factorial?
And then you're multiplying 100 times- well so 2 times 3 times 4 times 5 all the way up to 100,
it's probably an enormous number. Well here's an approximation that will will you know allow you
to understand a lot about the factorial function. That little symbol means approximately equal to
and then it is N to the power N times e to the negative N times the square root of N times the
square root of 2 pi. So I didn't write equals, and I want to spend a little bit time explaining what
this what- I mean by this little symbol here, because it's really an approximation of N
factorial. It's not exactly equal to the factorial but it's an approximation. Before I even tell you
in what sense is it an approximation, it's it's fun to ask which one of these is easier to work with?
(Brady: Because professor you said a moment ago that you were going to show me a simplification)
(but at first glance that doesn't look like a simplification to me, that looks like a right)
(old mess compared to just 10 times 11 times 12 times 13. But you tell me this is simpler?)
Yeah so that's a- that's a fantastic point and it doesn't look like it's simpler but it actually is.
So the the amount of computations you need to compute a very large number factorial like 100
factorial is actually much larger than the number of computations that you would need
on the computer to evaluate the right hand side when N is 100. And in that sense it really
is a simplification. - (Okay so it's like- it's a bit of a hack here. It's a bit of a shortcut)
(but but you don't get it exactly right.) - That's exactly right. So this is what we mean when we say
it's an approximation: instead of saying, do these two things get closer and closer to each other as
N grows, I want to consider the ratio. So I have N factorial and I form a fraction where the
numerator is N factorial and the denominator is this approximation. Stirling's approximation
is an approximation in the sense that, as I get larger and larger values of N, this ratio
gets closer and closer to 1. What I've just described is actually a concept called a limit
and that, you know, you learn about it basically in a precalculus course or a calculus course
and so I should write out more precisely. I mean limit as N goes to infinity - and now I'm going to
rewrite that whole ratio - N factorial over N to the N e to the negative N square root of N square root
of 2 pi equals 1. So- so that is the mathematical version of this arrow. And just means as N gets
larger and larger and larger this quantity gets closer and closer and closer to the number 1.
(So so as we start factorializing, if that's the word, bigger and bigger numbers this Stirling)
(approximation becomes more useful?) - Exactly yeah, that's that's exactly right. Here's a funny fact:
for very large numbers the two values, N factorial itself and the approximation, they actually
don't get closer to each other in in sort of magnitude it's just their ratio that gets
close to 1. And it seems funny that can happen without these two numbers actually
getting close to each other. So some examples are useful to see what I'm talking about there.
(So where are we going to start?) - Well let's start with a small number like uh 5 factorial.
So we already know that it's 120 - what do we get if we uh if we plug 5 into this crazy formula right
here? 5 to the fifth power e to the negative 5 times the square root of 5 times the square
root of 2 pi? I did that offline and here's what you get: 118.019. - (That's pretty close.)
(You think that's close or not?) - Well let's be honest, it's off by almost 2. That's probably
that doesn't seem so close right? But remember that that really what I should be checking to
to check closeness is is does the ratio get close to 1? So if I compute the ratio of 120 over 118
- and .019 - and use a calculator offline that actually is 1.01678. Should we go smaller or bigger?
(We've gotta go bigger!) - Let's go bigger. Okay so um what's a- what's a good number?
(Uh, 100?) - 100 is a great choice. Let's see, I think I know that one - actually I don't,
and it would probably run out of ink before I finish writing it. So what
can I tell you about 100 factorial? Well it's enormous, it has 158 digits.
So I probably could fit it on this paper but- but maybe it's not too illuminating to write
out a 158 digit number that- at the same time maybe it is illuminating and hopefully
you can see it on the screen right now. And if I now use the approximation, instead of
writing out 158 digits, if I use the approximation here is the first interesting statement I can make:
the approximation captures the first two digits correctly. - (That feels like a failure to me, there)
(are so many wrong digits! That seems like a bad approximation but you're telling me that's a)
(good approximation?) - Yeah, right. It sounds funny but the beautiful fact is it captures the size
correctly, the magnitude of the number is also correct. Consider the ratio 100 factorial over
the approximation - I'll just write down the word approximation - then it turns out that is 1.00083.
And so the- you know the ratio of the two is almost 1, up to eight parts in ten thousand,
so in that sense it's actually capturing the right size and the first digits. - (So even though)
(5 factorial was out by only 2, and this new one you've given me is out by zillions, it's)
(actually closer?) - Yeah it's really a fact that the approximation, that the brutal distance
between the two things, the actual 100 factorial and the approximation, is is very large but
the the relative size is- it's nailing the relative size. One more example? - (You go, you choose a)
(number this time.) - So how about 2,000? So that is a number that has 5,730-some digits.
That's a big number. That wouldn't fit on this piece of paper. And if I were to compute the
approximation - let me say it like this - if I if I compute the ratio using Stirling's approximation
it is 1.00004. At 100 factorial the approximation- the ratio
gave 1.00083, eight parts in 10,000, this one gives four parts in
100,000. The approximation captures five- almost five digits of 2,000 factorial but
mind you it is a number which has 5700 and some digits. - (As we approach the)
(limit, you're telling me this ratio is getting closer and closer to 1, but will the actual)
(difference between the two numbers also close at any time? Or will that just continue to balloon?)
Yeah the actual distance between them will continue to balloon. Absolutely grows, in fact grows
very very fast. But the ratio still goes to 1. - (Seems counterintuitive at first thought, doesn't it?
Yeah. So um so another question that people ask about often is uh, well this is a crazy formula
on the left hand side, you you are just multiplying together integers. And the asymptotic description,
the approximate description on the right hand side, it's it's got some interesting things, it's
got the number e - Euler's constant that comes from calculus. It's got root 2 pi which has a pi in
the middle of it. You know, where does this formula come from and how do these crazy constants that
come from some other parts of mathematics, how do they appear in this? I don't want to give you a
complete answer for that, but there is a beautiful formula which provides a fantastic explanation.
There's a way to represent any integer factorial as an integral from 0 to infinity of x to the N
times e to the negative x dx. Now this is something which if you have had a course in
calculus you would see this and say, oh I bet I can evaluate that. Think of it as a beautiful way to
represent N factorial and so some folks would say, N factorial is actually represented as an integral
and once you have an integral you can begin to play all kinds of tricks. And there's a five step
process to to compute this approximation - step five, at the very end, out pops the square root of two pi.
(Who uses Stirling's formula?) - So uh many many scientists use Stirling's formula. So uh people
in in mathematics, in the fields of combinatorics, it's it's uh it's their bread and butter. People in
mathematical physics who study statistical physics they use this this approximation all of the time.
Essentially every area of mathematics in which there's large numbers appearing
the approximation becomes very useful. Many areas of physics they- calculations are done on the back
of envelopes and those calculations always involve this approximation because it simplifies things.
(Are they using it to to save time or because it's a better thing to use?)
It's a better thing to use and it does save time. But it's really a a machine that will simplify
calculations. When you're interested in sort of behavior as number of unknowns grows to infinity,
or number of particles in a system goes to infinity, it's it's a simplifying machine
in those situations. Of course for smaller numbers it may not be so useful but once you have a large
number floating around in and you need the factorial of that large number this is a
approximation that's very useful. You take the best computer you can find and you ask how large
a value of N can I plug in and get an exact answer? And how large can I take this formula and use the
same computer to evaluate this formula? And the answer is the approximation can be evaluated for
much much larger values of the integer N than the exact formula N factorial, because it just takes
so long to compute. - ...easily in my head, now that's equal to 120. So these numbers increase
quite quickly. So it's fun just to work out factorial 20 and I can do that by continuing this
process but it's much easier to get out my pocket calculator. So let's do 20, so there's 20 going in...