Averaging down the triangle

Pascal’s triangle is built by one rule: every entry is the sum of the two above it. Read as a grid of streets, that rule counts routes, and every identity between the entries becomes a statement about walking. Read modulo a prime, it becomes a question about digits.

Change the rule slightly. Instead of adding the two entries above, take a fixed share of each — $1 - t$ of the one on the left and $t$ of the one on the right, for some $t$ between nought and one. The sum becomes an average, and the triangle becomes a machine for averaging.

Averaging down the triangle turns a polygon into a curve, and a function’s samples into a polynomial that approaches the function. Both are the same computation, and both inherit one property from the weights being shares: the result can never overshoot what it averages. That property is what makes the method safe, and it is also what makes it slow.

The rule with its parents weighted #

The construction in the figure is due to Paul de Casteljau, who worked it out at Citroën in 1959. Start with a row of points. Replace each neighbouring pair by the point $t$ of the way from the first to the second. That gives a row one shorter; do it again, and again, until one point is left.

Every step is Pascal’s rule with weights. So the last point is some mixture of the control points, and the amount of each control point in it can be found the way the routes were counted. A route from the top of the triangle to control point $P_k$ takes $n$ steps, $k$ of them towards the right parent and $n - k$ towards the left; each right step multiplies the weight by $t$ and each left step by $1-t$. There are $\binom{n}{k}$ such routes, each carrying $t^k (1-t)^{n-k}$, so

$$\text{weight on } P_k = \binom{n}{k}\, t^k (1-t)^{n-k}.$$

The count of routes is still there; each route has simply acquired a price. At $t = 0.4$ with four control points the prices are $0.6^3$, $0.4 \times 0.6^2$, $0.4^2 \times 0.6$ and $0.4^3$, the counts are 1, 3, 3 and 1, and the weights are 0.216, 0.432, 0.288 and 0.064. The figure computes them twice — once by pushing a weight of one down the weighted triangle, once from the formula — and requires the averaged point to equal the weighted sum.

The weights add to one, and the reason is the binomial theorem: they are the terms of $\big((1-t) + t\big)^n$, which is $1^n$. The unweighted triangle’s rows add to $2^n$ for the same reason with $1 + 1$ in the brackets.

A row spread over the interval #

Let $t$ run from nought to one and each weight becomes a polynomial. The $n+1$ polynomials $\binom{n}{k} x^k (1-x)^{n-k}$ are the Bernstein basis of degree $n$, and they are row $n$ of the triangle laid out along an interval.

Three facts about the row are visible and each is checked. The polynomial for $k$ peaks at $x = k/n$: setting its derivative to nought gives $k(1-x) = (n-k)x$. Each encloses exactly $1/(n+1)$, whatever $k$ is. And they add to one everywhere.

The second fact has a proof that uses no integration. Scatter $n + 1$ points independently and uniformly on the interval, and colour one of them red. The integral $\int_0^1 \binom{n}{k} x^k (1-x)^{n-k}\,dx$ is the chance that exactly $k$ of the other $n$ points land to the left of the red one: the red point sits at $x$, and each of the others falls left of it with chance $x$. But the $n + 1$ points are exchangeable, so the red one is equally likely to be first, second, or any of the $n + 1$ positions in order. Every $k$ has chance $1/(n+1)$, so every curve encloses the same area. Thomas Bayes used the same argument, with a ball rolled on a table, in the essay published after his death in 1763.

So a row of the triangle is a partition of one into $n+1$ smooth pieces, each concentrated near its own point $k/n$ and each carrying the same total. That is exactly what is needed to average something that lives on the interval.

Why the curve cannot leave its polygon #

The curve in the first figure is the set of points de Casteljau’s construction produces as $t$ runs from nought to one. Its formula is $\sum_k \binom{n}{k} t^k (1-t)^{n-k} P_k$, and since the weights are never negative and always add to one, every point of the curve is a weighted average of the control points, and so lies inside their convex hull. The figure checks that for 121 points along the curve.

That is the property that made the curves useful. Pierre Bézier, independently at Renault in the early 1960s, used them to describe car bodies: a designer moves the control points, the curve follows without ever swinging outside the polygon they make, and the curve’s ends start at $P_0$ and finish at $P_n$ heading along the first and last sides. A point inside the hull of many points is inside the hull of a few, and a curve built from positive weights inherits the whole family of such statements.

Almost every curved outline on a screen is drawn this way. Letterforms in the TrueType format are pieces of quadratic curves, three control points each; those in PostScript fonts, and the C command in an SVG path, are cubic, with four. Rendering one is the construction in the figure run at many values of $t$ — a few multiplications and additions per round, no powers, no binomial coefficients, and no rounding error that can push a point outside the hull, because every intermediate point is itself an average.

Sampling a function instead of a polygon #

Replace the control points by the values of a function at the evenly spaced points $0, 1/n, 2/n, \dots, 1$, and average them with the same weights:

$$B_n f(x) = \sum_{k=0}^{n} f\!\left(\frac{k}{n}\right) \binom{n}{k} x^k (1-x)^{n-k}.$$

