0.7. Information Theory (Shannon)

Information is resolved uncertainty.

Information theory begins when probability starts asking what is learned when something happens.

Learning, to Shannon, is reducing your space of uncertainty. Reducing your ignorance. It rings similar to Conan Doyle's "When you discard all other possibilities, truth remains."

Information is relative to a model.

Data is an observation. Information is what that observation changes about possibility.

A Datum by itself carries no absolute quantity of information.

Necesitamos una distribución $(p(x))$

Rarity carries information

Cuanto menos esperábamos un resultado, más aprendemos al observarlo:

$$ p(x)\downarrow \quad\Rightarrow\quad I(x)\uparrow $$

Certainty carries no surprise

$$ I(p=1)=0 $$

Si ya sabíamos qué iba a ocurrir, observarlo no resuelve incertidumbre.

Independent evidence adds

Si dos observaciones independientes tienen probabilidades $(p)$ y $(q)$, observar ambas debería dar:

$$ I(pq)=I(p)+I(q) $$

Surprise is logarithmic

$$ I(x)=\log_b\frac1{p(x)}=-\log_b p(x) $$

La base no cambia la estructura; cambia la unidad. Base 2 → bits

A bit is a halving of possibility.

Para $(p=1/2)$:

$$ I=1\text{ bit} $$

Para $(p=1/4)$, $(I=2)$ bits; para $(p=1/1024)$, $(I=10)$ bits. Esta interpretación conecta muy bien información con decisión binaria y codificación.

Surprisal belongs to an outcome; entropy belongs to a distribution.

$$ I(x)=-\log_2p(x) $$

$$ H(X)=\mathbb E[I(X)] =-\sum_x p(x)\log_2p(x) $$

Entropy is expected surprise

Antes de observar $(X)$, $(H(X))$ mide cuánto esperamos aprender al resolverlo. Después de observar $(x)$, $(I(x))$ mide la sorpresa concreta recibida.

Uniformity maximizes entropy.

Si hay $(N)$ resultados equiprobables:

$$ H(X)=\log_2N $$

Una distribución determinista tiene $(H=0)$. Una moneda justa alcanza 1 bit, el máximo posible para dos resultados.

Shannon information is not semantic meaning.

Context changes information.

$$ I(x\mid c)=-\log_2p(x\mid c) $$

Ésta es la puerta hacia lenguaje, inferencia, Bayes, cross-entropy y mutual information.

Shannon surprise

Probability of the exact observation

$$ h(x)=\log_2\frac1{p(x)} $$

Pattern surprise

Probability of a class/event we consider remarkable

Model surprise

Evidence that perhaps our assumed model was wrong

---

🏵 Main idea

The central conceptual chain should be:

Reality
   │
   ▼
Outcome
ω ∈ Ω
   │
   │ observation / measurement
   ▼
X : Ω → 𝒳
   │
   ▼
Observed value
x ∈ 𝒳
   │
   ▼
Probability
pX(x)
   │
   ▼
Surprisal
I(x) = -log₂ pX(x)
   │
   │ expectation
   ▼
Entropy
H(X) = E[I(X)]

The important transition is:

possibility → observation → probability → information

Probability describes the structure before an outcome is known.

Information describes what is resolved when an observation arrives.

---

🏵 Focus: distinguish Ω from 𝒳

This distinction should become part of the theoretical vocabulary of the project.

Ω — Sample space

Ω describes the possible states or outcomes admitted by the model.

An element is:

ω ∈ Ω

The outcome is not necessarily the datum we eventually record.

---

𝒳 — Observation alphabet

𝒳 is the set of values an observable can produce.

Examples:

𝒳 = {Head, Tail}

𝒳 = {⚀, ⚁, ⚂, ⚃, ⚄, ⚅}

𝒳 = ℝ

𝒳 = {positive, negative}

𝒳 = vocabulary of a language

This connects directly with the existing idea:

Types are alphabets.

---

X — Observation / random variable

A random variable is the bridge:

$$X : \Omega \rightarrow \mathcal X$$

It transforms an underlying outcome into a value that can be observed, recorded, compared, transmitted, or analyzed.

This is a fundamental connection with the philosophy of Data:

Data is not the world itself.
Data is what an observation preserves about the world.

A single reality may admit many different observables.

ω
├── X₁(ω) = temperature
├── X₂(ω) = color
├── X₃(ω) = category
└── X₄(ω) = signal amplitude

Different measurements produce different data because they preserve different distinctions.

---

🔰 Probability comes before information

Suppose:

$$X \sim p_X$$

Before observing X, we have a distribution over its possible values.

For an outcome x:

$$p_X(x)$$

describes how expected that observation was under the model.

This gives the first bridge between probability and information:

Rare observations resolve more uncertainty than common observations.

