A coin in front of every term

The harmonic terms $1, \tfrac12, \tfrac13, \dots$ have been added two ways so far. With every sign a plus they diverge, slowly but past every number. With the signs alternating they converge to $\log 2$, and rearranging those same terms can make them converge to anything at all. Both sign patterns were chosen. The question here is what happens when nobody chooses — when a fair coin is tossed for each term, heads for plus and tails for minus.

The answer is not obvious in advance. A random sign pattern will have long runs of plus signs, and a run of plus signs on the harmonic terms is exactly what makes them diverge. It will also have long runs of minus signs. Whether the runs cancel well enough, and what the sum does if they do, is a question about the balance between how fast the terms shrink and how badly a coin can misbehave.

Every run settles. The first few terms throw each one around — a term of size one half or one third moves the sum a long way — and by a hundred terms each run is creeping along at nearly constant height. The heights differ from run to run, which is the second thing the picture says: the random sum converges, and its limit is itself random. There is no single answer, only a distribution of answers.

Why random signs cancel well enough #

The all-plus sum grows like $\log n$ because the terms add without cancellation, and $\sum 1/k$ over $k$ up to $n$ is about $\log n$. With random signs the terms partly cancel, and the question is how much.

A bell curve assembled out of coin flips measured exactly this for terms of equal size: a sum of $n$ random signs has typical size $\sqrt n$, not $n$, because the variance of a sum of independent pieces is the sum of their variances. The same rule applies to unequal pieces. The term $\pm 1/k$ has variance $1/k^2$, so the variance of the whole random sum is

$$1 + \frac14 + \frac19 + \frac1{16} + \dots = \frac{\pi^2}{6},$$

finite, although the sum of the terms themselves is infinite. That is the whole reason the random series converges. Cancellation by random signs replaces the terms by their squares, and the squares of the harmonic terms add up to something finite even though the terms do not. The variance still left after the first $N$ terms is about $1/N$, so the sum’s wobbling beyond that point shrinks towards nothing; this was proved for this kind of series by Hans Rademacher in 1922 and put into general form by Andrei Kolmogorov a few years later.

The number $\pi^2/6$ is also the variance of the limit, so the limits have a standard deviation of about $1.28$. That matches the spread of the twelve runs in the figure, most of which end within about $1.3$ of zero.

The same arithmetic says how slowly a random run settles. After $N$ terms the unsettled remainder has standard deviation about $1/\sqrt N$, so pinning a random limit down to three decimal places takes around a million terms. The alternating series, whose signs are chosen to cancel as well as possible, is within $1/(2N)$ of $\log 2$ after $N$ terms and needs only about five hundred for the same accuracy. Random cancellation is enough for convergence and much worse than deliberate cancellation at achieving it, which is the difference between the settling runs in the figure and the flat dashed line among them.

The threshold moves from one to one half #

That argument does not care that the terms are $1/k$; it cares only that their squares add up to something finite. So it predicts where the boundary between convergence and divergence sits for terms $1/k^p$ with random signs.

With plus signs throughout, $\sum 1/k^p$ converges exactly when $p > 1$. With random signs, the variance $\sum 1/k^{2p}$ is finite exactly when $p > \tfrac12$, and the random series converges exactly when $p > \tfrac12$. Below that the variance grows without bound and the random sum wanders forever, never settling; Kolmogorov’s three-series theorem makes that a certainty rather than a tendency. At $p = \tfrac12$ exactly the variance is the harmonic sum itself, which grows like $\log n$, so the runs drift like $\sqrt{\log n}$ — the slowest possible way of not converging, and in the figure hard to tell from convergence.

The threshold has halved, and the reason is the square root in the size of a random walk. Terms of size $1/\sqrt k$ with random signs behave like a random walk whose steps shrink just fast enough to keep it from ever settling. Shrink them a little faster and it settles; a little slower and it wanders. The line between the two is exactly where fixed signs would already have been hopeless.

The coin is a single number in disguise #

A sequence of fair coin tosses has an exact deterministic stand-in: the binary digits of a number chosen uniformly between 0 and 1. Its first digit is 0 or 1 with equal chance, its second likewise, independently, and so on. So the random harmonic sum can be written as an ordinary function of one number $x$: read the $k$-th binary digit of $x$, and give the $k$-th term a plus sign if the digit is 0 and a minus sign if it is 1.

The graph is a single jagged, self-similar function. The largest value is at $x = 0$, where every digit is 0 and every sign plus. The alternating series lives at $x = \tfrac13$, whose binary expansion is $0.010101\ldots$ — plus, minus, plus, minus. The limit exists for every $x$ except a set of total length zero, which is what “the random sum converges with probability one” means in this language, and the question “how likely is the sum to land between $a$ and $b$” becomes “what total length of $x$ gives a value between $a$ and $b$”.

This rewriting is due to Hugo Steinhaus in the 1920s and 1930s, and it is the same idea the orbit written as a word used to turn a dynamical system into a sequence of letters. Probability disappears entirely: a fair coin becomes a uniform point, independence becomes the arithmetic of binary digits, and a statement about random sums becomes a statement about one function and the lengths of the sets where it takes each value.

