Gambling and Data Compression · Vaibhav on HTTPS

Motivation: the telegraph office next door to the racetrack

In the late 19th century, a large share of telegraph traffic was race results. Bookmakers in one city took bets on races being run in another, and the wire was how the results arrived. So the telecom company had two kinds of customers in the same building: the operator who wanted cheap descriptions of messages, and the gambler who wanted to profit from predicting them.

These look like unrelated businesses. One minimizes pulses on a wire, the other maximizes money in a pocket. This note shows they are the same problem:

Compression engineer	Gambler
Builds a codebook from an estimate $q$ of the source distribution	Places bets according to an estimate $b$ of the race distribution
Pays $H + D(p \Vert q)$ bits per symbol	Grows wealth at a rate that drops by $D(p \Vert b)$ per race
Saves $\log m - H$ bits per symbol versus a naive code	Doubles wealth $\log m - H$ times per race at uniform odds
Best possible: use $q = p$	Best possible: bet $b = p$

IntuitionThe central claim

A good gambler is a good compressor, and vice versa. Both are scored by how close their probability estimate is to the truth, with relative entropy as the score. Every bit of predictability in a source is worth either one bit saved on the wire or one doubling of a gambler’s wealth.

The horse race

Setup. $m$ horses run. Horse $i$ wins with probability $p_i$ . A bet of 1 dollar on horse $i$ returns $o_i$ dollars if it wins and nothing if it loses.

Convention“For” versus “to” odds

$a$ -for-1 is settled before the race: you hand over 1 dollar, and get $a$ dollars back if your horse wins.
$b$ -to-1 is settled after the race: you pay 1 dollar if you lose, and collect $b$ dollars if you win.

They are equivalent when $b = a - 1$ . Fair odds on a coin flip are 2-for-1, or 1-to-1 (“even odds”). This note uses $a$ -for-1 throughout: $o_i$ is what you get back per dollar bet.

DefinitionBetting strategy (portfolio)

The gambler splits all their wealth across the horses, with fraction $b_i \ge 0$ on horse $i$ and $\sum_i b_i = 1$ . We write $b(i)$ and $b_i$ interchangeably.

DefinitionWealth relative

If horse $X$ wins, the gambler’s wealth is multiplied by

$S(X) = b(X)\, o(X)$

Component	Detail
Signature	$S : \{1, \ldots, m\} \rightarrow [0, \infty)$ , a random variable through $X$
Domain	The winning horse.
Codomain	The factor by which wealth is multiplied in this race. $S = 0$ means ruin.

Why “maximize expected wealth” is the wrong goal

The tempting strategy is to put everything on the horse with the largest expected return $p_i o_i$ . That maximizes $\mathbb{E}[S(X)]$ for one race. But gambling is repeated, and winnings are reinvested, so wealth compounds multiplicatively:

$S_n = \prod_{i=1}^n S(X_i)$

WarningThe expected-value bettor goes broke

Two horses at even odds (2-for-1), with $p = (0.6, 0.4)$ . Going all-in on horse 1 every race gives $\mathbb{E}[S_n] = 1.2^n$ , which grows exponentially. But $S_n = 0$ unless horse 1 wins every race, which has probability $0.6^n \rightarrow 0$ . The expectation is carried entirely by one astronomically unlikely winning streak. Almost surely, the expected-value bettor is ruined.

IntuitionProducts want logarithms

A product of i.i.d. factors is governed by the average of their logarithms: $\log S_n = \sum \log S(X_i)$ is a sum, and the law of large numbers controls sums. This is exactly the move that turned the joint probability of a tape into a sample mean in the AEP.

DefinitionDoubling rate

$W(b, p) = \mathbb{E}\big[\log S(X)\big] = \sum_{k=1}^m p_k \log b_k o_k$

Component	Detail
Signature	$W : \mathcal{P}(\mathcal{X}) \times \mathcal{P}(\mathcal{X}) \rightarrow [-\infty, \infty)$
Domain	A betting strategy $b$ and the true win probabilities $p$ (the odds $o$ are fixed).
Codomain	Expected $\log_2$ wealth growth per race. $W = 1$ means wealth doubles each race; $W = -\infty$ means some winning horse has $b_i = 0$ , so ruin is possible.

TheoremWealth grows at the doubling rate

If race outcomes $X_1, X_2, \ldots$ are i.i.d. $\sim p(x)$ , the wealth of a gambler using strategy $b$ satisfies

