What's the perfect encoding? How do you know?

2026-06-10 · Source: 3Blue1Brown · Field: Technology & Digital — Artificial Intelligence & Machine Learning, Data Science & Analytics · Depth: Advanced, quick

Summary

A puzzle challenges readers to determine the most efficient binary encoding for robot movement instructions on a distant moon. The robot's movements are limited to four possibilities: up, down, left, or right, following a biased random walk. Specifically, half of its movements are up, a quarter are down, 1/8 are left, and 1/8 are right. The puzzle requires first finding the encoding that uses the fewest bits per instruction and then rigorously proving its optimality against all other possible encodings. This exercise serves as an introductory step towards understanding Shannon entropy, forming the basis of a video series exploring the concept that "compression is intelligence."

Key takeaway

For AI students or research scientists exploring information theory fundamentals, this puzzle offers a concrete entry point into optimal data encoding. You should attempt to solve both parts: first, devise an encoding strategy that minimizes bits per instruction for the given probabilities, and then rigorously prove its efficiency. This hands-on exercise will deepen your understanding of how probability distributions directly influence encoding design and the core principles behind Shannon entropy.

Key insights

Optimal binary encoding for probabilistic events minimizes bits per instruction, foundational to Shannon entropy.

Principles

• Encoding efficiency correlates with event probability.
• Proving optimality requires demonstrating no better alternative.

Method

Find the most efficient binary encoding for given probabilistic events, then mathematically prove its optimality.

In practice

• Encode robot movement instructions based on probabilities.
• Apply information theory to data compression challenges.

Topics

• Binary Encoding
• Information Theory
• Shannon Entropy
• Data Compression
• Probabilistic Systems
• Robot Control

Best for: AI Scientist, Research Scientist, AI Student

Related on AIssential

• Reinventing Entropy | Compression & Intelligence Part 1 — Prediction and compression are mathematically equivalent, forming the basis for information theory and LLM pre-training objectives.
• Information-driven design of imaging systems — A new framework directly evaluates and optimizes imaging systems based on mutual information, unifying quality metrics and improving design efficiency.
• Demystifying Bit Manipulation: The Ultimate Guide to Parity Checks in Python — This guide delves into bit manipulation, specifically focusing on the classic parity check problem, a critical skill for AI Engineers, low-level system optimization, custom CUDA kernels, and Data Stru…
• Yes it's just doing compression. No it's not the diss you think it is. — Optimizing language models for next-word prediction via log-likelihood is a form of data compression, which can be linked to understanding.
• An Information-Theoretic Criterion for Efficient Data Synthesis — Synthetic data is effective only when external signals keep the training loop "information-open."
• Predictive Coding with Bayesian Priors via Proximal Gradients — Predictive coding is reinterpreted as continuous-time proximal gradient descent on a regularized maximum-a-posteriori objective.

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by 3Blue1Brown.