John Cook writes:
The nth row of Pascal’s triangle contains the binomial coefficients C(n, r) for r ranging from 0 to n. For large n, if you print out the numbers in the nth row vertically in binary you can see a circular arc.
He explains:
The length of the numerical representation of a number is roughly proportional to its logarithm. Changing the base only changes the proportionality constant. The examples above suggests that a plot of the logarithms of a row of Pascal’s triangle will be a portion of a circle, up to some scaling of one of the axes, so in general we have an ellipse.
Cook continues with an explanation of why the ellipse fits so well:
WoЇfgang pointed out that the curve should be a parabola rather than an ellipse because the binomial distribution is asymptotically normal. Makes perfect sense.
So I redid my plots with the parabola that interpolates log C(n, r) at 0, n/2, and n. This also gives a very good fit, but not as good!
But that’s not a fair comparison because it’s comparing the best (least squares) elliptical fit to a convenient parabolic fit.
So I redid my plots again with the least squares parabolic fit. The fit was better, but still not as good as the elliptical fit.
I think the reason the ellipse fits better than the parabola has to do with the limitations of the central limit theorem. First of all, it applies to CDFs, not PDFs. Second, it applies to absolute error, not relative error. In practice, the CLT gives a good approximation in the middle but not in the tails. With all the curves mentioned above, the maximum error is in the tails.
Beyond the issue of the tails, I think there’s a perceptual issue, which is that we learn about parabolas in their convex orientation, as here:
The other thing is that a circle or an ellipse is finite and a parabola keeps going forever. So, the very fact that this graph stops makes it look less parabola-like, as compared to the sort of graph you might make where you can visually follow the curve off the edge of the graph.
The Ramanujan principle
Also I wanted to connect Cook’s point, that a table of numbers expressed in positional notation is approximately a graph of their logarithms, to the Ramanujan principle:
Tables are commonly read as crude graphs: what you notice in a table of numbers is (a) the minus signs, and thus which values are positive and which are negative, and (b) the length of each number, that is, its order of magnitude.
The name of the principle comes from a famous story of the mathematician Srinivasa Ramanujan supposedly conjecturing the asymptotic form of the partition function based on a look at a table of the first several partition numbers: he was essentially looking at a graph on the logarithmic scale.
Since they’re both conic sections, I would consider the parabola to be simply an extreme case of an ellipse. And a parabola is a good approximation of an ellipse at any point on the ellipse.
Visually, if I wanted to distinguish a parabola cut off at zero, from a half ellipse – I’d look at the edges. A parabola will have a finite slope there, while the ellipse will turn vertical. So this looks like a parabola.
That said, using Stirling’s approximation you can see that
ln C(n,r) ~= n ln(n) – r ln(r) – (n-r) ln(n-r)
which is neither a parabola nor an ellipse.
Robert:
Regarding your second paragraph: It’s not a half ellipse; it’s less than half an ellipse. So you won’t expect a vertical slope at the edges.
Regarding your third paragraph: The binomial density is approximately normal, and the logarithm of the normal density is quadratic, which is why you’d expect the curve be approximately parabolic. But, as Cook notes, the approximation is not so good in the tails, where absolute errors are magnified on the logarithmic scale.
If you apply the transformation r = n ( 1/2 + x ) and expand that function around x=0 you will get a first-order approximation of the form A – B x^2.
Of course that’s just an approximation valid for small values of x and the curve extends from x=-1/2 to x=1/2 which are not that small. The next order correction is quite large – within an order of magnitude – and we know that the true value diverges at those points.
I wouldn’t say that “the binomial distribution is asymptotically normal” when the normal approximation is never good far from the center (even though it’s true that the probability of that “far from the center” region vanishes asymptotically).
Anyway, given that it stays within the parabola – and in a bounded domain – it’s not really surprising that an ellipse can provide a much better fit.
> and we know that the true value diverges at those points.
Scratch that – it’s zero.
Zero is an infinite divergence on the log scale.
It’s zero as in “the logarithm of the first binomial coefficient which is one”.
> we learn about parabolas in their convex orientation
Some people learn about parabolas in the context of throwing stones, launching rockets and ballistic trajectories of projectiles in general.
Carlos:
Fair enough; indeed I shared such an example just yesterday!
With the transformation r = n ( 1/2 + x ) I mentioned above ln C(n,r) / n becomes (for large n) equal to – (1/2+x) ln (1/2+x) – (1/2-x) ln (1/2-x) where x is in the interval [-1/2 1/2].
Minimising the area between that curve and an ellipse (restricted to the upper half plane) one can find a very good fit, much better than the parabola corresponding to the quadratic approximation.
https://imgur.com/a/bl4w6L0
(It may be the same solution given in the original link but I can’t make sense of the parameters b and y0 given there which seem off by an order of magnitude compared to the values in the chart.)