$S_n \doteq 2^{nW(b,p)}$

in the sense of first-order exponential equality.

ProofWeak law on the log wealth

The $X_i$ are i.i.d., and $\log S(\cdot)$ is a fixed function, so $\log S(X_1), \log S(X_2), \ldots$ are i.i.d. By the weak law of large numbers,

$\frac{1}{n}\log S_n = \frac{1}{n}\sum_{i=1}^n \log S(X_i) \longrightarrow \mathbb{E}\big[\log S(X)\big] = W(b,p) \quad \text{in probability}$

So $S_n \doteq 2^{nW(b,p)}$ .

∎

So the gambler should maximize the exponent $W(b,p)$ over portfolios.

DefinitionOptimum doubling rate

$W^*(p) = \max_{b:\, b_i \ge 0,\, \sum b_i = 1} \;\sum_{i=1}^m p_i \log b_i o_i$

Kelly gambling

DerivationA Lagrange multiplier suggests

b = p

Changing the log base doesn’t move the maximizer, so use natural logs:

$J(b) = \sum p_i \ln b_i o_i + \lambda \sum b_i, \qquad \frac{\partial J}{\partial b_i} = \frac{p_i}{b_i} + \lambda = 0 \;\Rightarrow\; b_i = -\frac{p_i}{\lambda}$

The constraint $\sum b_i = 1$ forces $\lambda = -1$ , so $b_i = p_i$ . This is only a stationary point. Instead of checking second derivatives, we guess and verify, as in the entropy bound for codes.

TheoremProportional gambling is log-optimal

$W^*(p) = \sum_i p_i \log o_i - H(p)$

achieved by proportional (Kelly) gambling, $b^* = p$ .

ProofPull out a relative entropy

Step 1: Insert $p_i/p_i$ inside the log.

$W(b,p) = \sum p_i \log b_i o_i = \sum p_i \log\left(\frac{b_i}{p_i} \cdot p_i o_i\right)$

Step 2: Split into three sums.

$= \sum p_i \log o_i + \sum p_i \log p_i - \sum p_i \log \frac{p_i}{b_i} = \sum p_i \log o_i - H(p) - D(p \,\Vert\, b)$

Step 3: Drop the relative entropy. $D(p \Vert b) \ge 0$ by the information inequality, with equality iff $b = p$ .

∎

ImportantThe optimal bet ignores the odds

When the gambler must be fully invested, $b^* = p$ whatever the odds are. The odds only enter through the constant $\sum p_i \log o_i$ . A horse paying 100-for-1 gets exactly its win probability, no more. Long odds affect how fast you get rich, not how you should bet.

IntuitionThe same decomposition as wrong-codebook compression

The gambler’s penalty for a wrong belief $b$ is $D(p \Vert b)$ in the doubling rate. The compression engineer’s penalty for a wrong codebook $q$ is $D(p \Vert q)$ in bits per symbol (wrong-code theorem). It is the same quantity, charged in two currencies.

ExampleTwo horses at even odds

$o_1 = o_2 = 2$ . Then $W^*(p) = \sum p_i \log 2 - H(p) = 1 - H(p)$ , and

$S_n \doteq 2^{n(1 - H(p))}$

For $p = (0.6, 0.4)$ : $H(p) \approx 0.971$ , so $W^* \approx 0.029$ bits per race. Wealth doubles about every 34 races, slowly but surely. This is the bettor that was ruined above, now betting 60/40 instead of all-in. With $p = (\frac{1}{2}, \frac{1}{2})$ the race is a fair coin and $W^* = 0$ : no edge, no growth.

Fair odds: beating the bookie

DefinitionFair odds and the bookie’s estimate

Odds are fair when $\sum_i \frac{1}{o_i} = 1$ (no track take). Then $r_i = \frac{1}{o_i}$ is a probability distribution: the bookie’s implied estimate of the win probabilities.

FormulaDoubling rate as a difference of relative entropies

With fair odds $o_i = 1/r_i$ ,

$W(b, p) = \sum p_i \log \frac{b_i}{r_i} = \sum p_i \log\left(\frac{b_i}{p_i}\cdot\frac{p_i}{r_i}\right) = D(p \,\Vert\, r) - D(p \,\Vert\, b)$

IntuitionThe gambler profits only by out-predicting the bookie

