What not knowing the coin costs

A coin that lands heads with probability 0.6 pays even money, and the essay on Kelly’s rule settled how much of one’s wealth to stake on it: the fraction $2p - 1$, a fifth. That fraction maximises the expected logarithm of wealth, which is the growth rate a bettor who reinvests actually experiences, and it is eventually ahead of every other fixed fraction with probability one.

The rule has one input, and it is the one thing no real bettor is given. A card counter estimates the edge from the cards seen, an investor from past returns, a gambler from the coin’s history. Each of them stakes a fraction computed from an estimate, and the question this essay is about is what the estimate costs — how much growth is lost by not knowing $p$, and what a bettor who has to learn the coin should do differently from one who already knows it.

The run in the figure is an ordinary one. The bettor who knows $p$ ends with about $10^{19}$. The bettor who guessed once watched twenty tosses, saw fifteen heads, estimated $p$ as 0.75 and has staked half its wealth on every toss since. On a coin whose real chance is 0.6, that fraction has a growth rate of $0.6 \ln 1.5 + 0.4 \ln 0.5$, about $-0.034$ a toss, and after two thousand tosses the wealth is near $10^{-26}$. Nothing went wrong with the coin. The estimate was off by an amount twenty tosses make entirely ordinary, and staking it was ruinous.

The third bettor never commits to an estimate. Before each toss it recomputes the chance of heads from everything seen so far and stakes accordingly, and it ends about thirty times poorer than the bettor who knew — a factor of 33 out of a factor of $10^{19}$. The rest of this essay is about why that bettor does so well, and why its shortfall has an exact formula.

An estimate from m tosses costs half of one over m #

Start with the simplest way of not knowing. A bettor watches $m$ tosses, counts $k$ heads, estimates $\hat p = k/m$, and from then on stakes $\hat f = 2\hat p - 1$. Its growth rate per toss is $g(\hat f) = p \ln(1 + \hat f) + (1 - p)\ln(1 - \hat f)$, a random quantity because $\hat f$ is, and its expected value over the possible counts $k$ can be computed exactly by summing over the binomial distribution.

For small samples the expected growth is negative, and strongly so: the estimate is often far too large, and the growth curve falls much faster on the overbetting side than on the timid side. The curves cross nought near $m = 102$, $30$ and $15$ tosses for edges $0.1$, $0.2$ and $0.3$. After that they climb towards the growth of the bettor who knew, and the shortfall, once $m$ is moderately large, is very nearly $1/(2m)$ a toss — the same for every edge.

That number has a two-line explanation. Near its peak the growth rate is a parabola, $g(f) \approx g(f^*) - \tfrac12 \kappa (f - f^*)^2$, with curvature $\kappa = 1/(4p(1-p))$ at Kelly’s fraction. The estimated fraction misses $f^*$ by a random amount of variance $4p(1 - p)/m$, because $\hat f = 2\hat p - 1$ and the variance of $\hat p$ is $p(1 - p)/m$. The expected loss is half the curvature times the variance, and the factors $p(1 - p)$ cancel exactly:

$$\mathbb{E}\, g(\hat f) \approx g(f^*) - \frac{1}{2m}.$$

So a bettor pays half of one over the sample size, in nats a toss, whatever coin it is facing. Against that, the prize is about $\varepsilon^2/2$ for an edge $\varepsilon = 2p - 1$, which is the small-edge form of the growth rate. The prize exceeds the cost only when $m\varepsilon^2 > 1$, so a bettor needs to have seen about one over the edge squared tosses before staking its estimate is better than staking nothing at all. With a one per cent edge, that is ten thousand tosses of homework before the first bet. It is the same balance of a signal against its own noise that decides how far a sum strays from its average, read here as a growth rate.

Half Kelly is a statement about the standard error #

The figure suggests a remedy that practitioners arrived at long before anyone did the sum: stake less than the estimate says. If a bettor stakes a multiple $c$ of the estimated fraction, the same parabola gives an expected growth of about $c\varepsilon^2 - \tfrac12 c^2(\varepsilon^2 + 1/m)$, and the best multiple is

$$c^* = \frac{\varepsilon^2}{\varepsilon^2 + 1/m} = \frac{m\varepsilon^2}{1 + m\varepsilon^2}.$$