Where the sum lands #

The distribution of the limit can be computed exactly, by a route that avoids simulation altogether.

The characteristic function of a random variable — the average of $\cos(tX)$ — turns sums of independent pieces into products. The sign $\pm 1/k$ contributes the factor $\cos(t/k)$, so the random harmonic sum has characteristic function

$$\varphi(t) = \cos(t)\cos\!\left(\tfrac t2\right)\cos\!\left(\tfrac t3\right)\cdots,$$

a product of cosines that converges because $\cos(t/k)$ is close to $1 - t^2/2k^2$ for large $k$. From $\varphi$ the density follows by Fourier inversion, the same operation that assembles a square wave out of round ones, run in the other direction.

The histogram of simulated sums and the curve from the product of cosines are separate computations, and they agree. The shape has a broad flat top — the density barely changes between $-1$ and $1$ — and then falls steeply on both sides. Two values stand out. At the centre the density is $0.2499944$, which looks like a quarter until the sixth decimal place. At $\pm 2$ it is $0.125$, to every digit a double-precision computation can produce.

Byron Schmuland computed it to many more digits in 2003 and found that it is not one eighth. It agrees with $\tfrac18$ to forty-two decimal places and then differs. The near-miss at the centre, in the sixth place, is at least visible; the near-miss at 2 is not visible to any computation of ordinary precision, and a reader who trusted fifteen digits would conclude, wrongly, that the density there is exactly one eighth.

A tail thinner than any bell’s #

Its variance is $\pi^2/6$, and a sum of many small independent pieces usually looks like a bell curve. Near the middle the random harmonic sum does look like one. Far out it does not, and the difference is dramatic.

The reason is that the sum is not made of many small pieces. Its first few terms are large — one, a half, a third — and the only way to reach a value like 4 is for many of them to carry the same sign. The all-plus sum reaches 4 after 31 terms, as the sum that steps over every whole number counted, so landing near 4 needs roughly the first thirty signs to agree, and the chance of that is around $2^{-30}$. Reaching 5 needs the first eighty or so, 6 needs two hundred and more: the number of signs that must cooperate grows exponentially with the target, so the probability of reaching it falls doubly exponentially. A normal curve’s tail falls like $e^{-x^2/2\sigma^2}$, which is fast; this one falls like the exponential of an exponential, which is far faster.

This is the precise sense in which the random harmonic sum is not a bell curve. The central limit theorem needs every piece to be negligible compared with the total, and here the first piece alone is the size of the standard deviation. The tail is not a bell found the opposite failure — tails far heavier than normal — when a sum was dominated by rare huge terms. Here the terms are fixed in size and the tail is lighter than normal, because the largest pieces are few and a coin must line them all up.

Signs chosen by a rule instead #

The coin replaced a choice of signs by a distribution of choices. Going back the other way — choosing the signs by some rule — shows what the coin was doing and how special it is to land on a particular number.

A repeating pattern converges exactly when it adds to nothing over one period. With the signs $+, +, -, -$ repeating, each block of four terms is $\tfrac1{4j+1} + \tfrac1{4j+2} - \tfrac1{4j+3} - \tfrac1{4j+4}$, which shrinks like $1/j^2$, and the series converges — to $\tfrac\pi4 + \tfrac12\log 2 = 1.1320$, as it happens, a value that mixes the constants of the alternating series and of the series 1 − 1/3 + 1/5 − … for π/4, each of which the pattern contains. With $+, +, -$ repeating, each block leaves over about $\tfrac1{3j}$, and the leftovers add like a third of the harmonic series: divergence, like $\tfrac13\log n$. A periodic pattern with any surplus of plus signs over a period behaves like that surplus times the harmonic series. The coin never commits to a surplus, which is why it converges.

The primes choose a pattern that lands exactly on zero. Give the $n$-th term the sign of the Möbius function: plus if $n$ is a product of an even number of distinct primes, minus for an odd number, and drop the term if $n$ has a repeated prime factor. The sum

$$1 - \frac12 - \frac13 - \frac15 + \frac16 - \frac17 + \frac1{10} - \cdots$$

has partial sums $0.031$ after a hundred terms, $0.0044$ after a thousand, $-0.0021$ after ten thousand and $-0.00049$ after a hundred thousand, and it converges to exactly $0$. Hans von Mangoldt proved that in 1897, and Edmund Landau showed that the statement is equivalent to the prime number theorem — the fact that the primes up to $x$ number about $x/\log x$.

Seen against the figures above, that is remarkable. A sign pattern chosen by a fair coin lands at zero with probability zero; the density there is about a quarter per unit length, so a random sum lands within a thousandth of zero about one time in two thousand, and exactly at zero never. The Möbius signs look random in many statistical respects — that impression is a whole research programme — and yet they conspire to land the sum precisely on zero, and proving that they do is as hard as counting the primes.