$D(p \Vert r)$ is how wrong the bookie is. $D(p \Vert b)$ is how wrong the gambler is. Wealth grows iff the gambler’s estimate is closer to the truth than the bookie’s. Relative entropy is literally the scoreboard.

Uniform odds and the conservation law

With $m$ -for-1 odds on every horse (fair with respect to the uniform distribution $u$ ):

$W^*(p) = D\!\left(p \,\Big\Vert\, \tfrac{1}{m}\right) = \log m - H(p)$

TheoremConservation theorem

For uniform fair odds,

$W^*(p) + H(p) = \log m$

IntuitionEvery bit of entropy is a doubling foregone

The doubling rate plus the entropy is a constant. Each bit of predictability (each bit by which $H$ falls below its maximum $\log m$ ) doubles the gambler’s wealth once more per race. Low-entropy races are the most profitable. Compare the maximum entropy bound: $\log m - H(p)$ is also exactly the number of bits per symbol a compressor saves over the naive $\log m$ -bit code. Predictability is worth the same amount to the gambler and to the telecom.

Keeping some cash

Now let the gambler hold back a fraction $b(0)$ as cash. The wealth relative becomes

$S(X) = b(0) + b(X)\, o(X)$

and the optimal strategy depends on the odds:

Odds	Condition	Optimal behavior
Fair	$\sum \frac{1}{o_i} = 1$	Cash is redundant. Betting $b_i = \frac{1}{o_i}$ returns exactly 1 whatever horse wins, which is a synthetic cash position. Proportional betting stays optimal.
Superfair	$\sum \frac{1}{o_i} < 1$	Better than fair, so stay fully invested; proportional betting is optimal. A Dutch book also exists: bet $b_i = c/o_i$ with $c = 1/\sum_j \frac{1}{o_j}$ , and $S(X) = c > 1$ whatever happens. It is risk-free, but it does not maximize the doubling rate.
Subfair	$\sum \frac{1}{o_i} > 1$	The realistic case: the track takes a cut. Hold some cash. Proportional betting is no longer optimal; the optimum (from Kuhn–Tucker conditions) has a “water-filling” form (Problem 6.2).

Gambling with side information

The problem. The gambler has a tip, a past-performance sheet, or a cousin who works in the stables. That is side information $Y$ correlated with the winner $X$ . What is the tip worth in money?

Setup. $(X, Y)$ has joint pmf $p(x,y)$ . Horse $x$ pays $o(x)$ -for-1. A conditional strategy $b(x \mid y) \ge 0$ , with $\sum_x b(x \mid y) = 1$ , bets fraction $b(x \mid y)$ on horse $x$ after seeing $Y = y$ .

DefinitionDoubling rates with and without the tip

$W^*(X) = \max_{b(x)} \sum_x p(x) \log b(x) o(x), \qquad W^*(X \mid Y) = \max_{b(x \mid y)} \sum_{x,y} p(x,y) \log b(x \mid y) o(x)$

$\Delta W = W^*(X \mid Y) - W^*(X)$

For i.i.d. pairs $(X_i, Y_i)$ , wealth grows like $2^{nW^*(X \mid Y)}$ with the tip and like $2^{nW^*(X)}$ without it.

TheoremThe financial value of side information is mutual information

$\Delta W = I(X; Y)$

ProofConditionally proportional betting, then subtract

Step 1: With the tip. For each $y$ the problem is an ordinary horse race with win probabilities $p(x \mid y)$ , so the optimum is conditionally proportional betting, $b^*(x \mid y) = p(x \mid y)$ :

$W^*(X \mid Y) = \sum_{x,y} p(x,y) \log o(x) p(x \mid y) = \sum_x p(x) \log o(x) - H(X \mid Y)$

Step 2: Without the tip. By the Kelly theorem, $W^*(X) = \sum_x p(x) \log o(x) - H(X)$ .

Step 3: Subtract. The odds terms cancel:

$\Delta W = H(X) - H(X \mid Y) = I(X; Y)$

∎

IntuitionMutual information, in dollars

Mutual information was introduced as the reduction in uncertainty about the sender’s symbol after reading the receiver’s tape. Here it is the exact number of extra doublings per race a tip buys. A useless (independent) tip is worth nothing. A tip can never hurt the optimal gambler, because $I(X;Y) \ge 0$ , which is the betting version of “conditioning reduces entropy”.

ExampleA perfect tip