Found by a direct search over $c$ with the growth computed exactly, the optima for sixteen combinations of edge and sample size lie on that curve to within a few hundredths. Full Kelly is right only in the limit of a perfect estimate. Half Kelly is right at $m\varepsilon^2 = 1$ — that is, when one standard error of the estimated edge, $1/\sqrt m$, is as large as the edge itself. At ten tosses of a coin with a ten per cent edge the right stake is about a tenth of the estimate; at 2,500 tosses it is 96 per cent of it.

This turns a rule of thumb into a measurement. “Bet half Kelly” was the practical advice in the essay on Kelly’s rule, justified there by the smaller drawdowns it buys; here the same advice falls out of a quite different argument, as the right response to an estimate that is uncertain by as much as it is large. The formula $c^* = \varepsilon^2/(\varepsilon^2 + \sigma^2)$ is the familiar shape of shrinkage — the signal’s variance over the signal’s plus the noise’s — that appears whenever a noisy estimate is pulled toward a safe value, and it is what a Bayesian with a prior centred on no edge, of variance $\varepsilon^2$, would compute as the posterior mean.

The difficulty is that $c^*$ contains $\varepsilon$, the quantity being estimated. A bettor who knew how large the edge was would not need to shrink. The way out of the circle is to stop treating the estimate as something to be computed once and then trusted.

Learning while betting #

The third bettor of the first figure does exactly that. Before each toss it has seen $h$ heads and $t$ tails, and it estimates the chance of heads by Laplace’s rule of succession,

$$\hat p = \frac{h + 1}{h + t + 2},$$

which is the posterior mean of $p$ for a bettor whose prior made every value from nought to one equally likely — the rule that updating by Bayes’ theorem gives for a uniform start. It stakes $2\hat p - 1$, which is a stake on tails whenever the estimate falls below a half. A head then multiplies its wealth by $1 + (2\hat p - 1) = 2\hat p$, and a tail by $2(1 - \hat p)$.

Wealth is again a product of random factors, and its growth is set by the logarithms of the factors rather than by any one of them. Multiply those factors along a run and something exact happens. After $n$ tosses with $H$ heads and $T$ tails, the numerators collect into $1 \cdot 2 \cdots H$ and $1 \cdot 2 \cdots T$ whatever order the heads and tails came in, and the denominators into $2 \cdot 3 \cdots (n + 1)$. The learner’s wealth is

$$W_n = 2^n \frac{H!\, T!}{(n + 1)!}.$$

It depends on the run only through the number of heads. That already says something odd: a learner that saw all its heads first and all its tails afterwards, and so spent a long stretch staking heavily on the wrong side, ends with exactly the same wealth as one that saw them interleaved.

The learner holds every fixed bet at once #

The formula has a second reading, and it is the heart of the matter.

A bettor that staked a fixed $2q - 1$ throughout ends with $(2q)^H (2(1 - q))^T = 2^n q^H (1 - q)^T$. Average that over every $q$ from nought to one:

$$\int_0^1 2^n q^H (1 - q)^T\, dq = 2^n \frac{H!\, T!}{(n + 1)!},$$

which is Euler’s beta integral, and which is $W_n$. The bettor who learns by Laplace’s rule ends with exactly the average of the wealths of all the bettors who committed to one fraction in advance. Equivalently: split the starting stake into infinitely many equal slivers, give each sliver to a different fixed-fraction bettor, never move money between them — and the total at the end is what the learner has. The figure checks it numerically, integrating the curve to within one part in a million of the closed form.

Thomas Cover found this construction in 1991 for portfolios of many assets, and called the resulting strategy universal: it needs no knowledge of the market, and its wealth is the average of the wealths of all constant-proportion portfolios. For a single coin the average is dominated by the fractions near the peak of the curve, so the learner’s wealth is the peak — the best fixed fraction in hindsight — times the width of the peak. The width is what learning costs.

The same picture says why the guess-once bettor did so badly. It put the whole sliver on one value of $q$, chosen from twenty tosses, and that value sat far down the right side of the curve. The learner hedged across every value of $q$ and so was guaranteed to have some money on the right one.

The cost of learning is a logarithm #

The shortfall against hindsight has an exact formula too. The best fixed fraction after the fact is $2H/n - 1$, which ends with $2^n (H/n)^H (T/n)^T$, so the learner falls behind by

