Full transcript
0:04Well,
0:23[clears throat]
0:25deploy
0:26set.
0:30is
0:45factorich.
1:09the
1:16factorial.
1:25Factorial
1:44Okay. Yeah.
1:54No, there
2:43Okay.
2:46foreign.
3:16foreign.
3:24Yeah.
3:34foreign.
4:04Yeah.
4:21Say
4:42data for.
4:44Yeah.
4:55Yeah.
5:15Amber processors.
5:32on there.
5:50Yeah.
5:56Fore!
5:59Foreign! Foreign!
6:09Fore!
6:21Foreign! Foreign!
6:34Yeah.
6:46Yeah.
6:53for
7:23um
7:41Well,ch.
7:53Professor
8:05Donald
8:21for
8:50inch.
8:55Yeah.
8:59Yeah.
9:04Yeah.
9:13for
9:30[snorts]
9:49Okay.
10:00for
10:19YouTube.
10:25Share
10:42Hi. Uh, welcome to uh first computer
10:46musing of the uh there's an echo. Is it
10:48okay? Um
10:51uh okay. There's a Welcome to the first
10:53computer musing this uh this quarter. I
10:56expect to have another one uh on 13th of
10:59December. Uh I'm sorry I I can't do it
11:02during finals week. So this is the
11:03Monday after finals week. And so I know
11:05a lot of you'll be gone home. If so, you
11:07can watch it on TV. Uh these uh the
11:11Stanford uh SCPD, whatever it stands
11:14for, u has been uh very good about
11:18putting the back lectures in this series
11:21online. And um I I watched most of them
11:25again and I realized that I had now I
11:28had better stop telling the same jokes
11:29all the time. Um and and I have to pay
11:34more attention to other little
11:35mannerisms that I'll try to get rid of.
11:37But anyway, uh uh it is possible uh uh
11:42let's hope to uh to watch uh this again
11:46uh later on uh in case you want to see
11:49you know why I made certain mistakes or
11:52whatever it is. And uh also uh uh uh uh
11:55we hope this will be a resource for
11:57future uh people who who are interested
12:01in in the cool stuff that I that I might
12:04have uh uh uh
12:08well
12:10the point of these lectures is that is
12:12uh whenever I whenever I hear something
12:14that I think is pretty interesting that
12:16I that I don't think is in any of our
12:18other curriculum um I can't resist
12:21coming in front of noise and telling
12:23somebody about it. And today is a
12:24special is is a special case. You know,
12:27uh my title today is hooray for
12:29probability theory. And really that's a
12:31sentiment I felt very strongly twice
12:34this year. Um when I had been working
12:37hard on a problem for a long time uh
12:40well for me a long time is two weeks.
12:42But anyway, I've been working very hard
12:43on the on these problems and I decide to
12:45give up on it and then um all of a
12:48sudden uh uh um wake up in the morning
12:52say wait probability theory might help
12:54and then I find not only a way to solve
12:56the problem but a way that's that's uh
12:58easy and beautiful and so on. Um uh I
13:02hope you I hope you agree when you see
13:05when you see the two things I'm going to
13:06talk about. In fact, the the first one
13:07I'm going to talk about is is something
13:09I learned about just at the end of June.
13:12And it's so uh it's so simple, so
13:16useful, so beautiful that I think it
13:19should be in all books on mathematics.
13:21But I had never heard about it until
13:23last June. I you know I thought you know
13:24by the time you get to be as old as me
13:26you it's not very often that you hear
13:29something that's that has all those
13:30characteristics anymore because most of
13:32the simple stuff uh presumably has has
13:35been well hashed over and maybe a lot of
13:37you will know this. It's just that it
13:38was just me that didn't know it. But
13:39anyway, it's a it if I were uh you know
13:42if I had known about it uh before I
13:44retired, I certainly would have put it
13:46in uh um in my book concrete
13:49mathematics. And now um uh I I was able
13:53to sneak it in as exercise number 62 in
13:56uh art of computer programming. But uh
13:58uh I want to I'm glad to see so many
14:01people here today so that uh uh you can
14:03pass the word on because it's it really
14:07a beautiful result. Now how can anything
14:08possibly live up to so much hype? Uh
14:11well we'll have to see. So first, so I
14:14guess I better just write down a theorem
14:17and see uh and and then we'll we'll add
14:19to the theorem. But uh uh the first uh
14:23uh result um uh comes out with about
14:27probability theory and u uh so let's uh
14:32well I won't write down a theorem that's
14:33a boring way to let let's suppose that I
14:36have n coins and I'm going to flip uh
19:55uh I you know I had never I I never
19:58heard it I I I knew it in in special
20:00cases but I never had heard it before
20:02and and this has many corlaries that I'm
20:03going to get to later. So so before I go
20:06to the corlaries and applications let's
20:08try to prove this result because the
20:10proof is also very nice. Um, so, uh, is
20:15it clear what I'm trying to prove
20:16though? First of all, that if you're
20:18flipping coins and you want to know
20:20what's the odds of getting, uh, getting
20:24K heads and K is less than or equal to
20:26the average, then that's bigger than
20:29your chance of getting less than uh, K
20:32minus one heads. Uh, strictly bigger.
20:36Uh
20:37and um
20:40uh
20:42let's see. This is
20:45weird. Let me see.
21:00Is this
21:03Let me just check that it's correct.
21:06when when all the P's are one and when
21:08Q's are zero
21:10um because that because I'm a little
21:12worried there if all the P's are one
21:14that means I'm always going to get N
21:15heads right so A N is one and all these
21:18others A's are zero here and so uh I
21:21have better
21:24what yeah but it's it's strictly oh okay
21:27uh or AK equals Z or or or they're both
21:32zero or both are zero Um
21:37uh so so there isn't there is this
21:39little exception. That's one of the
21:41great advantages you have of when you
21:44when you give a lecture you always think
21:46of something that you don't think of
21:47when you're writing the book. Okay.
21:49Okay. So uh but it's going to be strict
21:52it's going to be strictly less than uh
21:53in the interesting cases. And I and I'm
21:55going to want I'm going to want to know
21:57that. Um so trivially the we can have
22:01some zeros at the very at the beginning
22:04uh or at the end I mean all the things
22:06these things could be zero as well. Um
22:09so we got the same caveat both zero.
22:13Okay. Now um but let's let's consider
22:15first the case when all the all the
22:17probabilities are equal. So, so first
22:20case one is uh P subj equals P for all
22:26J.
22:28All right. Well, that's easy.
22:31What's this polinomial in that case? So,
22:32that's Q + P Z raised to the N power.
22:37And we know the binomial theorem. So
22:39that is the summation of you know n
22:42choose k b to the k um v to the k
22:50q to the n minus k
22:52which is you know the coe so a subk is
22:55the coefficient of z to the k which is n
22:58choose k p the k q n minus k I'll write
23:00I'll write that as n factorial over k
23:03factorial n minus k factorial
23:06p to the a u to the n minus k.
23:11Now uh so let's check it uh let's let's
23:14check if our result works. Um what is
23:16mu? mu is equal to n * p the average
23:23uh and a k minus one / a k
23:28uh we just plug in. So got n factorial k
23:34-1 factorial
23:36n minus k + 1 factorial
23:41um e the k minus one
23:45q n minus sorry q n minus k + one and
23:50then I got to divide by a k which is n
23:53factorial k factorial n minus k
23:55factorial e to the k q n minus k lot of
23:59cancellation occurring here. So the P to
24:02the K goes out with this P to the K. The
24:05Q to the N minus K goes out with this Q
24:07to the N minus K. Uh the N factorials go
24:11away.
24:12Uh the K factorial
24:15almost cancels with K minus one
24:17factorial and the N minus K + 1
24:20factorial almost cancels with this guy.
24:22So what? So I'm left with P I'm sorry, Q
24:25over P
24:27uh K over N + 1 - K.
24:33Um and um now I want to show that that
24:38if K is less than um or equal to mu uh
24:42that this is less than one
24:47less than one. So, so uh the thing is if
24:51k if k is is less than or equal mu then
24:58uh k over mu
25:01is uh less than or equal to n n n n n n
25:04n n n n n n n n n n n n n n n n n n n n
25:04n n n n n n n n n n n n n n n n n n n n
25:04n n n n n n n n n n n n n n n + 1 - k /
25:06n + 1 - mu.
25:09that this is true if I put any number in
25:11in place there because you know you
25:13multiply it out what do you get the uh
25:17uh k * n +1
25:20minus k mu multiply this by this and and
25:23that is supposed to be less than or
25:24equal to mu * n +1 - k mu and that
25:30certainly is is true n +1 being positive
25:35so so here's uh something that I can
25:39Also, what about Q over P?
25:42Oh, well, Q is is N minus NP.
25:47[clears throat]
25:48Uh, I'm sorry. Yeah, Q is is um
25:54Q over P is 1 - P over P, which is N
25:58minus mu over N minus
26:04mu over mu because you multiply both
26:07numerator and denominator
26:09by n and you get this.
26:12So, so then my uh in my proof of pen I
26:17have a k - 1 over a k is equal to q over
26:20p * k / n - 1 - k
26:25um and this is equal to n - mu over mu
26:29uh and k over n -1 - k well that's let
26:32me just make that less than or equal
26:35because k over n - 1 - k is less than or
26:38equal to mu / n +1 - mu right so this is
26:42equal to n - mu / n + 1 - mu and it is
26:46definitely less than one. That was what
26:48we wanted to prove. Strictly less than
26:49one. So a a k minus one is less than a
26:51subk uh unless they're both zero.
26:56Uh which could happen if p is equal to
26:58one as we observed before. Now um
27:04uh so we prove this result in the case
27:06where all the probabilities are the
27:08same. And now uh we want to prove it the
27:13other case where the probabilities are
27:14not the same. Um well uh so now let's
27:18suppose that um that I've got two
27:22probabilities P1 and P2 that are
27:27different and also different from zero
27:29or one. Zero and one are trivial cases
27:32that there's no there's no chance when P
27:36when when the probability is zero or
27:37one. So suppose we have this condition
27:41then uh we consider uh another set of
27:45probabilities. So I'll take P1 prime
27:48to be P1
27:51uh minus epsilon
27:55and P2 prime to be P2
27:58plus epsilon.
28:02And uh then of course q1 prime is going
28:04to be q1 plus epsilon and q2 prime is q2
28:08minus epsilon. But I I subtracted
28:12epsilon is some terribly small number. I
28:14subtracted epsilon from for in one case
28:18and added it in the other case because I
28:19still have the same mu. Mu prime is is
28:22p1 prime plus pn prime is the same as p1
28:28through pn. So I haven't changed the
28:30average. I'm just changing that making
28:32this uh first coin a little less tiny
28:35bit less probable the second coin tiny
28:37bit more probable. Um
28:40um so let's compare you know what the
28:44different coefficients are and let's
28:46figure out what's ak prime
28:49um
28:51and um ak prime
28:55uh is equal to a k. Now here we have
29:00well we can work it out. Um and uh uh
29:04it's tedious to go through the details
29:06but I'll show you how it starts. Um so
29:10um come back to this in a minute. Uh
29:12let's start out and figure out what what
29:15we've done. So Q1 prime + P1 prime Z *
29:19Q2 prime + P2 prime Z um is equal to Q1
29:27um plus epsilon
29:30plus P1 prime
29:34uh let's
29:36simplify a little bit q1 + p1 z
29:41plus epsilon * 1 - Z
29:50and then the second term is same
29:54[snorts] same deal Q2 + P2 Z but now
29:57minus epsilon * 1 - Z and so this turns
30:00out to be equal to what we had before Q1
30:03plus P1 Z
30:05uh Q2 + P2Z
30:08and then it um I actually want to work
30:11out the other term exactly and I but I
30:14won't bore with it. You have to trust
30:15me. It turns out to be epsilon * p1
30:18minus p2 minus epsilon * 1 - z ^ 2.
30:24And uh you you can check that out with
30:27any of your favorite computer algebra
30:28system. Uh so um but it uh it's nice
30:35because it um factors in this way and
30:39therefore I claim that a k prime is
30:43equal to a k plus epsilon * p1 minus p2
30:50minus epsilon time some factor alpha k
30:55where where alpha k comes from I mean
30:58here you
31:01you you multiply
31:03you you multiply this by all the other
31:05guys uh Q3 plus P3 Z and all the other
31:09and all the others and so so the same
31:12thing occurs here P3Z and all the other
31:15um and and on the last term too
31:20um and so what's the perturbation in
31:22these coefficients it's something that's
31:25epsilon * P1 - P2 - epsilon time
31:28something that has nothing to do with P1
31:30and P2.
31:32So, so this is alpha K is some function
31:35of P3
31:38uh to PN but the P1 and P2 don't appear
31:41there. So, so um
31:45now uh the point is um I'm going to try
31:49to find uh well the difference between
31:52alpha K prime prime and alpha K minus
31:55one prime. I'm going to try to make this
31:58extreme. I'm going to try to make this
32:00uh uh let's say as u as small as
32:04possible
32:06because if I make it as small as
32:07possible and it still is positive uh
32:10then it then a you know uh that's what I
32:13want to prove. If if my result is wrong
32:16u this is going to have to go negative.
32:18So anyway, I'm going to look for the for
32:20the I'm I'm going to consider all
32:22choices of all my probabilities uh in
32:24such a way that this number comes out to
32:27be as small as it is. And I'm going to
32:29show that that's still positive. Um and
32:32so uh what is it? It's equal to uh a k -
32:37a k minus one plus epsilon * p1
32:41- p2 - epsilon times some you know beta
32:45k difference of of alpha k minus one. So
32:50um now
32:53if beta k is not zero
32:57then I can't possibly have have found
32:59the this the worst case of these
33:01probability
33:02because I uh uh because if beta k is not
33:06zero uh you know I I can choose epsilon
33:09to be some small number and this is
33:11going to be smaller
33:14than this guy. I mean depends if beta k
33:16is positive uh you know p1 is less than
33:20p2. So this guy is definitely negative.
33:22Uh so I choose you know if bk is
33:25positive then I could choose you know
33:26epsilon to be positive some positive
33:28small number. If BK is negative, I can
33:30choose F1 to be some negative number.
33:31But certainly um uh if BK is not equal
33:35to zero, I'm not at, you know, I'm not
33:38at the at an extreme point.
33:42uh but on the other hand if BK beta K is
33:46zero then
33:49um I then I can then I can choose
33:54epsilon
33:56so that
33:58either
34:01E1 prime equals zero or E2 prime equals
34:061 because you see how I chose you see
34:09how how uh you know so
34:12I can choose epsilon to be uh
34:16p1 unless that makes p2 get too big in
34:21which case I choose epsilon so that p2
34:23gets equal to one. So, so in other
34:26words, I I so, so, so the, so if bk is
34:30z, if beta k is zero,
34:33then there's also an extreme point in
34:35which uh in which uh I have, you know,
34:40another zero, another one.
34:42So I keep doing this and and finally I
34:45get to the situation where I can't do it
34:48anymore. That means that I have some
34:52probabilities are zero, some
34:54probabilities are one and all the rest
34:56are equal.
34:57With me there is there's got to be an
35:00extreme point in which all the
35:02probabilities are
35:05one of these three values 01 or P some
35:08common value P.
35:10Uh now but but that's the case I already
35:15proved it correct for. So this is the
35:18this is the completion of the of the
35:20proof because if if all the values are
35:22zero um or one or p um you know that
35:26means that I had a um a polomial where
35:31uh well the zeros and ones are really
35:33easy to you know they're just little
35:34factors of uh that don't affect the
35:37final coefficient and they affect mu in
35:40the in the [clears throat] obvious way.
35:41So uh uh any questions on this? I I
35:46proved the I proved the amazing theorem
35:48that you that you your chances of
35:51getting more heads always increase as
35:53you get closer and closer to the mean.
35:56Now you might say, okay, so what what
35:59does that mean to me? And the next uh
36:02result will explain one of the reasons
36:05why uh I like it. And um uh so for this
36:11let me show you one of the
36:15page from volume one of the art of
36:16computer programming. Let's see if we
36:18can zoom up on that. How close can you
36:20get in on that? Um, Sean,
36:24very good. Yeah, this is page 99
36:28and I'm analyzing one of the this
36:33first algorithm where I really uh uh
36:37thought it was simple and and worth you
36:39know non-trivial analysis and that was
36:41the problem of finding the maximum of
36:44set of n numbers and uh it turns out
36:47that uh the the algorithm we all that we
36:52all almost always use is we say well we
36:54compare the first number to the second
36:55number and then um half the time we
36:58might have to switch. But we always
36:59compare our current maximum to the then
37:02to the third number and and maybe switch
37:05um if necessary and and then compare
37:07that to the fourth number and so on. And
37:09um uh at the end uh we want to know
37:12maybe how many times we had to switch
37:13during this algorithm. Um, and the it's
37:18like flipping a coin because when you
37:20compare the first number to the second
37:21number, the half the time you're going
37:23to have to switch. After you compare the
37:26max of those two to the third number,
37:28oneird of the time you're going to have
37:29to switch. And so uh you you get a uh a
37:33histogram like this where saying, you
37:35know, uh certain certain uh odds that
37:40you never have to switch. The first guy
37:42was already the biggest. Uh this is a
37:44case where there were 12 you're trying
37:46to find a maximum of 12 guys. U the
37:48secondly uh though maybe you had to
37:50switch once or twice or something like
37:51but it looks like you know it peaks here
37:53at two.
37:55So uh in fact now we know that in that
37:58uh this
38:00any histogram for a sequence of coin
38:03flips is going to look is going to go up
38:05and then it's going to come down. And
38:07furthermore, we know uh that the place
38:10is going to uh where it's going to
38:13change from up to down is is there at at
38:16at mute. In fact, you see what what
38:19we've shown is that uh um the maximum
38:24of a1 or a z through a n is either equal
38:29to a sub floor of mu or
38:34a sub ceiling of mu. If if mu is an
38:38integer, we know that the maximum occurs
38:40right at that integer point. But if the
38:42if if if mu is 3.1 then it's either then
38:47the maximum is either going to be uh a3
38:50or a4.
38:52Um
38:54uh and uh
38:57now uh I also worked out a formula here
39:01for the for what those what those
39:04probabilities are and in that particular
39:06case of the finding the maximum problem.
39:09Uh well this as I say it's a coin flip
39:11and you can write and you can write the
39:13thing as like this z plus one z plus 2
39:16up to z plus n and then um I'm sorry uh
39:22uh let's go
39:25z + one
39:28uh up to z + n minus one
39:31u divided by n factorial
39:35and the coefficient of z to the k will
39:37be the probability that we needed to to
39:40switch our maximum k times.
39:43Um
39:45it's it's the same as writing z times z
39:50over 2 plus oh sorry 12 plus uh z over 2
39:55and then 2/3 + z over 3
40:00up to n minus one
40:03over n + z / n. Uh
40:08so so you know when we make the last
40:10comparison we have a a chance one over n
40:13of of having to switch. Um so now uh so
40:18this is the generating function for how
40:20many uh how many times I'm going to have
40:23to switch when finding the maximum. Um
40:25and the coefficients here are
40:29um are are well known as the the
40:31sterling numbers. of the coefficient ak
40:34in that case is the is the sterling
40:35number n
40:38uh over k with brackets around it
40:40divided by n factorial. Um and these
40:44numbers uh
40:46n um
40:49over k with brackets are are well known
40:52to be also the number of permutations on
40:55n elements that have exactly kycles.
41:00Uh so these numbers are occur all over
41:03the place in in mathematics. Um and uh
41:07so now uh so we have a and what's mu?
41:11music.
55:52Okay.
56:35Gambia. for
57:05set Fore!
57:15Foreign! Foreign!
57:39island.
57:47Okay.
58:04No. Yeah.
58:14foreign.
58:21Okay.