5 ms·

Since the article links straight to the video stream (OP: please add a note to the title), here's Knuth's introduction to this particular Christmas Tree Lecture

Since the article links straight to the video stream (OP: please add a note to the title), here's Knuth's introduction to this particular Christmas Tree Lecture (on Pi): "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."

ddlatham 16y ago
Why 2*Pi?
JoeAltmaier 16y ago
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.
- ximeng 16y ago
  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: 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) This is meant to be symmetric around x=y. Each different character represents a different total. All these areas are the ones we've been trying to make the same: "." is the probability of getting a total of two on two dice. "#" is the probability of a 3 total, and so on. It gets closer and closer to a circle. 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... This looks like this (- marks 0) x x x x x---x-x-x- etc. x x x x We know Sum(ak, a(n-k))=1. 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.
- endtime 16y ago
  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.
- omaranto 16y ago
  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"?)
tedunangst 16y ago
for the curious, that formula in bc -l parlance is: p = a(2^1000)*2 sqrt(2 * p * n) * (n / e(1))^n

ddlatham 16y ago

Why 2*Pi?

JoeAltmaier 16y ago

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.

ximeng 16y ago
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: 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) This is meant to be symmetric around x=y. Each different character represents a different total. All these areas are the ones we've been trying to make the same: "." is the probability of getting a total of two on two dice. "#" is the probability of a 3 total, and so on. It gets closer and closer to a circle. 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... This looks like this (- marks 0) x x x x x---x-x-x- etc. x x x x We know Sum(ak, a(n-k))=1. 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.
endtime 16y ago
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.
omaranto 16y ago
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"?)

tedunangst 16y ago

for the curious, that formula in bc -l parlance is: p = a(2^1000)*2 sqrt(2 * p * n) * (n / e(1))^n