$$\ln \frac{W_{\text{best}}}{W_n} = \ln(n + 1) + \ln \binom{n}{H} - n\, h\!\left(\tfrac{H}{n}\right),$$

with $h$ the entropy of the observed share of heads, in nats. Stirling’s estimate of the factorials turns that into about $\tfrac12 \ln n - \tfrac12 \ln\big(2\pi\, \hat p (1 - \hat p)\big)$.

Two numbers frame the whole result. On a typical run the learner falls behind hindsight by about half the logarithm of the number of tosses: 3.25 nats at a thousand tosses of the 0.6 coin, 5.55 at a hundred thousand, which is a factor of about 260. On the worst run imaginable, all heads, the hindsight bettor stakes everything on heads and doubles every time, while the learner, cautious at the start, ends with $2^n/(n + 1)$: a factor of exactly $n + 1$ behind, and never more. Neither number grows anything like $n$.

That is the decisive point. The learner’s shortfall per toss is about $\tfrac{\ln n}{2n}$, which goes to nought, so its long-run growth rate is the growth rate of the best fixed fraction — and for an independent coin that is Kelly’s rate with the true $p$. The bettor who knew $p$ has an advantage that grows only like a logarithm, while its own wealth grows exponentially. On the run in the first figure the gap was 1.5 orders of magnitude out of 19.

The coin matters to the constant and not to the rate. A more lopsided coin — chance 0.9 — sits half a nat higher, because $\hat p(1 - \hat p)$ is smaller and the peak of the wealth curve is narrower, so the average over $q$ captures less of it. A bettor learning a nearly certain coin pays slightly more for its ignorance than one learning a nearly fair one, in exchange for a much larger prize.

There is a standard improvement, due to Raphail Krichevsky and Victor Trofimov: add a half instead of one to the counts, which is the posterior mean under the prior with density proportional to $1/\sqrt{p(1 - p)}$. It loses at most $\tfrac12 \ln n$ plus less than one nat, even on the worst run, and no strategy can guarantee better than $\tfrac12 \ln n$ plus a constant against every sequence. That half a logarithm is a law of nature for this game: it is the price of locating one unknown number to within its own standard error, and it is the same half logarithm per unknown parameter that Jorma Rissanen proved in 1984 any compressor must pay for not knowing the source it is compressing. Following the empirical frequencies with a little caution added is also what a player who best-replies to the past does in a game, and the half logarithm is what that caution costs when the opponent is a coin.

Facing a fair coin, the learner pays the square root #

The worst coin for a learner is the one with nothing to learn.

On a fair coin the right stake is nought, and a bettor who knew that would keep its one unit of wealth for ever. The learner’s estimate is almost never exactly a half, so it always stakes something, on whichever side the coin has happened to favour so far, and on a fair coin that is a bet with no edge and a negative growth rate. At an even split its wealth is $2^n \big((n/2)!\big)^2/(n + 1)!$, which by Stirling is close to $\sqrt{\pi/(2n)}$: about an eighth after a hundred tosses and a two-hundred-and-fiftieth after a hundred thousand, with the median run doing a little better than that, at about a seventh and a two-hundredth.

Strangely, the even split is the learner’s worst outcome on a fair coin, and the median run sits just above it. Any imbalance between heads and tails, even an imbalance produced by pure chance, is something the learner partly bets on and partly profits from. It is the overfitting of a model to noise, written as money: the learner treats the fluctuation as signal, and against a fair coin every fluctuation is noise, but the fluctuations it has already seen are, by construction, the ones it bet on.

So the price of learning cuts in both directions. Against a coin with an edge, the learner loses a slowly growing factor and gains an exponentially growing one. Against a coin with none, there is nothing to gain and the same slowly growing factor to lose. A bettor uncertain whether any edge exists at all can put part of its wealth with the learner and keep part in reserve, and the arithmetic of mixtures says exactly what that costs — the same arithmetic as peeking at a test until it says yes, where a Bayes factor kept its guarantee under any stopping rule for the same reason, being a likelihood averaged over a prior.

Why averaging beats estimating #

The two bettors who did not know $p$ in the first figure behaved very differently, and the difference was not cleverness. The plug-in bettor answered the question what is $p$? and then acted as if the answer were exact. The learner never answered that question; it kept a weighted vote over every possible $p$, and the weights were updated by the evidence exactly as evidence measured in decibans accumulates — multiplicatively, toss by toss.