This is the Bernstein polynomial of $f$, and it has a reading that explains everything about it. The weights are the binomial distribution. Toss $n$ coins that each land heads with probability $x$; the chance of exactly $k$ heads is $\binom{n}{k} x^k (1-x)^{n-k}$. So $B_n f(x)$ is the average value of $f$ at the proportion of heads — and the proportion of heads, for large $n$, crowds around $x$.

For $x^2$ the gap can be computed exactly. The average of the squared proportion is the square of its average plus its variance, and the variance of the proportion of heads in $n$ tosses is $x(1-x)/n$. So

$$B_n(x^2) = x^2 + \frac{x(1-x)}{n},$$

and the figure checks that identity at all 241 of its points. The largest gap is at $x = \tfrac12$ and is $1/(4n)$: 0.125 at degree 2, 0.031 at degree 8, 0.0078 at degree 32. The polynomial always lies above the curve, and the reason is general: for any function that bends upward, the average of its values exceeds its value at the average — the chord lies above the curve — and $B_n f(x)$ is an average of $f$ over a distribution whose mean is $x$.

The same fact is why the method does not interpolate. A Bernstein polynomial agrees with its function only at the two ends; everywhere else it is a blur of nearby samples. That looks like a defect and is actually the source of the theorem below.

What the averages keep: order and bending #

A blur loses detail, but this particular blur keeps two things exactly, and both come from the triangle.

Differentiate a Bernstein polynomial and the triangle’s previous row appears. The derivative of $B_n f$ is

$$n \sum_{k=0}^{n-1} \left[ f\!\left(\tfrac{k+1}{n}\right) - f\!\left(\tfrac{k}{n}\right) \right] \binom{n-1}{k} x^k (1-x)^{n-1-k},$$

the differences between neighbouring samples, averaged with the weights of row $n-1$. So if the samples rise from left to right, every difference is positive, every weight is positive, and the derivative is positive everywhere: a function that only increases has a Bernstein polynomial that only increases. The same computation one level further down averages the second differences with row $n-2$, so a function whose samples bend upward has a polynomial that bends upward everywhere.

That is a property most ways of fitting a polynomial do not have. The polynomial through evenly spaced samples of an increasing function can wiggle down between them, and a least-squares fit can put a bump where the data has none. An averaging rule cannot invent a turning point, because at every $x$ it is a positive combination of the slopes the samples already have. For a designer that is the difference between a curve that follows the control polygon’s intentions and one that has ideas of its own; for a numerical analyst it is the reason Bernstein polynomials are used to prove that shape-preserving approximation is possible at all.

The derivative formula also says the derivatives converge. When $f$ has a continuous derivative, the differences divided by $1/n$ are samples of that derivative, and the same law-of-large-numbers argument applied to them shows that the slope of $B_n f$ approaches the slope of $f$ uniformly. A single sequence of polynomials approximates the function and, at the same time, its slope.

Every continuous function, by tossing coins #

In 1885 Karl Weierstrass proved that every continuous function on a closed interval can be approximated, uniformly, as closely as desired by a polynomial. In 1912 Sergei Bernstein gave a proof in half a page, and the polynomial it uses is $B_n f$.

The argument splits the average in two. Where the proportion of heads is close to $x$, $f$ at the proportion is close to $f(x)$, because a continuous function on a closed interval changes by little over short distances — by at most some $\varepsilon$ over any distance less than some $\delta$, the same $\delta$ everywhere. Where the proportion is far from $x$, $f$ can be anything up to its largest size, but Chebyshev’s inequality says the chance of being that far away is at most $x(1-x)/(n\delta^2)$, which is at most $1/(4n\delta^2)$ whatever $x$ is. Make $n$ large enough and the second part is smaller than $\varepsilon$ too.

Both bounds hold at every $x$ simultaneously, which is what makes the convergence uniform — the gap measured as the largest distance anywhere, not point by point. The proof is the law of large numbers, applied to a coin whose bias is the point being approximated.

The proof asks for continuity and nothing more, and a function with a corner shows what that minimum buys. At $x = \tfrac12$ the polynomial is the average distance of the proportion of heads from one half, and the proportion’s spread is $1/(2\sqrt n)$. The average distance from the centre of a bell curve is its spread times $\sqrt{2/\pi}$, so the gap is about $0.399/\sqrt n$ — to halve it takes four times the degree. The figure’s third column is the gap times $\sqrt n$, and it settles at exactly that constant.

Smoothness buys nothing past one over n #

A corner costs a square root. The natural expectation is that a smooth function does much better — that for a function with every derivative, the gap should fall faster and faster, as it does for a Taylor series inside its radius.

It does not. The gap times the degree settles to a constant instead of falling, so the gap itself shrinks only like $1/n$, the same rate as for $x^2$. For every function with a second derivative, $n$ times the gap tends to $x(1-x)f''(x)/2$ — Elizaveta Voronovskaya’s theorem of 1932 — and that limit is nought only where the function is straight. The converse is also known: a Bernstein polynomial whose largest gap falls faster than $1/n$ belongs to a straight line. Infinitely many derivatives do not help, because the method never uses any of them.

