How bounds are computed

Some numbers are hard to pin down exactly. Take \(\pi\) — the ratio of a circle's circumference to its diameter. You cannot write it out; its digits never end. But you do not always need the exact value. Very often it is enough to say: whatever \(\pi\) is, it is bigger than this and smaller than that. Those two numbers are a lower and an upper bound, and together they build a fence the true value is trapped inside.

The beautiful part is that you can compute such a fence for a number you cannot compute directly — and then squeeze it as tight as you like. Archimedes did exactly this over two thousand years ago. Draw a many-sided polygon inside the circle: its perimeter is a bit short of the circle, so it gives a lower bound. Draw one around the circle: its perimeter overshoots, giving an upper bound. Add more sides and both close in on the truth.

Drag the slider. You are not looking up \(\pi\) — you are manufacturing a guarantee about it, and watching the guarantee get sharper.

Here is the move that powers almost every upper bound you will ever meet. Suppose you want to bound a sum but the terms are awkward. Replace each term by something larger and easier. If every new piece is at least as big as the old one, the new total must be at least as big as the old total. So the messy sum is \(\le\) the tidy sum — a guaranteed upper bound. (Flip every inequality and the same move gives a lower bound.)

Let us try it on \(\displaystyle\sum_{k=1}^{n}\frac{1}{k^2} = 1 + \tfrac14 + \tfrac19 + \cdots\). The crudest possible replacement: every term is at most the biggest term, which is the first one, \(1\). Round every bar up to that height. The sum is now trapped under \(n\cdot 1 = n\).

Press the button and watch it happen. The rounded bars sit above the true bars everywhere — so their total is a real, honest upper bound. It is also, frankly, terrible: as \(n\) grows it races off to infinity while the true sum barely moves. That gap is the lesson. The move is always valid; the art is choosing a replacement that is both easy and tight. Step 3 makes the clever choice.

Same sum, smarter swap. For \(k\ge 2\), compare \(1/k^2\) with \(\dfrac{1}{k(k-1)}\). Since \(k(k-1) < k^2\), the second fraction is larger — so it is a legal upper replacement. Why bother? Because it splits into a difference:

\[ \frac{1}{k(k-1)} = \frac{1}{k-1} - \frac{1}{k}. \]

Now picture each replacement as a segment on a number line, stretching from \(1/k\) up to \(1/(k-1)\). Its length is exactly that difference. Line them up: the segment for \(k=2\) is \([\tfrac12, 1]\), for \(k=3\) it is \([\tfrac13,\tfrac12]\), and so on. Each one starts where the last ended — they tile the interval from \(1/n\) all the way to \(1\) with no gaps and no overlaps. The endpoints cancel in a chain (this cancelling is called telescoping), and the total length is simply the whole span: \(1 - \tfrac{1}{n}\).

Build the picture stage by stage. The blue segments are the tiling; the green shows each true term \(1/k^2\) nestled inside its segment. Since every green fits inside its blue, the true sum is at most the total blue length, which is under \(1\). Add back the one term we set aside (\(k=1\), worth \(1\)) and the entire infinite sum is fenced under 2.

Sometimes the cleverest replacement is not another sum — it is an integral. The harmonic sum \(H_n = 1 + \tfrac12 + \tfrac13 + \cdots + \tfrac1n\) has no tidy closed form, but its terms trace the curve \(y = 1/x\). So draw each term as a rectangle of width \(1\) and height \(1/k\). The sum becomes a staircase of area \(H_n\), and we can trap that staircase between two copies of the smooth area under the curve — which we can compute, because \(\int 1/x\,dx = \ln x\).

The direction is the whole game, so go slowly. Because \(1/x\) is decreasing, sliding each rectangle one step to the right drops it under the curve; sliding it left lifts it above. That single fact hands you both fences:

• Line the bars up so each sits above the curve (height \(1/k\) on \([k,k+1]\)). Their area \(H_n\) exceeds the area under the curve from \(1\) to \(n{+}1\): so \(H_n > \ln(n{+}1)\) — a lower fence.
• Line them up to sit below the curve instead. Now their area \(H_n - 1\) is less than the area from \(1\) to \(n\): so \(H_n < 1 + \ln n\) — an upper fence.

Step through the stages and read the fence off the picture. The same curve, approached from above and from below, sandwiches a sum that has no formula of its own.

The move is not just for sums. Here is a question about chance: if a non-negative quantity has average value \(\mu\), how much of it can pile up far out at value \(a\) or beyond? Intuition says: not much, because anything sitting way out there is expensive — it drags the average up. Let us turn that intuition into a computed bound with the exact same replace-and-keep-direction move.

