Information Theory

← Back to Domain-Specific Abstractions by Domain

13 domain-specific abstractions whose origin domain is Information Theory.

• Asymptotic equipartition property — The information-theoretic property that long source sequences concentrate on a typical set whose members have nearly equal exponential probability.
• Binary entropy function — The Shannon entropy of a Bernoulli variable as a concave function of its success probability.
• Binary erasure channel — A memoryless channel model that delivers each input bit correctly or replaces it with an explicit erasure symbol at a fixed probability.
• Blahut–Arimoto algorithm — A family of alternating iterative optimization algorithms for channel capacity and rate-distortion problems that updates distributions until the information-theoretic objective converges.
• Directed information — An information-theoretic quantity summing the conditional information that the present and past of one process provide about each current value of another given the latter's past.
• Error-Correcting Codes with Feedback — Channel codes whose encoder causally adapts later transmissions to receiver-side information returned over a feedback link, with reliability, rate, delay, stopping, and feedback-noise assumptions stated as part of the code.
• Information dimension — The asymptotic growth rate of the Shannon entropy of increasingly fine quantizations of a random variable or distribution.
• Krichevsky–Trofimov estimator — Estimate categorical symbol probabilities by adding one-half to every observed count, the Jeffreys-prior predictive rule that attains asymptotically minimax worst-case coding regret.
• Min-entropy — The negative logarithm of the largest outcome probability, measuring worst-case single-guess unpredictability as the order-infinity Rényi entropy.
• Nat (unit) — The unit of information associated with natural logarithms, equal to the information in an event of probability 1/e and to 1/ln 2 bits.
• Shannon capacity of a graph — A graph invariant giving the asymptotic zero-error information rate of a confusability graph under repeated independent channel uses.
• Shannon–Fano–Elias coding — A prefix-coding construction that chooses codewords from binary expansions of cumulative-probability midpoints.
• Typical set — The high-probability set of long source sequences whose per-symbol information is close to the source entropy.