If the tipster always names the winner ( $Y = X$ ), then $\Delta W = I(X;X) = H(X)$ . At uniform odds, $W^*(X) = \log m - H(X)$ , so $W^*(X \mid X) = \log m$ : bet everything on the named horse and multiply wealth by $m$ every race.

NoteGeneral stock markets

For a general stock market (Chapter 16) one only gets $\Delta W \le I$ , with equality iff the market is a horse race.

Dependent horse races and entropy rate

The problem. The most common side information is the past results themselves. For independent races they are worthless. But if races depend on each other (fatigue, track conditions, the same horses running every week), the past is a free tip.

Let $\{X_k\}$ be a stochastic process of winners, with uniform $m$ -for-1 odds, and let the bet on race $k$ depend on the previous results. The conditionally proportional bet $b^*(x_k \mid x_{k-1}, \ldots, x_1) = p(x_k \mid x_{k-1}, \ldots, x_1)$ achieves

$W^*(X_k \mid X_{k-1}, \ldots, X_1) = \log m - H(X_k \mid X_{k-1}, \ldots, X_1)$

DerivationSum the per-race rates with the chain rule

Wealth after $n$ races is $S_n = \prod_{i=1}^n S(X_i)$ , so

$\frac{1}{n}\mathbb{E}\log S_n = \frac{1}{n}\sum_{i=1}^n \mathbb{E}\log S(X_i) = \frac{1}{n}\sum_{i=1}^n \big(\log m - H(X_i \mid X_{i-1}, \ldots, X_1)\big) = \log m - \frac{H(X_1, \ldots, X_n)}{n}$

The last step is the chain rule for entropy.

TheoremConservation for dependent races

For a stationary process of races with entropy rate $H(\mathcal{X})$ ,

$\lim_{n \rightarrow \infty} \frac{1}{n}\mathbb{E}\log S_n + H(\mathcal{X}) = \log m$

RemarkRemoving the expectation

For an ergodic process (Chapter 16), $S_n \doteq 2^{nW}$ with probability 1, where $W = \log m - H(\mathcal{X})$ . This is the betting counterpart of the general AEP.

IntuitionGrammar is money

An operator with grammar has entropy rate below $\log m$ , and the gap is exactly what a gambler who knows the grammar can extract. The compression engineer and the gambler are paid by the same quantity: $\log m - H(\mathcal{X})$ , in bits saved per symbol or doublings per race.

Example: red and black

ExampleBetting on the colour of the next card

A deck holds 26 red and 26 black cards. Before each card is turned, bet on its colour at 2-for-1 (fair if red and black were equally likely). Unlike horses, the outcomes become more predictable as the deck thins: with one card left, you know its colour.

Scheme 1 (sequential). Bet proportionally to the conditional probability of the next card: $(\frac{1}{2}, \frac{1}{2})$ on the first; $(\frac{26}{51}, \frac{25}{51})$ on (red, black) for the second if the first was black; and so on.

Scheme 2 (all at once). There are $\binom{52}{26}$ equally likely colour sequences. Put $1/\binom{52}{26}$ of the money on each, and let every bet ride through all 52 cards.

They are the same strategy. In Scheme 2, the fraction of money riding on sequences whose next card is red always equals the conditional probability that the next card is red. For example, half of all sequences start with red. A bet on a sequence multiplies by $2^{52}$ if it is the one dealt and loses otherwise, so

$S_{52}^* = \frac{2^{52}}{\binom{52}{26}} \approx 9.08$

IntuitionEvery deal is typical

The final wealth is $9.08$ whatever order the cards come in, with zero variance. All $\binom{52}{26}$ sequences are equally likely, so every one is “typical”, like an exaggerated typical set that covers everything. Sequential proportional betting is equivalent to betting on whole sequences: this equivalence is the key to the twin compressor below.

The entropy of English

English, simplified to 26 letters and a space ( $m = 27$ ), is the natural source to try all this on. It is probably not stationary or ergodic (styles and topics drift), but we can still estimate its entropy rate by building better and better stochastic models.

RemarkEnglish is far from uniform

E has frequency about 13%; Q and Z about 0.1%. (The 267-page novel Gadsby by Ernest Vincent Wright avoids E entirely, which is a remarkable feat.)
Pairs are also far from uniform: Q is always followed by U, and TH is the most common pair at about 3.7%.

WarningHigher-order models run out of data

