stanford-online.stanford.edu
Why pi?
http://stanford-online.stanford.edu/seminars/knuth/101206-knuth-500.asx
13 comments
The formulae are similar; are they really related? Any more than the dance of bees are related to quantum mechanical states (another recent article)?
I'm sorry, I couldn't sit through the whole lecture (2 minutes actually); the digressions and glacial pace reminded me viscerally why I had such trouble in graduate school.
I'm sorry, I couldn't sit through the whole lecture (2 minutes actually); the digressions and glacial pace reminded me viscerally why I had such trouble in graduate school.
It gets going after the first 2 minutes, not many digressions, pretty much pure maths lecture. Summary below of the first hour or so if you want it, might be hard to follow, but it shows the depth of the lecture pretty well.
He will establish a link between Pi and factorials, as well as trees, using generally simple maths.
---
The number of (ordered) forests with n nodes:
n=2 - 2 forests [o, o; o (o)], where , separates trees within forests, ; separates forests, () indicates child node
n=3 - 5 forests [o, o, o; o, o (o); o (o), o; o (o) (o); o (o (o))]
In general the number of forests with n nodes is Cn where Cn is the nth catalan number. For n=0..4, Cn=[1, 1, 2, 5, 14].
The nth catalan number is C(n):=((2n)!/n!(n+1)!). E.g. for n=3, 6!/(3!4!)=5.
It turns out that:
C(n) approx= Exp(4,n)/(Sqrt(npi)(n+1))
For n=1000, the first 4 significant figures match in a number with 598 digits.
Johan Wästlund published a result explaining the link between Pi and trees in Dec 2007.
---
Problem inspiring JW's investigation is biasing two dice (changing their probability) so that 2..12 are all equally likely.
To do this set the probability of two 1s to x. This is the probability of rolling a total of 2.
Now the probability of a total of 3 is the probability of a 1 and a 2, times two. So we want the chance of rolling a 2 to be half the probability of rolling a 1.
Similarly the probability of rolling a total of 4 is the probability of a 1 plus a 3 times two, plus the chance of two 2s.
If we set p1 = probability of a 1, p2 = probability of a 2, ...
(1) p1p1 = p1p2 + p2p1 (since a total of 2 is as likely as a total of 3) => p2 = p1/2
(2) p1p1 = p1p3 + p2p2 + p3p1 = p1p3 + p1p1/4 + p3p1 => p3 = 3p1/8
(3) ... p4 = 15p1/16
(4) ... p5 = 35p1/128
(5) ... p6 = 63p1/256
This set of probabilities satisfies the original problem up until a total of 6.
( ^ ) Note the constants are: 1/2, 1/2 3/4, 1/2 * 3/4 * 5/6, 1/2 * 3/4 * 5/6 * 7/8.
( ^^ ) Proof of this: Let pj=a(j-1)p1. We have a0=1, a1=1/2.
Form an infinite series, A(z)=a0+a1z+a2Exp(z,2)+a3Exp(z,3)+... Square it: Exp(A(z),2)=a0a0+(a0a1+a1a0)z+(a0a2+a1a1+a2a0)Exp(z,2)+... This equals 1+z+Exp(z,2)+Exp(z,3)+... (by hypothesis, ajp1=p1 for all aj), which is just a geometric series with total 1/(1-z).
(+) So A(z) = 1/(sqrt(1-z)) = Exp(1-z,-1/2). Using binomial theorem, this equals
Sum(n=0..infinity) of (-1/2 choose n [binomial coefficient])Exp(-z,n).
an=(-1/2 choose n)Exp(-1,n)
E.g. a3= (-1/2 - 3/2 - 5/2)/(3 2 * 1) * Exp(-1,n) = (1+3+5) / (2 * 3!), which is the result we had above at ( ^ ).
( ^^^ ) We know p1+p2+p3+p4+p5+p6=1 as the dice are six-sided. This gives p1p1(a0+a1+...+a5) = 1 (see ( ^^ )). So what's a0+a1+...+a5?
Take A(z)(1+z+Exp(z,2)+...) = a0+(a0+a1)z+(a0+a1+a2)Exp(z,2)+... . Let's call this S1 + S2z + S3z + ... . Then we want to find S6 = a0 + ... + a5. Remember that p1p1s6=1 from ( ^^^ ).
Well by (+) A(z)(1+z+Exp(z,2)+...)=Exp(1-z,-1/2) (1+z+Exp(z,2)=Exp(1-z,-1/2) Exp(1-z,-1). This is just Exp(1-z,-3/2).
Expanding that, we have Sum(n=0..infinity) of (-3/2 choose n)Exp(-z,n). The - signs cancel out again.
Let's work out the values of Sn: S1=1, S2=a0+a1=3/2, S3=a0+a1+a2=15/8=3/2 * 5/4 ... and S6=3/2 * 5/4 * 7/6 * 9/8 * 11/10.
Picture here:
So this is the link to the circle. If n is the area shown in the diagram above, we have n approx= (pi/4) Exp(Sn,2), since this is a quarter of a circle with radius Sn. We want to prove the circle goes through the rectangles just outside the edge, if so we can show that n - 1 < (pi/4) Exp(Sn,2) < n + 1 (!) . This is because we are setting the area of each total (i.e 2..7) to be 1, so adding an extra total (which looks more and more like a circle as n gets bigger) will just add one to the total, and we are going to prove an ideal circle would go through the outer rim (e.g. the "z"s in the diagram above).
Let's look at some examples.
Exp(S6,2) = Exp(3/2,2) * Exp(5/4,2) * Exp(7/6,2) * Exp(9/8,2) * Exp(11/10,2) from above.
Exp(S9,2) = Exp(s6,2) * Exp(13/12,2) * Exp(15/14,2) * Exp(17,16,2)
Note Exp(1+1/2k,2)=1+ 1/k + 1/(4Exp(k,2)) > 1 + 1/k
So Exp(S9,2) > Exp(S6,2) (1+1/6)(1+1/7)(1+1/8) = Exp(S6,2)(7/6)(8/7)(9/8)=Exp(S6,2)(9/6) by cancelling. He also proves that Exp(S9,2) < Exp(S6,2)(8/5).
In general Exp(Sa,2)(a+b)/a < Exp(s(a+b),2) < Exp(Sa,2)((a+b-1)/(a-1)). From this inequality (ineq), he can prove his result on the approximate value of Sn, (!) above.
He wants the circle of radius S6 to go outside the inner most notches in the diagram (between " and z in the diagram above). Note that these coordinates (S5,S1), (S4,S2), ... . By Pythagoras we want Exp(Sk,2) + Exp(S(n-k),2) < Exp(Sn,2) < Exp(Sk, 2) + Exp(S(n+1-k),2), this follows from his inequality (ineq) above.
(Incidentally you can do the same construction with 3 dice forming a ball, there is a picture at 56:00 which I won't try to reproduce in ascii.)
---
So we now have a relationship between Sn and Pi, Sn approx= 4n/Pi. Also Sn is a sum of values of an, which are just (1/2) (3/4) ... (2n-1/2n). Finally Sn=2nan (not quite sure why??). From all this we can get an=1/(Sqrt(Pin).
The number an is famous in connection with a random walk of length n. The probability of flipping a coin 2n times and getting equal number of heads and tails is an. This probability is (2n choose n)/Exp(2,2n). But (2n choose n) is just ((2n) (2n-1) ... 1) / (n! n!), which is just an an above.
Rather than a coin, he takes the binary digits of pi/4 as heads and tails:
This is equivalent to (apparently!) Sum((2k choose k) * (2n-2k choose n-k)=Exp(n,4)
(A digression here on "balanced random walks" and the links to 2d barcodes like QR-codes. You decompose a finite random sequence of bits like the bits of pi, into two parts. The first part is the sequence up to the last point the sequence crosses the origin, this part is balanced. The second part diverges from zero and needs to be balanced by flipping some bits according to a "Christmas tree pattern".)
--- c. 1h15m in at this point.
It gets a bit sketchy from here, but he goes to the Stirling formula from here, which uses the Catalan numbers.
He will establish a link between Pi and factorials, as well as trees, using generally simple maths.
---
The number of (ordered) forests with n nodes:
n=2 - 2 forests [o, o; o (o)], where , separates trees within forests, ; separates forests, () indicates child node
n=3 - 5 forests [o, o, o; o, o (o); o (o), o; o (o) (o); o (o (o))]
In general the number of forests with n nodes is Cn where Cn is the nth catalan number. For n=0..4, Cn=[1, 1, 2, 5, 14].
The nth catalan number is C(n):=((2n)!/n!(n+1)!). E.g. for n=3, 6!/(3!4!)=5.
It turns out that:
C(n) approx= Exp(4,n)/(Sqrt(npi)(n+1))
For n=1000, the first 4 significant figures match in a number with 598 digits.
Johan Wästlund published a result explaining the link between Pi and trees in Dec 2007.
---
Problem inspiring JW's investigation is biasing two dice (changing their probability) so that 2..12 are all equally likely.
To do this set the probability of two 1s to x. This is the probability of rolling a total of 2.
Now the probability of a total of 3 is the probability of a 1 and a 2, times two. So we want the chance of rolling a 2 to be half the probability of rolling a 1.
Similarly the probability of rolling a total of 4 is the probability of a 1 plus a 3 times two, plus the chance of two 2s.
If we set p1 = probability of a 1, p2 = probability of a 2, ...
(1) p1p1 = p1p2 + p2p1 (since a total of 2 is as likely as a total of 3) => p2 = p1/2
(2) p1p1 = p1p3 + p2p2 + p3p1 = p1p3 + p1p1/4 + p3p1 => p3 = 3p1/8
(3) ... p4 = 15p1/16
(4) ... p5 = 35p1/128
(5) ... p6 = 63p1/256
This set of probabilities satisfies the original problem up until a total of 6.
( ^ ) Note the constants are: 1/2, 1/2 3/4, 1/2 * 3/4 * 5/6, 1/2 * 3/4 * 5/6 * 7/8.
( ^^ ) Proof of this: Let pj=a(j-1)p1. We have a0=1, a1=1/2.
Form an infinite series, A(z)=a0+a1z+a2Exp(z,2)+a3Exp(z,3)+... Square it: Exp(A(z),2)=a0a0+(a0a1+a1a0)z+(a0a2+a1a1+a2a0)Exp(z,2)+... This equals 1+z+Exp(z,2)+Exp(z,3)+... (by hypothesis, ajp1=p1 for all aj), which is just a geometric series with total 1/(1-z).
(+) So A(z) = 1/(sqrt(1-z)) = Exp(1-z,-1/2). Using binomial theorem, this equals
Sum(n=0..infinity) of (-1/2 choose n [binomial coefficient])Exp(-z,n).
an=(-1/2 choose n)Exp(-1,n)
E.g. a3= (-1/2 - 3/2 - 5/2)/(3 2 * 1) * Exp(-1,n) = (1+3+5) / (2 * 3!), which is the result we had above at ( ^ ).
( ^^^ ) We know p1+p2+p3+p4+p5+p6=1 as the dice are six-sided. This gives p1p1(a0+a1+...+a5) = 1 (see ( ^^ )). So what's a0+a1+...+a5?
Take A(z)(1+z+Exp(z,2)+...) = a0+(a0+a1)z+(a0+a1+a2)Exp(z,2)+... . Let's call this S1 + S2z + S3z + ... . Then we want to find S6 = a0 + ... + a5. Remember that p1p1s6=1 from ( ^^^ ).
Well by (+) A(z)(1+z+Exp(z,2)+...)=Exp(1-z,-1/2) (1+z+Exp(z,2)=Exp(1-z,-1/2) Exp(1-z,-1). This is just Exp(1-z,-3/2).
Expanding that, we have Sum(n=0..infinity) of (-3/2 choose n)Exp(-z,n). The - signs cancel out again.
Let's work out the values of Sn: S1=1, S2=a0+a1=3/2, S3=a0+a1+a2=15/8=3/2 * 5/4 ... and S6=3/2 * 5/4 * 7/6 * 9/8 * 11/10.
Picture here:
6zzzzzz
5""""""zzzzz
4oooooo"""""zzzz
xxxxxxooooo""""zz
3xxxxxxooooo""""zz
######xxxxxoooo""zz
2######xxxxxoooo""zz
######xxxxxoooo""zz
......#####xxxxoo""z
......#####xxxxoo""z
1......#####xxxxoo""z
......#####xxxxoo""z
1 2 3 4 56 (each number j has width / height a(j-1)), total width = S6)
So this is the link to the circle. If n is the area shown in the diagram above, we have n approx= (pi/4) Exp(Sn,2), since this is a quarter of a circle with radius Sn. We want to prove the circle goes through the rectangles just outside the edge, if so we can show that n - 1 < (pi/4) Exp(Sn,2) < n + 1 (!) . This is because we are setting the area of each total (i.e 2..7) to be 1, so adding an extra total (which looks more and more like a circle as n gets bigger) will just add one to the total, and we are going to prove an ideal circle would go through the outer rim (e.g. the "z"s in the diagram above).
Let's look at some examples.
Exp(S6,2) = Exp(3/2,2) * Exp(5/4,2) * Exp(7/6,2) * Exp(9/8,2) * Exp(11/10,2) from above.
Exp(S9,2) = Exp(s6,2) * Exp(13/12,2) * Exp(15/14,2) * Exp(17,16,2)
Note Exp(1+1/2k,2)=1+ 1/k + 1/(4Exp(k,2)) > 1 + 1/k
So Exp(S9,2) > Exp(S6,2) (1+1/6)(1+1/7)(1+1/8) = Exp(S6,2)(7/6)(8/7)(9/8)=Exp(S6,2)(9/6) by cancelling. He also proves that Exp(S9,2) < Exp(S6,2)(8/5).
In general Exp(Sa,2)(a+b)/a < Exp(s(a+b),2) < Exp(Sa,2)((a+b-1)/(a-1)). From this inequality (ineq), he can prove his result on the approximate value of Sn, (!) above.
He wants the circle of radius S6 to go outside the inner most notches in the diagram (between " and z in the diagram above). Note that these coordinates (S5,S1), (S4,S2), ... . By Pythagoras we want Exp(Sk,2) + Exp(S(n-k),2) < Exp(Sn,2) < Exp(Sk, 2) + Exp(S(n+1-k),2), this follows from his inequality (ineq) above.
(Incidentally you can do the same construction with 3 dice forming a ball, there is a picture at 56:00 which I won't try to reproduce in ascii.)
---
So we now have a relationship between Sn and Pi, Sn approx= 4n/Pi. Also Sn is a sum of values of an, which are just (1/2) (3/4) ... (2n-1/2n). Finally Sn=2nan (not quite sure why??). From all this we can get an=1/(Sqrt(Pin).
The number an is famous in connection with a random walk of length n. The probability of flipping a coin 2n times and getting equal number of heads and tails is an. This probability is (2n choose n)/Exp(2,2n). But (2n choose n) is just ((2n) (2n-1) ... 1) / (n! n!), which is just an an above.
Rather than a coin, he takes the binary digits of pi/4 as heads and tails:
.11001001...
x
x x x
x---x-x-x- etc.
x x
x
x
This is equivalent to (apparently!) Sum((2k choose k) * (2n-2k choose n-k)=Exp(n,4)
(A digression here on "balanced random walks" and the links to 2d barcodes like QR-codes. You decompose a finite random sequence of bits like the bits of pi, into two parts. The first part is the sequence up to the last point the sequence crosses the origin, this part is balanced. The second part diverges from zero and needs to be balanced by flipping some bits according to a "Christmas tree pattern".)
--- c. 1h15m in at this point.
It gets a bit sketchy from here, but he goes to the Stirling formula from here, which uses the Catalan numbers.
Lectures are a small part of graduate school, in my experience. Any impatience with lectures wouldn't seem to me to explain someone's trouble with graduate school. (Maybe you didn't mean "graduate school" but specifically "graduate courses"?)
I think the point is that pi, a constant defined by properties of circles, is also useful in an approximation of factorials, and there was no obvious reason for the circle-specific constant to show up in anything related to factorials.
for the curious, that formula in bc -l parlance is:
p = a(2^1000)*2
sqrt(2 * p * n) * (n / e(1))^n> Now I will go on with my own experience as a youngster in mathematics. Another thing that my father told me--and I can't quite explain it, because it was more an emotion than a telling--was that the ratio of the circumference to the diameter of all circles was always the same, no matter what the size. That didn't seem to me too unobvious, but the ratio had some marvelous property. That was a wonderful number, a deep number, pi. There was a mystery about this number that I didn't quite understand as a youth, but this was a great thing, and the result was that I looked for pi everywhere.
When I was learning later in school how to make the decimals for fractions, and how to make 3 1/8, 1 wrote 3.125 and, thinking I recognized a friend, wrote that it equals pi, the ratio of circumference to diameter of a circle. The teacher corrected it to 3.1416.
I illustrate these things to show an influence. The idea that there is a mystery, that there is a wonder about the number was important to me--not what the number was. Very much later, when I was doing experiments in the laboratory--I mean my own home laboratory, fiddling around--no, excuse me, I didn't do experiments, I never did; I just fiddled around. Gradually, through books and manuals, I began to discover there were formulas applicable to electricity in relating the current and resistance, and so on. One day, looking at the formulas in some book or other, I discovered a formula for the frequency of a resonant circuit, which was f = 1/2 pi LC, where L is the inductance and C the capacitance of the... circle? You laugh, but I was very serious then. Pi was a thing with circles, and here is pi coming out of an electric circuit. Where was the circle? Do those of you who laughed know how that comes about?
I have to love the thing. I have to look for it. I have to think about it. And then I realized, of course, that the coils are made in circles. About a half year later, I found another book which gave the inductance of round coils and square coils, and there were other pi's in those formulas. I began to think about it again, and I realized that the pi did not come from the circular coils. I understand it better now; but in my heart I still don't know where that circle is, where that pi comes from.
-Richard Feynman
"What is Science?"
1966 Lecture
http://www.fotuva.org/feynman/what_is_science.html
When I was learning later in school how to make the decimals for fractions, and how to make 3 1/8, 1 wrote 3.125 and, thinking I recognized a friend, wrote that it equals pi, the ratio of circumference to diameter of a circle. The teacher corrected it to 3.1416.
I illustrate these things to show an influence. The idea that there is a mystery, that there is a wonder about the number was important to me--not what the number was. Very much later, when I was doing experiments in the laboratory--I mean my own home laboratory, fiddling around--no, excuse me, I didn't do experiments, I never did; I just fiddled around. Gradually, through books and manuals, I began to discover there were formulas applicable to electricity in relating the current and resistance, and so on. One day, looking at the formulas in some book or other, I discovered a formula for the frequency of a resonant circuit, which was f = 1/2 pi LC, where L is the inductance and C the capacitance of the... circle? You laugh, but I was very serious then. Pi was a thing with circles, and here is pi coming out of an electric circuit. Where was the circle? Do those of you who laughed know how that comes about?
I have to love the thing. I have to look for it. I have to think about it. And then I realized, of course, that the coils are made in circles. About a half year later, I found another book which gave the inductance of round coils and square coils, and there were other pi's in those formulas. I began to think about it again, and I realized that the pi did not come from the circular coils. I understand it better now; but in my heart I still don't know where that circle is, where that pi comes from.
-Richard Feynman
"What is Science?"
1966 Lecture
http://www.fotuva.org/feynman/what_is_science.html
Very nice indeed. From the begining I felt it sounded like Feynman - he was an interesting guy.
On a purely superficial note, here are Knuth's recent Google searches, according to the Safari search box dropdown list that flashes by at 2:22:
• google calculator
• wolfram alpha
• williams cutlery
• craig gentry
• "the lost chord"
• acrobat scroll speed
• html bulleted list
• html subscript
• doerr "protocol partition number"
• google calculator
• wolfram alpha
• williams cutlery
• craig gentry
• "the lost chord"
• acrobat scroll speed
• html bulleted list
• html subscript
• doerr "protocol partition number"
> • acrobat scroll speed
I can't help but notice that two of those searches make Knuth probably a 'satisfied user' of w3schools :)
I'm glad I'm not the only one who can never remember Wolfram Alpha's URL and consequently accesses it through Google...
You should add "[video]" (or alike) to the title at least.
Just in case, the poster is not around, even the moderators can do that, right?
`mplayer "mmsh://proedvid.stanford.edu/knuth/musings/101206/101206-knuth-500.wmv?MSWMExt=.asf"`
For those of you who hate it when your browser decides to try to embed videos...
For those of you who hate it when your browser decides to try to embed videos...
Thanks!
Also,
> mplayer -dumpstream "mmsh://proedvid.stanford.edu/knuth/musings/101206/101206-knuth-500.wmv?MSWMExt=.asf"
for for those you who'd like to download the video for later viewing.
Also,
> mplayer -dumpstream "mmsh://proedvid.stanford.edu/knuth/musings/101206/101206-knuth-500.wmv?MSWMExt=.asf"
for for those you who'd like to download the video for later viewing.
I thought this was going to be pi's rebuttal to tau. :)
Me too, although in that vein I'll note that the π in the formula is actually a 2π, so the τists win again. ;)
What's the type of pen he uses while writing/drawing? I really would like to have one of those.
It looks like a permanent marker felt tipped pen. It's probably a Sharpie or Pilot brand.
I highly recommend the new Sharpie 'Pen' if you're looking for a nice writing pen. (This is not the one he's using.) http://pen.sharpie.com/
I highly recommend the new Sharpie 'Pen' if you're looking for a nice writing pen. (This is not the one he's using.) http://pen.sharpie.com/
Very odd. My browser (Chrome Mac 8.0.552.237) downloads the page (101206-knuth.asx) instead of showing it. Is this a bug on my end or on the hosting end?
EDIT: Nevermind, just realized I was expecting a web page and its a streaming media file. I confused the extension with .asp
EDIT: Nevermind, just realized I was expecting a web page and its a streaming media file. I confused the extension with .asp
It's not a bug, that's actually a video stream. Open VLC, and then use Open Network to open the link. It'll stream the video lecture.
But what about Preset 3? Has it, at long last, been stored?
[deleted]
[deleted]
"Mathematicians have known for almost 300 years that the value of 'n factorial' (the product of the first n positive integers)is approximately equal to n/e to the nth power times the square root of 2(Pi)n, where Pi is the ratio of the circumference of a circle to its diameter. That's 'Stirling's approximation'. But it hasn't been clear why there is any connection whatever between circles and factorials; the appearance of Pi has seemed to be purely coincidental, one of the amazing accidents of nature. Recently however Johan Wästlund has found a nice explanation of this phenomenon, and the reason turns out to be connected with the theory of trees."