Mathematical Rules of Thumb, illustrated reader · Chapter 15

15Information Theory

Measuring Information and Its Limits

5 demonstrations follow the chapter's rules. Choose a value, watch the figure and the numbers change, and check your prediction. Every choice is precomputed from the notebook calculations.

Ask the chapter skill

“Help me use Chapter 15 for my question. Choose a rule, check its assumptions, and show how the result changes when an input changes.”

Use math-thumb-information-theory from the companion's skill package. The demonstrations below also work on their own.

Examples use constructed inputs or the book's own values, disclosed in each panel. A picture illustrates a rule; its assumptions set its scope.

1Demonstration 1 of 5

Separate rare-event surprisal from average entropy

Why is entropy low when p=.01?

The entropy curve peaks at equal probabilities, even though individual rare events can be surprising.

H(p)=−plog⁡2p−(1−p)log⁡2(1−p) H(p)=-p\log_2p-(1-p)\log_2(1-p)

Bernoulli probability p. Bits; terms with probability zero contribute zero by their limiting value.

Predict first. Why is entropy low when p=.01?

Choose an example

Separate rare-event surprisal from average entropy. At p=0.2, entropy is 0.721928 bits. The rare outcome carries 2.32193 bits of surprisal when it happens. As p moves away from .5 toward zero, entropy falls because outcomes become more predictable.
Bernoulli probability p: 0.2
Constructed teaching inputs; calculations executed locally. Supported menu choices are precomputed.

Calculated values

Entropy in bits
0.721928
Effective alphabet size
1.64938

At p=0.2, entropy is 0.721928 bits. The rare outcome carries 2.32193 bits of surprisal when it happens. As p moves away from .5 toward zero, entropy falls because outcomes become more predictable.

Use the idea

Use rule 15.1.3 when its stated conditions fit. Compare the calculation with your own decision threshold; retain the relevant error or uncertainty.

Where the conclusion applies

Bits; terms with probability zero contribute zero by their limiting value.

Check your understanding: Why is entropy low when p=.01?
Most outcomes are the predictable common outcome. High surprisal of the rare outcome contributes only with weight .01.

Book source: Rule 15.1.3: Entropy of a Rare Bernoulli Event. Demonstration C15-D01. Worked illustration.

2Demonstration 2 of 5

Price a probability model mismatch

Where is cross-entropy minimized?

True probabilities remain (.8,.2) while the model changes. Cross-entropy exposes the additional cost of mismatch.

H(P,Q)=−∑iPilog⁡2Qi,perplexity⁡=2H(P,Q) H(P,Q)=-\sum_i P_i\log_2Q_i,\quad\operatorname{perplexity}=2^{H(P,Q)}

Model probability q for first outcome. Matching outcome space; Q is positive wherever P is positive. No fitted language-model performance is claimed.

Predict first. Where is cross-entropy minimized?

Choose an example

Price a probability model mismatch. True probabilities are (.8,.2), while the model assigns (0.5,0.5). Cross-entropy is 1 bit, the average cost of coding real outcomes with the model. The excess over the true entropy, 0.2781 bits, is the price of the wrong model (KL divergence). Perplexity 2 means the model is as unsure as a fair pick among that many options.
Model probability q for first outcome: 0.5
Constructed teaching inputs; calculations executed locally. Supported menu choices are precomputed.

Calculated values

True entropy
0.721928
Cross-entropy
1
Perplexity
2
KL divergence (bits)
0.278072

True probabilities are (.8,.2), while the model assigns (0.5,0.5). Cross-entropy is 1 bit, the average cost of coding real outcomes with the model. The excess over the true entropy, 0.2781 bits, is the price of the wrong model (KL divergence). Perplexity 2 means the model is as unsure as a fair pick among that many options.

Use the idea

Use rule 15.1.4 when its stated conditions fit. Compare the calculation with your own decision threshold; retain the relevant error or uncertainty.

Where the conclusion applies

Matching outcome space; Q is positive wherever P is positive. No fitted language-model performance is claimed.

Check your understanding: Where is cross-entropy minimized?
At Q=P, where the KL excess is zero and cross-entropy equals entropy.

Book source: Rule 15.1.4: Perplexity Is Exponentiated Cross-Entropy. Demonstration C15-D02. Worked illustration.

3Demonstration 3 of 5

Read a channel limit as a limit

What information capacity remains at ε=.5?

A binary symmetric channel loses information capacity as its independent flip probability approaches one half.

C=1−H2(ϵ) C=1-H_2(\epsilon)

Bit-flip probability ε. Ideal memoryless binary channel and asymptotic coding capacity in bits/use.

Predict first. What information capacity remains at ε=.5?

Choose an example

Read a channel limit as a limit. The ideal memoryless binary symmetric channel has capacity 0.531004 bits per use at flip probability 0.1. So you need about 1.88 sent bits per data bit, even with ideal coding. Real codes need somewhat more.
Bit-flip probability ε: 0.1
Constructed teaching inputs; calculations executed locally. Supported menu choices are precomputed.

Calculated values

