3Blue1Brown
June 10, 2026
Optimal Binary Encoding and Shannon Entropy
TL;DR
A puzzle about efficiently encoding robot movement instructions using binary reveals the optimal encoding strategy and introduces the concept of Shannon entropy.
Key Takeaways
- 1The most efficient encoding assigns shorter bit sequences to more frequent instructions (up movement at 50%) and longer sequences to less frequent ones (down, left, right at 25%, 12.5%, 12.5%)
- 2This encoding problem is foundational to understanding Shannon entropy and information theory
- 3Proving optimality requires demonstrating that no alternative encoding scheme can achieve better average bits-per-instruction performance
- 4The biased random walk distribution of movements directly determines the efficiency ceiling for any encoding method
Notable Quotes
“If you can answer this question, it's the first step towards reinventing the idea of Shannon entropy.”
Chapters
1. The Robot Movement Problem
A thought experiment about sending instructions to a robot on a distant moon that can move in four directions (up, down, left, right) with different probability distributions.
2. Movement Probabilities
The robot follows a biased random walk where up movements occur 50% of the time, down 25%, and left/right each 12.5% of the time.
3. Binary Encoding Challenge
Find the most efficient way to encode these movement instructions into binary, minimizing bits per instruction.
4. Proving Optimality
The challenge mode requires proving that the found encoding is truly optimal and no other encoding method could perform better.
5. Connection to Shannon Entropy
Solving this puzzle is the first step toward understanding Shannon entropy and the theoretical limits of data compression.
Glossary
- Binary encoding
- Representing information using sequences of 0s and 1s (bits)
- Biased random walk
- A random movement pattern where different directions have different probabilities rather than equal chances
- Shannon entropy
- A measure of the average information content or uncertainty in a message, determining the theoretical limit for data compression
- Bits per instruction
- The average number of binary digits required to encode a single movement command