Symbolically:

$$p(x) \downarrow \quad\Rightarrow\quad I(x) \uparrow$$

---

🏵 Surprisal

The information carried by observing an outcome x is:

$$I(x) = -\log_2 p(x) = \log_2 \frac{1}{p(x)}$$

This quantity is often called:

• surprisal
• self-information
• information content

For the book, surprise or surprisal is probably the best conceptual entry point.

Information is logarithmic rarity.

$$ \boxed{ I(x)=\log_2\rho(x) } $$

---

🔰 Why probability is inverted

A probable event teaches us little.

If:

$$p(x) = 1$$

then:

$$I(x) = -\log_2(1) = 0$$

The observation tells us nothing we did not already know.

At the opposite extreme:

$$p(x) \rightarrow 0$$

implies:

$$I(x) \rightarrow \infty$$

A sufficiently unexpected observation carries large information relative to the model.

⚜️ This relativity matters:

Information is not an intrinsic property of a symbol.

The same observation can carry different amounts of information under different models.

---

🏵 Why the logarithm?

The logarithm should not appear as an arbitrary definition.

The crucial property is additivity.

Suppose two independent observations occur:

$$P(x,y) = P(x)P(y)$$

We want their combined information to satisfy:

$$I(x,y) = I(x) + I(y)$$

Therefore:

$$I(pq) = I(p) + I(q)$$

The logarithm transforms multiplication into addition:

$$\log(pq) = \log p + \log q$$

Hence:

$$I(p) = -\log p$$

up to a multiplicative constant / choice of unit.

⚜️ Focus on this idea:

Independent probabilities multiply.
Independent information adds.

This is one of the conceptual reasons information theory is logarithmic.

---

🔰 Bits

Using logarithm base 2 gives information in bits.

Examples:

$$p = \frac12 \Rightarrow I = 1\text{ bit}$$ $$p = \frac14 \Rightarrow I = 2\text{ bits}$$ $$p = \frac1{1024} \Rightarrow I = 10\text{ bits}$$

A useful interpretation is:

One bit corresponds to resolving one fair binary distinction.

Equivalently, each bit halves the remaining possibilities under an ideal binary partition.

---

🏵 Outcome surprise versus entropy

This distinction should be explicit very early.

Surprisal

Surprisal belongs to a particular observation:

$$I(x) = -\log_2 p(x)$$

It is evaluated after a specific value occurs.

---

Entropy

Entropy belongs to a distribution:

$$H(X) = \mathbb E[I(X)]$$

For a discrete random variable:

$$H(X) = -\sum_x p(x)\log_2 p(x)$$

So:

I(x)   → information in this observation

H(X)   → expected information before observing X

⚜️ The first introductory chapter should probably stop here.

Conditional entropy, mutual information, KL divergence, coding theorems, etc. can come later.

---

🏵 Entropy as expected surprise

Substituting surprisal into the expectation:

$$H(X) = \sum_x p(x)I(x)$$

gives:

$$H(X) = -\sum_x p(x)\log_2p(x)$$

This interpretation is preferable to presenting entropy initially as an unexplained formula.

Entropy is the average surprise produced by a source.

Or, more cautiously:

Entropy measures the expected information obtained when the uncertainty represented by a distribution is resolved.

---

🔰 Extremes of entropy

Certain distribution

If one outcome has probability 1:

p = [1, 0, 0, ...]

then:

$$H(X)=0$$

Nothing remains to be learned.

---

Uniform distribution

For N equally probable outcomes:

$$p(x)=\frac1N$$

then:

$$H(X)=\log_2N$$

The uniform distribution maximizes entropy among distributions over the same finite alphabet.

Interpretation:

Uncertainty is maximal when no available outcome is preferred over another.

---

⚠️ Important: probability of a sequence is not pattern surprise

A useful opening example is ten consecutive heads:

HHHHHHHHHH

For a fair coin:

$$P(HHHHHHHHHH) = 2^{-10}$$

Therefore:

$$I(HHHHHHHHHH) = 10\text{ bits}$$

But the sequence:

HTHHTTHTTH

also satisfies:

$$P(HTHHTTHTTH) = 2^{-10}$$

Every exact sequence of ten fair coin tosses has the same probability.

So Shannon surprisal alone does not explain why:

HHHHHHHHHH

looks more remarkable.

This distinction is worth emphasizing rather than hiding.

---

🏵 Three different kinds of surprise

What humans casually call "surprising" may refer to several different mathematical ideas.

1. Outcome surprise
   ↓
   How improbable was this exact observation?

2. Pattern surprise
   ↓
   How improbable is the class or structure we noticed?

3. Model surprise
   ↓
   Does this observation make another model more plausible?

The first belongs directly to Shannon information.

The other two lead toward deeper theories.

---