Flip probability
0.1
Channel capacity
0.531004

The ideal memoryless binary symmetric channel has capacity 0.531004 bits per use at flip probability 0.1. So you need about 1.88 sent bits per data bit, even with ideal coding. Real codes need somewhat more.

Use the idea

Use rule 15.3.3 when its stated conditions fit. Compare the calculation with your own decision threshold; retain the relevant error or uncertainty.

Where the conclusion applies

Ideal memoryless binary channel and asymptotic coding capacity in bits/use.

Check your understanding: What information capacity remains at ε=.5?
Zero. Output bits then carry no information about the input in this model.

Book source: Rule 15.3.3: Binary Symmetric Channel Capacity. Demonstration C15-D03. Worked illustration.

4Demonstration 4 of 5

Price signal power in bits

At 30 dB, what does doubling transmit power buy?

Mark the chosen SNR on the capacity curve and show what doubling the signal power buys.

C=12log⁡2(1+SNR) C=\tfrac12\log_2(1+\mathrm{SNR})

Signal-to-noise ratio (dB). Ideal additive white Gaussian noise channel, bits per real sample. dB means 10·log10 of the power ratio.

Predict first. At 30 dB, what does doubling transmit power buy?

Choose an example

Price signal power in bits. At 10 dB (power ratio 10), the ideal Gaussian channel carries 1.7297 bits per real sample. Doubling signal power adds 0.466 bits. At high SNR each doubling adds only about half a bit per real sample, so more bandwidth (more samples per second) usually beats more power.
Signal-to-noise ratio (dB): 10
Constructed teaching inputs; calculations executed locally. Supported menu choices are precomputed.

Calculated values

SNR (dB)
10
SNR as a power ratio
10
Capacity (bits per real sample)
1.72972
Capacity with double power
2.19616
Gain from doubling power (bits)
0.466443

At 10 dB (power ratio 10), the ideal Gaussian channel carries 1.7297 bits per real sample. Doubling signal power adds 0.466 bits. At high SNR each doubling adds only about half a bit per real sample, so more bandwidth (more samples per second) usually beats more power.

Use the idea

Use rule 15.3.2 when its stated conditions fit. Compare the calculation with your own decision threshold; retain the relevant error or uncertainty.

Where the conclusion applies

Ideal additive white Gaussian noise channel, bits per real sample. dB means 10·log10 of the power ratio.

Check your understanding: At 30 dB, what does doubling transmit power buy?
About half an extra bit per real sample, from 4.98 to 5.48.

Book source: Rule 15.3.2: Gaussian Channel Capacity Grows Logarithmically with SNR. Demonstration C15-D04. Worked illustration.

5Demonstration 5 of 5

Pick the number of hashes for a Bloom filter

With 8 bits per item, are 20 hashes safer than 6?

Plot the false-positive rate against the number of hash functions. Too few hashes give weak fingerprints; too many fill the bit array.

pfp≈(1−e−kn/m)k,k*=mnln⁡2 p_{fp}\approx\left(1-e^{-kn/m}\right)^k,\quad k^*=\tfrac mn\ln2

Bits per item m/n. Standard approximation with independent ideal hashes and n items in m bits. False negatives cannot occur.

Predict first. With 8 bits per item, are 20 hashes safer than 6?

Choose an example

Pick the number of hashes for a Bloom filter. With 8 bits per stored item, the false-positive rate is smallest near k=(m/n)ln 2=5.55; the best whole number is 6, giving 2.16%. One hash gives 11.8%, and 24 hashes give 29.4% because the bit array fills up. Each doubling of memory squares the best rate, roughly.
Bits per item m/n: 8
Constructed teaching inputs; calculations executed locally. Supported menu choices are precomputed.

Calculated values

Bits per item m/n
8
Ideal k = (m/n) ln 2
5.54518
Best whole k
6
False-positive rate at best k
0.0215771
False-positive rate at k=1
0.117503
Rate at k=24
0.293564

With 8 bits per stored item, the false-positive rate is smallest near k=(m/n)ln 2=5.55; the best whole number is 6, giving 2.16%. One hash gives 11.8%, and 24 hashes give 29.4% because the bit array fills up. Each doubling of memory squares the best rate, roughly.

Use the idea

Use rule 15.3.5 when its stated conditions fit. Compare the calculation with your own decision threshold; retain the relevant error or uncertainty.

Where the conclusion applies

Standard approximation with independent ideal hashes and n items in m bits. False negatives cannot occur.

Check your understanding: With 8 bits per item, are 20 hashes safer than 6?
No. Six hashes give about 2.2%; twenty give about 18% because most bits are already set.

Book source: Rule 15.3.5: Bloom Filter Optimal Hash Count. Demonstration C15-D05. Worked illustration.

Bring the idea to a question of your own

Choose the relationship that answers your question, check its conditions, and compare the result with the accuracy or decision threshold you need.

The chapter skill can adapt these calculations to your inputs. It should name the assumptions, explain what the result supports, and say what still needs evidence. The chapter workbook adds a lab and three exercises with answers.