The reason is the blur. $B_n f(x)$ averages $f$ over a spread of width about $1/\sqrt n$ around $x$; averaging a curved function over a spread of that width misses its value by its curvature times the square of the width, which is $1/n$. The positive weights that keep the curve inside its polygon are the same weights that smear the function, and a smear of positive weights cannot cancel curvature — cancelling would need some weights to be negative.

The rate, measured #

On logarithmic scales a rate of $1/n$ is a line of slope $-1$ and a rate of $1/\sqrt n$ a line of slope $-\tfrac12$, and the figure’s lines are those. $x^2$ lies exactly on its line from the first degree. The sine joins it after a few doublings. The corner runs parallel at half the slope.

The fourth line is the function that defeats interpolation at evenly spaced points. There, the polynomial through 41 equally spaced samples of it missed by more than six. Here the error at degree 512 is 0.043 and falling. Bernstein polynomials never diverge — every one of them lies between the function’s smallest and largest sample values — but for Runge’s function they are still far from their eventual slope of $-1$ at degree 512, because its curvature at the centre is large and the constant in front of $1/n$ is correspondingly big.

That is the trade in one figure. Interpolation at the right points converges geometrically for a function like this, adding a fixed number of correct digits per doubling. Bernstein’s averaging converges for every continuous function without exception and never overshoots, and it pays for that with a rate that is never better than $1/n$. A method that cannot go wrong has given up the means of going fast.

Where the construction needs its hypotheses #

The function has to be continuous on a closed interval. Bernstein’s proof uses the fact that a single $\delta$ works everywhere, which fails on an open interval — $\sin(1/x)$ near nought has no such $\delta$ — and fails for a function with a jump, where the polynomials converge to the midpoint of the jump rather than to either side.

The samples are at evenly spaced points, and they must be. The binomial distribution with mean $x$ is what makes the average centre on $x$; move the samples and the weights no longer average towards the right place.

The weights must be positive. Every good property here — the hull, the absence of overshoot, convergence for every continuous function — comes from the weights being shares. Every limitation — the $1/n$ floor, the failure to interpolate — comes from the same place.

And a Bernstein curve is a polynomial. No polynomial curve traces an exact circle, so a circle drawn from control points needs a further step: weights attached to the control points themselves, which makes the curve a ratio of two polynomials.

The rate is measured to degree 512 and proved beyond it #

The largest gap in every figure is found on a grid of 1,001 points. For $x^2$ and for the corner the largest gap sits at $x = \tfrac12$, which is on the grid, so the values are exact; for the sine and Runge’s function it sits between grid points, and the value shown is a lower bound that is accurate to within the grid spacing times the slope there.

The rate figure stops at degree 512. The slopes over the last three doublings are measurements, and a measured slope of −0.81 for Runge’s function is a statement about degrees 128 to 512, not about the limit; that the limit is −1 is Voronovskaya’s theorem and not something the figure shows.

And the first figure shows the construction at one value of $t$. The curve is drawn from 121 values, each computed by the same rounds of averaging, but only one set of rounds is drawn — the picture of all of them would be a triangle of triangles, and no single one of its lines would be readable.

Still open: the best a polynomial can do at a corner #

Bernstein’s own polynomials approach $|x - \tfrac12|$ like $0.399/\sqrt n$. They are far from the best polynomials of the same degree, which are not averages and are allowed negative weights in effect. Bernstein himself studied that best approximation: for $|x|$ on the interval from $-1$ to $1$, the smallest possible largest gap for a polynomial of degree $2n$ behaves like $\beta/(2n)$ for a constant $\beta$ near 0.2802.

He conjectured in 1914 that $\beta$ is $1/(2\sqrt\pi) = 0.28209\ldots$, a guess that agreed with his numerical evidence to two figures. Richard Varga and Amos Carpenter showed in 1985, by computing the best approximations to high degree with great precision, that it is not: $\beta = 0.28016\ldots$. No closed form for it is known, nor any proof that it is related to any other constant. So the rate at which the best possible polynomials approach the simplest possible corner is a number known to many digits and to no formula.

Safety and speed are bought with the same weights #

The habit worth keeping is about properties that come as a pair.

Weighted averaging down the triangle has a property that is easy to admire: whatever it is given, its output stays within the range of its input — inside the hull of a polygon, between the smallest and largest sample of a function. That is why designers could trust the curves and why Bernstein’s proof works for every continuous function. It is tempting to treat that property as a free benefit and the slow rate as a separate flaw. It is not separate. A rule that can never overshoot has to average, an average over a spread cannot recover curvature, and so the $1/n$ floor is the price of the guarantee rather than a defect alongside it.

When a method has a strong guarantee and a disappointing rate, look for the single choice responsible for both. Here it is the positivity of the weights, and every faster method of approximation — interpolation at well-chosen points, the best approximation Bernstein studied — gets its speed by giving the guarantee up.