In wealth, the multiplication is literal. A fixed-fraction bettor’s wealth at the end is the likelihood of the observed sequence under its $q$, scaled by $2^n$, so a sliver of money placed on $q$ grows in exact proportion to how well $q$ explains the data. Splitting the money among all the $q$ and letting each sliver grow is Bayesian updating with dollars as the probabilities, and the learner’s posterior-mean stake is just the bet that the whole portfolio of slivers would make if it were pooled. This is why the learner’s wealth equals the marginal likelihood of the data — the same quantity a Bayes factor is a ratio of — and why a bettor and a statistician who never discuss betting end up computing the same integral. Divided by the wealth of a bettor who stakes nothing, which is one, the learner’s $2^n H!\,T!/(n + 1)!$ is exactly the uniform-prior Bayes factor against a fair coin that the essay on peeking watched toss by toss: its wealth is evidence, and the fair coin’s figure above is that Bayes factor’s slow decline under the null, seen from the gambler’s side.

It also explains when the plug-in approach is harmless. With $m\varepsilon^2$ large, the posterior is concentrated — it piles up on the true $p$ the way a posterior always piles up on the best available hypothesis — the slivers that matter all sit near the true $p$, and committing to the estimate costs almost nothing. With $m\varepsilon^2$ near one or below, the posterior is wide, and acting on its centre ignores most of what is known — namely, how little is known.

What the computations assume #

Every number here is for the cleanest version of the problem: a single coin, the same coin on every toss, even money, tosses independent of one another. The exact formulas — the $1/(2m)$ loss to second order, the shrinkage factor, the beta integral, the $\ln(n + 1)$ worst case — are statements about that model, and the simulations only illustrate them.

Real edges drift, and a learner that weights a thousand old tosses as heavily as the last ten will be slow to notice when the coin changes. Cover’s construction does extend beyond the coin: for a portfolio of $d$ assets the universal strategy falls behind the best constant-proportion portfolio in hindsight by about $\tfrac{d - 1}{2} \ln n$, half a logarithm per free parameter, against any sequence of returns at all — no randomness assumed. That is a strong guarantee and a modest benchmark, because the best constant portfolio in hindsight can be a poor strategy when the world does not hold still.

And the figures cannot show that maximising the logarithm is right for a given person. That argument was had in the essay on Kelly’s rule and is not reopened here; the claim of this essay is narrower. Given that a bettor wants Kelly’s growth, not knowing the coin costs a factor of about $\sqrt n$ if the bettor learns sensibly, and can cost everything if it does not.

Still open: the right prior for a moving edge #

What should a bettor do when the edge changes over time? For a fixed coin the answer is settled: the Krichevsky–Trofimov mixture is within a constant of the best guarantee any strategy can make against every sequence. For an edge that switches between values at unknown times, there are mixtures over switching strategies — the fixed-share and related methods of Mark Herbster and Manfred Warmuth — that track the best sequence of fractions with a penalty growing with the number of switches, and they are known to be nearly optimal in the worst case. What is not settled is the choice between them when the edge drifts gradually rather than jumping, or when the bettor has partial knowledge of how fast it drifts, and how the best achievable shortfall depends on the drift’s size is known only in special models. The worst-case theory and the Bayesian theory agree on the fixed coin and part company as soon as the coin is allowed to move, and which of them a bettor should trust on a real, slowly changing edge is a question about the world as much as about mathematics.

Hedge across the coins #

A bettor who does not know the coin should not bet as if it did. Staking an estimate costs $1/(2m)$ a toss and turns negative below about $1/\varepsilon^2$ tosses, which is why the estimated stake should be shrunk by $m\varepsilon^2/(1 + m\varepsilon^2)$ — half Kelly exactly when the standard error equals the edge. Learning toss by toss with Laplace’s rule does better than any single estimate, because it is the same as holding every fixed fraction at once: its wealth is $2^n H!\, T!/(n + 1)!$, it falls behind hindsight by about $\tfrac12 \ln n$ and never by more than $\ln(n + 1)$, and on a fair coin it pays a factor of about $\sqrt{\pi n/2}$ for looking for an edge that is not there.