How many bits does a message need? The surprising answer is: tell me what the receiver already knows.
If I ask you to identify a card chosen from a full deck, you face many possibilities. If I first tell you the card is a heart, your uncertainty shrinks. If I also tell you it is a face card, fewer possibilities remain.
The card itself did not change. The receiver’s knowledge did.
This is the world of side information: information available alongside the message that can reduce how much new description is required.
Quick Read
- Description length depends on uncertainty, and uncertainty depends on prior knowledge.
- Side information is correlated information available to the encoder, decoder or both.
- Conditional entropy measures the remaining uncertainty in one variable after another is known.
- If two sources are strongly related, one can help describe the other.
- Previous frames, reference genomes, maps, dictionaries and neighbouring sensors can all act as side information.
- Side information must be available where the decoding argument assumes it is available.
- A tiny payload can therefore be misleading if we ignore the correlated information already present at the receiver.
The One-Sentence Answer
Side information reduces compression cost when knowledge already available to the receiver removes uncertainty about the message, leaving fewer genuinely new possibilities that must be distinguished.
The Twenty Questions Version
Imagine I choose one animal from a list of 1,024 equally plausible animals. In a perfectly balanced yes-or-no questioning game, identifying it could require about ten binary decisions.
Now suppose you already know it is a bird, and only 32 birds appear on the list. The remaining uncertainty is much smaller.
Side information has compressed the search space before the explicit message begins.
This is why “How much information is in X?” is often incomplete. A sharper question is “How much information does X provide given Y?”
Conditional Entropy: What Remains Unknown?
Information theory formalises this with conditional entropy. If X is the message and Y is related side information, H(X|Y) represents the average uncertainty remaining about X once Y is known.
If Y tells us nothing about X, conditional entropy remains high. If Y almost determines X, little uncertainty remains.
The key idea is relational:
information needed = what the receiver still cannot infer
Yesterday Can Compress Today
A weather map today often resembles yesterday’s map. A video frame resembles nearby frames. A document revision resembles its previous version. A sensor reading resembles recent readings.
Instead of describing the new object independently, a system can describe its differences from a reference.
new state = known reference + new information
The reference is side information. The delta carries what changed.
This connects with Borrowed Space, but the present question is sharper: exactly why does the reference help? Because correlation reduces conditional uncertainty.
A Reference Genome Can Make Another Genome Cheaper
Human genomes share enormous amounts of structure. If both sender and receiver possess an agreed reference genome, another genome can often be represented partly as differences from that reference rather than as an entirely independent sequence.
The reference does not make biological variation disappear. It gives common structure somewhere to live.
The remaining message concentrates on substitutions, insertions, deletions and other differences according to the chosen representation.
Two Cameras Watching the Same Street
Suppose two cameras observe overlapping views. Their images are not identical, but they share information about the same cars, weather, lighting and movement.
In principle, knowledge from one stream can reduce uncertainty about the other. Distributed source-coding theory explores remarkable cases in which correlated sources can be encoded separately yet decoded jointly with rates approaching what their statistical relationship permits.
The famous Slepian–Wolf result shows how powerful correlation can be even when encoders do not fully cooperate in the ordinary way.
The larger lesson is simple: information can be physically distributed yet statistically connected.
The Decoder-Side Surprise
One of the most counterintuitive ideas in information theory is that useful side information does not always need to be available to the encoder in the same way it is available to the decoder.
Under particular assumptions, clever codes can exploit correlation that becomes available during joint decoding.
This is not magic. The code is designed around a statistical model of how the sources relate. The decoder uses its side information to narrow which candidate source sequence is consistent with the received code.
A Dictionary Is Side Information
If both sides already possess a dictionary containing common phrases, the sender can refer to entries instead of spelling them out.
The dictionary reduces uncertainty because a short identifier selects among known alternatives.
Again, the payload is small because the receiver contributes information.
This is why measuring only the payload can create absurd claims. A one-byte index into a terabyte database is not a one-byte self-contained representation of the selected object.
Context Is Side Information in Conversation
Someone texts:
Same place?
Two words may be enough between close friends. To a stranger, they are nearly useless.
The difference is shared context. Previous conversations, routines and relationships supply side information.
Human communication is extraordinarily compressed because people rarely transmit the whole world. They transmit the difference between what the receiver already knows and what the receiver needs next.
Mutual Information: How Much Do Two Things Tell Us About Each Other?
Another information-theoretic quantity, mutual information, captures how much knowing one variable reduces uncertainty about another on average.
If two variables are independent, knowing one does not help predict the other and their mutual information is zero. If they are strongly related, knowledge transfers.
Compression can exploit that shared structure.
We can think of mutual information as the portion of uncertainty that does not need to be paid twice when the relationship is properly modelled.
Side Information Can Be Wrong
What happens if sender assumes the receiver has version 7 but the receiver has version 6?
A delta may reconstruct the wrong object. A dictionary reference may point somewhere unintended. A cached resource may be stale.
Side information therefore creates a synchronisation obligation. Systems need version identifiers, hashes, negotiation or other ways to ensure both sides are referring to compatible state.
Borrowed information becomes dangerous when the lender is missing.
Side Information Has an Acquisition Cost
Suppose a shared dictionary reduces every future message by 20%. Wonderful. But how did the dictionary reach the receiver?
If it cost 100 MB to distribute and we only send one 1 KB message, the bargain is terrible. If millions of messages reuse it, the setup cost may become negligible per message.
This is amortisation. Side information pays when reuse is large enough.
Education: Prior Knowledge Changes Lesson Length
A teacher explaining simultaneous equations to a student who already understands algebra can move quickly. The same lesson for a learner who struggles with negative numbers may require far more explanation.
The topic is the same. The receiver state differs.
This is why good teaching diagnoses prerequisites. Prior knowledge acts as side information that makes new instruction shorter and more meaningful.
Primary School: One Clue Changes the Search
Ask a child to guess a number from 1 to 100. Then reveal that it is even. Then reveal that it is greater than 80.
Each clue reduces the remaining possibilities.
The child can feel conditional uncertainty shrinking without needing formal notation.
Secondary School: Describe B Given A
Give students two similar diagrams. Ask them first to describe diagram B from scratch. Then ask them to describe B assuming the listener already has A.
The second description should focus on differences. Students have discovered conditional description length.
JC and Beyond: Conditional Entropy Sets the Target
At higher levels, conditional entropy H(X|Y) becomes the natural lower-bound quantity when Y is available as side information under the relevant coding setup.
The Slepian–Wolf theorem goes further for correlated sources, showing that separate encoders can, asymptotically and under its assumptions, achieve a joint rate region governed by conditional and joint entropies.
This is one of information theory’s most beautiful corrections to naive intuition: physical separation of encoders does not necessarily force us to pay independently for statistically shared information.
A Side-Information Checklist
- What related information already exists at the receiver?
- How strongly is it correlated with the new message?
- Does the encoder also know it?
- How was the side information acquired?
- Can its cost be amortised across many messages?
- How do we verify that sender and receiver have matching versions?
- What happens when the side information is unavailable?
- Are we measuring the payload or the whole reconstruction system?
The Deeper Point
A message does not have one universal length independent of its receiver.
The number of bits we need depends on what uncertainty remains after everything already known has done its work.
This makes compression relational.
The shortest useful message is often not the smallest description of the world. It is the smallest description of what the receiver still needs to learn.
Explore the How Compression Works.