Rearrangements are a different kind of choice. Riemann’s theorem reaches any target by choosing the order of fixed signs, spending positive terms until the sum passes the target and negative terms until it comes back. That needs both kinds of term to have infinite sum on their own — which is exactly what happens when the terms are $\pm 1/k$ with infinitely many of each. Random signs supply infinitely many of each almost surely, so a random sign pattern, reordered, can also be made to converge to anything; left in its natural order it converges to its own random limit. The coin decided the signs and the order decided the sum, and the two decisions are separate.

What the pictures cannot show #

The limit itself, for any particular run. Each coloured run in the first figure is drawn for four hundred terms. Its final value is not its limit; the terms beyond still move it, by an amount with standard deviation about $1/\sqrt{400} = 0.05$. The runs have settled to the eye, not to the number, and no finite drawing can show the limit of a series that converges this slowly.

The forty-second decimal. The density figure prints the value at 2 to twelve places and states the rest. A double-precision Fourier inversion cannot resolve a difference of $10^{-42}$; that comes from Schmuland’s high-precision computation and from his analysis of why it is so small, not from anything drawn here.

The shape of the jagged function in full. The function of $x$ is drawn with fourteen binary digits, so it has $2^{14}$ steps. The true function uses all the digits and is defined only almost everywhere — at a set of $x$ of total length zero its series diverges, and near such points the graph has spikes no drawing at any resolution can contain.

Why the value at 2 is almost exactly an eighth #

The near-miss at 2 has an explanation, and it is short enough to give. Split the sum into its first two terms and the rest: $S = \pm 1 \pm \tfrac12 + T$, where $T = \pm\tfrac13 \pm \tfrac14 \pm \cdots$. The first two signs put $S$ in one of four bands, centred at $-\tfrac32$, $-\tfrac12$, $\tfrac12$ and $\tfrac32$, each with chance one quarter, and $T$ spreads each band out. So the density at 2 is a quarter of the density of $T$ at four points, $\tfrac12$, $\tfrac32$, $\tfrac52$ and $\tfrac72$.

Now a property of $T$ that looks like a coincidence. Its characteristic function is the product of $\cos(t/k)$ for $k \ge 3$, and at $t = 2\pi m$ the factor with $k = 4m$ is $\cos(\pi/2) = 0$. So the characteristic function of $T$ vanishes at every non-zero multiple of $2\pi$, and by the Poisson summation formula that says exactly this: the copies of $T$’s density shifted by all the whole numbers add up to a perfectly flat line of height one. Folded onto an interval of length one, $T$ is exactly uniform.

Put the two facts together. By symmetry, the values of $T$’s density at $\tfrac12, \tfrac32, \tfrac52, \dots$ add up to exactly one half. The density of $S$ at 2 is a quarter of the first four of them — so it is $\tfrac18$ minus a quarter of the values at $\tfrac92, \tfrac{11}2, \dots$. For $T$ to reach $\tfrac92$ its terms from $\tfrac13$ onwards must add like the all-plus sum for a couple of hundred terms — the all-plus sum from $\tfrac13$ needs 227 terms to get there — and that is where the deficit of about $10^{-42}$ comes from. At 0 the same argument subtracts values of $T$’s density at $\tfrac52$ and beyond, which are around $10^{-5}$ — which is why the value at the centre visibly misses a quarter and the value at 2 invisibly misses an eighth. The coincidence is the term $\tfrac14$, whose cosine vanishes at $\pi/2$, and the rest is how thin the tail is.

Still open: signs on a geometric sequence #

The harmonic terms give a distribution whose density is smooth, positive everywhere and computable to any accuracy. Change the terms and much less is known. Replace $1/k$ by $\lambda^k$ for a fixed $\lambda$ between one half and one: the random sum $\sum \pm \lambda^k$ is called a Bernoulli convolution, and the question is whether its distribution has a density at all or is concentrated on a set of length zero.

Paul Erdős showed in 1939 that for some special values — $\lambda$ the reciprocal of the golden ratio is the first — it has no density: the distribution lives on a set of zero length, although it is spread over a whole interval. Boris Solomyak showed in 1995 that it does have a density for almost every $\lambda$ between one half and one, and later work has settled many specific algebraic values. For most individual values of $\lambda$, whether the random geometric sum has a density is still open, which puts one of the simplest random series imaginable beyond current methods, one change of term away from the harmonic series, whose answer is completely understood.

Randomness halves the threshold #

The harmonic series diverges with every sign positive and converges with signs alternating; with a coin for each sign it converges almost always, because random cancellation turns the terms into their squares and the squares add up to $\pi^2/6$. The price is that the answer is no longer a number but a distribution, spread with standard deviation $1.28$, flat on top, and far thinner in its tails than a bell curve because its biggest terms are few.

Read through binary digits, the same distribution is the shape of one jagged function on the unit interval, with no probability in it at all. And its height at 2 is one eighth for forty-two decimal places and then is not — a fact that no picture and no ordinary computation could have revealed, and a reminder that a number agreeing with a simple fraction to every digit anyone checked is evidence, not proof.