💡 Pattern surprise

HHHHHHHHHH has a visible structure.

Humans rarely ask only:

What was the probability of this exact string?

We ask something closer to:

What was the probability of getting a sequence this regular?

That question describes an event, not a single sequence.

For example:

A = {all ten outcomes are identical}

Now:

$$P(A) = P(H^{10}) + P(T^{10}) = 2\cdot2^{-10} = 2^{-9}$$

The event captures the pattern we cared about.

This connects information theory back to the existing distinction between:

outcome
vs
event

---

🪄 Model surprise

After observing:

HHHHHHHHHH

we might begin comparing hypotheses.

For example:

H₀ : the coin is fair

H₁ : the coin is biased toward heads

The observation can alter our relative belief in these models.

This later connects to:

• likelihood
• likelihood ratios
• Bayes' theorem
• Bayesian updating
• evidence
• KL divergence

This should be noted but not introduced in the first Information chapter.

---

🔥 Algorithmic information is another question

There is also a deeper reason:

HHHHHHHHHH

can be described much more compactly than:

HTHHTTHTTH

For example:

"10 H"

is a short description.

This intuition eventually connects to:

• compression
• description length
• Kolmogorov complexity
• algorithmic information theory

This is distinct from Shannon information.

⚠️ Do not conflate them.

Shannon asks:

How improbable was the observation under a probability model?

Algorithmic information asks something closer to:

How short is the shortest description capable of generating it?

These become related in important ways, but they are not the same object.

---

🏵 Information depends on a model

This principle deserves explicit prominence.

Suppose we observe:

Head

Under:

$$P(H)=0.5$$

the information is:

$$I(H)=1\text{ bit}$$

But under:

$$P(H)=0.99$$

we obtain:

$$I(H) = -\log_2(0.99) \approx 0.0145\text{ bits}$$

Same observation.

Different model.

Different information.

Therefore:

Information is relational: it connects an observation with an expectation.

This is one of the most important ideas for later statistical inference.

---

🏵 Context changes information

Eventually the model may depend on context.

Instead of:

$$P(x)$$

we use:

$$P(x\mid c)$$

and therefore:

$$I(x\mid c) = -\log_2P(x\mid c)$$

This is central to language.

Consider:

I drink coffee with ___

A word such as:

milk

may have relatively high probability.

A word such as:

uranium

has very low probability.

Therefore:

$$I(\text{uranium}\mid\text{context}) > I(\text{milk}\mid\text{context})$$

The unusual word carries more surprisal.

⚠️ This does not imply that it carries more meaning.

It carries more information relative to that predictive context.

---

⚠️ Shannon information is not meaning

This distinction should be permanent in the project.

Shannon information does not measure:

• truth
• importance
• usefulness
• semantic meaning
• emotional relevance
• epistemic value

A completely meaningless random string may have very high Shannon entropy.

A profound but predictable statement may have low surprisal.

Therefore:

information ≠ meaning

The two can interact, but they should not be identified.

---

🏵 Proposed conceptual principles

These can act as the local canon for the Information section.

P₀ — Information requires a model

There is no surprisal without an expectation distribution.

---

P₁ — Rare observations carry more surprisal

$$p(x)\downarrow \Rightarrow I(x)\uparrow$$

---

P₂ — Certainty carries zero surprisal

$$p(x)=1 \Rightarrow I(x)=0$$

---

P₃ — Independent evidence adds

For independent observations:

$$I(x,y)=I(x)+I(y)$$

---

P₄ — Surprisal is logarithmic

$$I(x) = -\log_b p(x)$$

The base defines the unit.

---

P₅ — A bit resolves a binary distinction

$$-\log_2\left(\frac12\right)=1$$

---

P₆ — Surprisal belongs to an outcome

$$I(x)$$

describes one resolved observation.

---

P₇ — Entropy belongs to a distribution

$$H(X) = \mathbb E[I(X)]$$

---

P₈ — Uniformity maximizes entropy

Among finite distributions over the same number of possible outcomes, the uniform distribution contains the greatest uncertainty.

---

P₉ — Information is not semantic meaning

Shannon information measures probabilistic uncertainty, not importance or truth.

---

P₁₀ — Context changes information

$$I(x\mid c) = -\log_2P(x\mid c)$$

Prediction and information are therefore inseparable.

---

☯ Connection with the architecture of Data

The Information section should connect existing parts of the project rather than form an isolated branch.

A possible architecture is:

Reality
   │
   ▼
Sample Space
Ω
   │
   ▼
Events
𝒜
   │
   ▼
Probability
ℙ
   │
   ▼
Observable
X : Ω → 𝒳
   │
   ▼
Distribution
pX
   │
   ▼
Information
I(x)
   │
   ▼
Entropy
H(X)
   │
   ▼