Replace the quantity \(X\) with a cruder stand-in: the step function that is \(a\) whenever \(X \ge a\), and \(0\) otherwise. Since \(X\) is non-negative, \(X\) is always at least this stand-in. Taking averages (which preserves \(\ge\)) gives \(\mu = \mathbb{E}[X] \ge a\cdot\mathbb{P}(X\ge a)\), and dividing by \(a\):

\[ \mathbb{P}(X \ge a) \;\le\; \frac{\mathbb{E}[X]}{a}. \]

That is Markov's inequality. Now feel why it cannot be beaten. In the widget the average is held fixed at a budget of \(\mu = 1\). You slide where a lump of probability mass sits; to keep the average fixed, pushing the lump out to distance \(x\) means you can only afford a fraction \(1/x\) of it there (the rest falls back to \(0\)).

Try to make the tail \(\mathbb{P}(X\ge a)\) as large as you can. You will discover you cannot lift it past the dashed ceiling \(\mu/a\) — and it touches that ceiling only when the lump sits exactly at \(a\). Push farther out and the budget forces the lump to shrink; pull it in and it stops counting. The bound is tight, and the widget lets you bump into the reason.

Here is a bound worth a whole field. In a probabilistic model you have things you can see (data \(x\)) and hidden things you cannot (latent variables \(z\) — a cause, a cluster label, a compressed code). To score how well the model explains the data you want the evidence \(p(x)\): the probability of the data with every possible hidden \(z\) summed out.

\[ p(x) = \int p(x,z)\,dz. \]

That integral is the wall. For any interesting model it ranges over a huge or continuous space of hidden values and cannot be computed. This is exactly the situation from Step 1 — a number you cannot evaluate directly — so we do the same thing: build a computable fence. The ELBO is the floor.

Bring in a guess, then use one inequality

Invent any distribution \(q(z)\) over the hidden variable — your guess at where \(z\) probably is. Multiply and divide by it, which turns the integral into an average over your own guess:

\[ \log p(x) = \log \int q(z)\,\frac{p(x,z)}{q(z)}\,dz = \log \, \mathbb{E}_{q}\!\left[\frac{p(x,z)}{q(z)}\right]. \]

Now the one new tool. The logarithm is concave — it bends downward, so any chord joining two points on the curve lies below it. A quick consequence, called Jensen's inequality: taking the log of an average is at least the average of the logs, \(\log \mathbb{E}[Y] \ge \mathbb{E}[\log Y]\). The curvature only ever helps you in this one direction — which is precisely what makes it a bound. Apply it:

\[ \log p(x) \;\ge\; \mathbb{E}_{q}\!\left[\log \frac{p(x,z)}{q(z)}\right] \;=\; \underbrace{\mathbb{E}_{q}\!\big[\log p(x,z)\big] - \mathbb{E}_{q}\!\big[\log q(z)\big]}_{\textstyle \text{the ELBO}}. \]

Look at what happened: the intractable integral became an expectation under \(q\), a distribution we chose to be easy. Every piece on the right is computable. That is the whole trick — the same replace-in-a-known-direction move as telescoping and Markov, now powered by the concavity of the log. The name says it: the Evidence Lower BOund.

How loose is the fence? Exactly KL

A bound is only as good as its slack, so measure it. The gap between the true evidence and the ELBO turns out to be an exact, familiar quantity — the Kullback–Leibler divergence from your guess \(q\) to the true posterior \(p(z\mid x)\), a measure of how different two distributions are (always \(\ge 0\), and \(0\) only when they match):

\[ \log p(x) - \text{ELBO}(q) \;=\; \mathrm{KL}\big(q(z)\,\big\|\,p(z\mid x)\big) \;\ge\; 0. \]

So — just like Markov's ceiling in Step 5 — the bound is tight exactly when your guess is right: when \(q\) equals the true posterior, the slack vanishes and the ELBO equals the evidence. And it hands you a free algorithm: since \(\log p(x)\) is a fixed ceiling, raising the ELBO can only mean shrinking the KL — pushing your guess toward the truth. Maximizing a computable lower bound quietly does inference for you.

Feel it below. The model is fully worked out (Gaussian prior, one noisy observation \(x=2\)), so the true posterior — the green target — is known. Drag your guess \(q\) (blue). Watch the ELBO climb toward the fixed evidence ceiling, the gold KL-gap close, and the bound snap tight the instant blue lands on green.