A third-order Markov model needs $p(x_i \mid x_{i-1}, x_{i-2}, x_{i-3})$ , a table with $27^4 = 531{,}441$ entries. Estimating it accurately takes millions of letters of text. Each step up in order multiplies the data needed by 27.

RemarkSampling a model without building it

To generate second-order text from a book: open it at random and pick a letter. Then open it at random again, read until you meet that letter, and take the letter after it. Repeat. The output has the book’s pair statistics, without anyone tabulating them.

Shannon’s approximations

Model	Sample (from Shannon 1948 and Lucky)
Zero order: independent, equiprobable	`XFOML RXKHRJFFJUJ ZLPWCFWKCYJ`
First order: independent, English letter frequencies	`OCRO HLI RGWR NMIELWIS EU LL NBNESEBYA TH EEI`
Second order: English pair frequencies	`ON IE ANTSOUTINYS ARE T INCTORE ST BE S DEAMY`
Third order: English triple frequencies	`IN NO IST LAT WHEY CRATICT FROURE BERS GROCID`
Fourth order: English quadruple frequencies	`THE GENERATED JOB PROVIDUAL BETTER TRAND THE DISPLAYED CODE`
First-order word model	`REPRESENTING AND SPEEDILY IS AN GOOD APT OR COME CAN DIFFERENT NATURAL`
Second-order word model	`THE HEAD AND IN FRONTAL ATTACK ON AN ENGLISH WRITER THAT THE CHARACTER OF THIS POINT`

Model	Entropy estimate (bits per letter)
Zero order	$\log 27 \approx 4.76$
First order	$4.03$
Fourth order	$2.8$

IntuitionEach model is a better gambler

Every step up in model order captures more structure, lowers the conditional uncertainty of the next letter, and therefore both compresses better and bets better. Even the fourth-order model misses most of English’s structure. The gambling estimates below come in near 1.3 bits.

ExampleRedundancy fills in the blanks

Delete the vowels from a sentence:

TH R S NLY N W Y T F LL N TH V W LS N TH S S NT NC

Most readers recover it at once. This redundancy is what breaks simple substitution ciphers: guess the most frequent cipher letter is E, then let the structure of English fill in the rest. Much of Shannon’s information theory grew out of his wartime cryptography work.

RemarkLanguage models in speech recognition

Speech recognizers combine the acoustic signal with a stochastic language model, commonly a trigram (second-order Markov) word model that predicts the next word from the previous two. Such models work surprisingly well without encoding any explicit grammar.

Data compression and gambling

The problem. We claimed a good gambler is a good compressor. Here is the construction. If a gambler makes a lot of money on a sequence, that sequence can be compressed by a correspondingly large amount.

Setup. Binary outcomes $X_1, \ldots, X_n$ , uniform 2-for-1 odds. The gambler places sequential bets $b(x_{k+1} \mid x_1, \ldots, x_k) \ge 0$ with $\sum_{x_{k+1}} b(x_{k+1} \mid x_1, \ldots, x_k) = 1$ .

FormulaSequential betting assigns a probability to whole sequences

$S_n = 2^n \prod_{k=1}^n b(x_k \mid x_1, \ldots, x_{k-1}) = 2^n\, b(x_1, \ldots, x_n), \qquad b(x^n) = \prod_{k=1}^n b(x_k \mid x^{k-1})$

The product $b(x^n)$ is a probability distribution on the $2^n$ sequences. So gambling elicits the gambler’s probability estimate, $\hat{p}(x^n) = S_n / 2^n$ , and an entropy estimate $\hat{H} = -\frac{1}{n}\log \hat{p}(x^n)$ .

IntuitionWealth and compressed length are the same number

If $\hat p(x^n) = S_n / 2^n$ is the gambler’s probability for the actual sequence, a code built from it should spend about $\log \frac{1}{\hat p} = n - \log S_n$ bits. Every doubling of wealth saves one bit.

The identical-twin compressor

flowchart LR
  X["Text x^n"] --> E["Encoder: gambler computes wealth on every sequence up to x^n"]
  E -->|"k = ceil(n - log S_n) bits"| W[Wire]
  W --> D["Decoder: identical twin replays the same bets"]
  D --> R["Recovered x^n"]

AlgorithmEncoding with a gambler

Both ends know $n$ and run identical, deterministic gamblers.

