Why pi?

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.

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.

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"?)

The weird wallpaper can be a sign it's Knuth's Computer :)