2026 - DNA Discovery

And More, ()


Topics - Prediction and Compression

In information theory, compression and prediction are essentially two sides of the same coin.
Claude Shannon, in his foundational work, revealed a core principle: the more accurate your
predictions of your data, the smaller you can compress it.

Better prediction → lower surprisal → fewer bits

Ideal coding length

L(x₁:ₜ) = −Σₜ₌₁ᵀ log₂ P(xₜ x<ₜ)
where P(xₜ x<ₜ) is the probability of the next symbol xₜ given all previous symbols.


Concept Meaning
Core relationship Better prediction → lower surprisal → fewer bits
Sequence x₁, x₂, …, xₜ
Ideal coding length L(x₁:ₜ) = −Σₜ₌₁ᵀ log₂ P(xₜ | x<ₜ)
Conditional probability P(xₜ | x<ₜ) is the probability assigned to the next symbol xₜ given all previous symbols.
Surprisal −log₂ P(xₜ | x<ₜ) measures how unexpected the observed symbol is.
Highly predictable symbol A high-probability symbol has low surprisal and requires fewer bits.
Unexpected symbol A low-probability symbol has high surprisal and requires more bits.
Total compression cost The coding length of the full sequence is the sum of the surprisal values of all symbols.
Main conclusion Probabilistic prediction and entropy-based compression are two views of the same mathematical process.





Three Compression Boundaries

Layer Core Question Mathematical Form Meaning
1. Information-Theoretic Boundary What is the minimum number of bits required under ideal conditions? Lossless: $H(X)$
Lossy: $R(D)$		 This is the fundamental theoretical limit determined by the source distribution and, for lossy compression, the chosen distortion measure. It assumes an ideal probability model, arbitrarily long coding blocks, and no practical limits on computation, memory, or latency.
2. Algorithmic Boundary What is the best compression achievable under a finite computational budget? $T(n) \le B$, therefore $R_B(D) \ge R(D)$ The information-theoretic optimum may require prohibitively expensive or intractable search. A practical algorithm explores only a restricted set of encoding decisions, so its best achievable rate is generally no better than the theoretical rate–distortion limit.
3. Format and System Boundary What is achievable after imposing real deployment constraints? $R_{\mathrm{sys}}(D) \ge R_B(D) \ge R(D)$ A real codec must satisfy bitstream syntax, decoder complexity, memory limits, latency, random access, parallelism, error resilience, streaming, hardware support, and backward compatibility. These constraints further reduce the feasible solution space.



































References 1

















References 2





























References













References