Order all $2^n$ binary sequences lexicographically (e.g. 0100101 < 0101101).
The encoder computes what its wealth $S_n(x'^n)$ would have been on every sequence $x'^n \le x^n$ , and forms the cumulative sum $F(x^n) = \sum_{x'^n \le x^n} 2^{-n} S_n(x'^n) \in [0, 1]$
Let $k = \lceil n - \log S_n(x^n) \rceil$ . Send the first $k$ binary digits of $F(x^n) = .c_1 c_2 \cdots c_k$ .
The decoder twin computes the same cumulative sums over all sequences in order, and outputs the first sequence whose cumulative sum falls in $[.c_1 \cdots c_k,\; .c_1 \cdots c_k + 2^{-k}]$ .

IntuitionWhy it decodes

The terms $2^{-n} S_n(x'^n) = b(x'^n)$ cut $[0,1]$ into consecutive intervals, one per sequence, and the interval for $x^n$ has width $b(x^n) = S_n(x^n)/2^n$ . Choosing $k \approx \log \frac{1}{b(x^n)}$ makes the precision $2^{-k}$ fine enough to land inside $x^n$ ‘s interval. This is Shannon–Fano–Elias coding with the gambler’s distribution $b$ in place of the true $p$ , which is to say arithmetic coding driven by a gambler.

TheoremBits saved equals log wealth

The twin scheme uses $k = \lceil n - \log S_n(x^n) \rceil < n - \log S_n + 1$ bits, saving about $\log S_n$ bits relative to sending the $n$ raw bits. With proportional gambling ( $b = p$ ), $S_n(x^n) = 2^n p(x^n)$ , so

$\mathbb{E}\,k = \sum_{x^n} p(x^n)\left\lceil \log \frac{1}{p(x^n)} \right\rceil \le H(X_1, \ldots, X_n) + 1$

which achieves the Shannon limit.

NoteWhat the book’s construction glosses over

Cover & Thomas present the decoder informally (“the size of $S(x(n))$ guarantees…”). They don’t address boundary cases, where a truncated $F$ could land at an interval edge (the reason Shannon–Fano–Elias spends one extra bit and uses the midpoint of each step). They also assume the decoder knows where the $k$ -bit codeword ends. Treat the scheme as a demonstration of the duality, not a production codec. The careful version is arithmetic coding (Chapter 13).

ImportantThe duality in one sentence

Gambling and compression both reduce to estimating the true distribution. The better the estimate, the faster the wealth grows and the shorter the code. Each doubling is one bit saved.

Gambling estimates of the entropy of English

The duality gives a way to measure English’s entropy rate using humans as the probability model. Humans know far more about English than any fourth-order table.

The Shannon guessing game

DefinitionGuessing game

A subject reads English text and guesses the next letter, trying the most likely letter first, then the next most likely, and so on. The experimenter records how many guesses each letter took. Many letters take one guess; word and sentence beginnings take many.

IntuitionThe guess counts are a lossless re-encoding of the text

Model the subject as a deterministic machine (the same past always produces the same guess order). Given an identical machine and the sequence of guess counts, you can regenerate the text: run the machine, and if position $i$ took $k$ guesses, output the machine’s $k$ -th guess. The map is invertible, so the guess sequence carries exactly the information in the text, and its entropy is the entropy of English.

RemarkFrom histogram to bound

Treating successive guess counts as independent can only overestimate their joint entropy (by the independence bound). So the entropy of the guess-count histogram is an upper bound. Shannon’s 1950 experiment gave about 1.3 bits per letter.

The gambling estimate

Guessing only records a rank. Betting lets the subject express graded confidence. The subject bets on the next letter at 27-for-1 on the correct letter. Sequential betting equals betting on whole sequences, so after $n$ letters

$S_n = 27^n\, b(X_1, \ldots, X_n)$

DerivationThe bettor’s wealth bounds the entropy rate from above

Step 1: Expected log wealth.

$\frac{1}{n}\mathbb{E}\log S_n = \log 27 + \frac{1}{n}\sum_{x^n} p(x^n)\log b(x^n)$

Step 2: Insert $p(x^n)/p(x^n)$ and split.

$= \log 27 - \frac{1}{n}\sum_{x^n} p(x^n) \log \frac{p(x^n)}{b(x^n)} + \frac{1}{n}\sum_{x^n} p(x^n)\log p(x^n) = \log 27 - \frac{1}{n}D\big(p(x^n) \Vert b(x^n)\big) - \frac{1}{n}H(X_1, \ldots, X_n)$

Step 3: Drop the relative entropy. $D \ge 0$ , so $\frac{1}{n}\mathbb{E}\log S_n \le \log 27 - \frac{1}{n}H(X_1, \ldots, X_n)$ .

Step 4: Compare the block average with the rate. For a stationary source the conditional entropies $H(X_i \mid X^{i-1})$ are nonincreasing with limit $H(\mathcal{X})$ . Their running average $\frac{1}{n}H(X_1, \ldots, X_n)$ is therefore at least the limit. Hence

$\frac{1}{n}\mathbb{E}\log S_n \le \log 27 - H(\mathcal{X})$

(Cover & Thomas state this last inequality without the justification in Step 4.)

TheoremGambling estimate of the entropy rate

$\hat H(\mathcal{X}) = \log 27 - \frac{1}{n}\log S_n$

is an upper bound on the entropy rate of English, in expectation. If English is ergodic and the gambler bets $b(x^n) = p(x^n)$ , then $\hat H \rightarrow H(\mathcal{X})$ with probability 1.

IntuitionWhy it can only overestimate

A gambler cannot extract more than the true predictability. Any modelling error ( $D > 0$ ) shows up as lost wealth, which makes $\hat H$ larger. So a low estimate is believable, and better gamblers push it down toward the truth.

ExampleThe experiment

Twelve subjects gambled on a 75-letter passage from Jefferson the Virginian by Dumas Malone (the same source Shannon used). The estimate was 1.34 bits per letter, close to Shannon’s guessing-game 1.3 and far below the 2.8 of a fourth-order letter model.

Method	Estimate (bits/letter)
Zero-order model	4.76
First-order model	4.03
Fourth-order model	2.8
Shannon guessing game	1.3
Gambling (12 subjects, 75 letters)	1.34

IntuitionWhat 1.3 bits means for the telegraph

A naive 27-symbol code spends $\log 27 \approx 4.76$ bits per letter. An ideal compressor that understood English as well as a human reader would spend about 1.3: roughly 72% of a plain-English telegram is redundancy. That is also how many doublings per letter a perfect English-predicting gambler could extract at 27-for-1 odds.

Quick reference

Object	Statement	Reads as
Wealth relative	$S(X) = b(X)o(X)$	Wealth multiplier for one race.
Doubling rate	$W(b,p) = \sum p_k \log b_k o_k$	Expected log growth per race.
Growth	$S_n \doteq 2^{nW(b,p)}$	Wealth grows exponentially at rate $W$ .
Kelly	$W^* = \sum p_i \log o_i - H(p)$ at $b^* = p$	Bet in proportion to belief, whatever the odds.
Penalty	$W(b,p) = W^* - D(p \Vert b)$	A wrong belief costs $D(p\Vert b)$ doublings per race.
Fair odds	$W = D(p \Vert r) - D(p \Vert b)$ , $r_i = 1/o_i$	Win only by out-predicting the bookie.
Conservation	$W^* + H(p) = \log m$ (uniform odds)	Each bit of entropy is a doubling foregone.
Side information	$\Delta W = I(X;Y)$	A tip is worth its mutual information.
Dependent races	$\lim \frac{1}{n}\mathbb{E}\log S_n + H(\mathcal{X}) = \log m$	Grammar is money.
Red and black	$S_{52}^* = 2^{52}/\binom{52}{26} \approx 9.08$	Same payoff on every deal.
Twin compressor	$k = \lceil n - \log S_n \rceil$ bits	Each doubling saves one bit.
Gambling estimate	$\hat H = \log 27 - \frac{1}{n}\log S_n \ge H(\mathcal{X})$	Human bettors upper-bound English’s entropy.

Constants and identities to keep to hand:

$a$ -for-1 equals $(a-1)$ -to-1. Even odds = 2-for-1 = 1-to-1.
Fair: $\sum 1/o_i = 1$ . Superfair: $< 1$ (a Dutch book exists). Subfair: $> 1$ (hold cash).
Maximizing $\mathbb{E}[S]$ goes broke; maximizing $\mathbb{E}[\log S]$ grows surely.
English: $\log 27 \approx 4.76$ bits; first order 4.03, fourth order 2.8, humans about 1.3.
$\frac{1}{n}H(X_1, \ldots, X_n) \ge H(\mathcal{X})$ for stationary sources: block averages overestimate the rate.

References

Cover & Thomas, Elements of Information Theory — Chapter 6