Repeated observations
Data
   │
   ▼
Inference / Statistics

This creates a useful progression:

What could happen?
        ↓
What did we observe?
        ↓
How likely was it?
        ↓
How much did we learn?
        ↓
What structure can repeated observations reveal?

---

🏵 Ideas the first chapter should focus on

The introductory chapter should remain intentionally narrow.

Focus on:

rare vs common events

probability as expectation

surprise as resolved expectation

I(x) = -log₂ p(x)

bits

outcome surprisal vs distribution entropy

H(X) = E[I(X)]

one light linguistic example

Do not yet develop:

conditional entropy

mutual information

KL divergence

cross-entropy

channel capacity

coding theorem

Bayesian evidence

Kolmogorov complexity

These should appear only as conceptual doors.

---

💡 Suggested pedagogical beat

A simple chapter rhythm:

1. Common events teach us little.

2. Rare events attract attention.

3. Define surprisal.

4. Explain why the logarithm appears.

5. Interpret the bit.

6. Work through a small probability → bits example.

7. Distinguish observation surprisal from entropy.

8. Introduce entropy as expected surprisal.

9. Show a simple linguistic prediction example.

10. Stop.

A small interactive cell can then allow the reader to modify:

p

and observe:

$$-\log_2p$$

without introducing additional theory.

---

⚙️ Useful worked values

p = 1
I = 0 bits

p = 1/2
I = 1 bit

p = 1/4
I = 2 bits

p = 1/8
I = 3 bits

p = 1/16
I = 4 bits

p = 1/1024
I = 10 bits

The pattern should be visible before becoming abstract:

$$P=2^{-n} \quad\Rightarrow\quad I=n\text{ bits}$$

---

📚 Core sources

Ralph Hartley — 1928

Transmission of Information

Useful for the historical path toward logarithmic information and the relation:

$$I \propto \log N$$

Focus:

• distinguishable alternatives
• information as logarithm of available possibilities
• precursor to Shannon

---

Claude Shannon — 1948

A Mathematical Theory of Communication

Primary theoretical source.

Focus:

• entropy
• communication
• stochastic sources
• coding
• uncertainty

This should remain the canonical historical source.

---

Claude Shannon — 1951

Prediction and Entropy of Printed English

Particularly useful for the later linguistic hook.

Focus:

• predictability of language
• redundancy
• conditional uncertainty
• empirical estimation of language entropy

---

David MacKay

Information Theory, Inference, and Learning Algorithms

Probably the best pedagogical secondary reference for this project.

Focus:

• surprisal
• entropy
• coding
• probability
• inference
• machine learning connections

This source fits particularly well with the intended architecture of Data because it treats information theory as part of a larger theory of inference.

---

Cover & Thomas

Elements of Information Theory

Use as the technical reference.

Focus:

• entropy
• joint entropy
• conditional entropy
• mutual information
• relative entropy
• source coding
• channel capacity

Useful for verifying definitions and formal results rather than determining the introductory narrative.

---

A. I. Khinchin

Mathematical Foundations of Information Theory

Important for the axiomatic perspective.

Focus:

Why does Shannon entropy have this particular mathematical form?

Useful later for showing that entropy is not merely an arbitrary formula: under a suitable family of natural requirements, its logarithmic form is essentially forced.

---

🪄 Future conceptual branches

The Information section can eventually grow into several distinct paths:

Information
│
├── Surprisal
│
├── Entropy
│   ├── Joint entropy
│   └── Conditional entropy
│
├── Mutual information
│
├── Relative information
│   ├── KL divergence
│   └── Cross-entropy
│
├── Coding
│   ├── Huffman
│   ├── source coding
│   └── channel capacity
│
├── Inference
│   ├── likelihood
│   ├── Bayes
│   └── evidence
│
├── Language
│   ├── prediction
│   ├── surprisal
│   └── redundancy
│
└── Algorithmic Information
    ├── compression
    ├── description length
    └── Kolmogorov complexity

These should remain separate enough that similar vocabulary does not collapse distinct concepts.

---

🏵 Working definition for the project

A useful conceptual statement is:

Data is an observation. Information is what that observation resolves relative to what was expected.

A shorter formulation:

Information is resolved uncertainty.

This is useful as an intuition, but should not be presented as a universal philosophical definition of all possible forms of information.

---

☯ Final conceptual bridge

The deeper structure we want the reader eventually to recognize is:

Probability describes expectation.

Information measures the resolution of expectation.

Entropy describes expected resolution.

Data provides realized observations.

Statistics learns from their structure.

Or symbolically:

$$\Omega \rightarrow X \rightarrow p(x) \rightarrow -\log p(x) \rightarrow \mathbb E[-\log p(X)]$$

That chain should become one of the theoretical spines of Data.