LearnViz CompSci
Home / Learn / Theory & Discrete Math / Information Theory

Advanced Topic 46 of 51 Theory & Discrete Math

Information Theory

Quantifying information and entropy.

How it works

Information theory, founded by Claude Shannon in 1948, quantifies information and communication limits. Entropy measures the average uncertainty or information content of a random source in bits, H equal to minus the sum of p log p. Key results include the source coding theorem, which gives the lower bound on lossless compression, and the noisy-channel coding theorem, which states that reliable communication is possible at any rate below the channel capacity. Related measures are mutual information, cross-entropy and KL divergence.

Step-by-step walkthrough

  1. Information measures surprise.
  2. A fair coin flip carries 1 bit.
  3. A biased coin carries less.
  4. A certain event carries none.
  5. Entropy is the average surprise and sets the limit on lossless compression.

Where it is used

Data compression, error-correcting codes, cryptography, machine-learning loss functions, decision tree splitting, telecommunications and neuroscience use information theory.

Common pitfall

Entropy depends on the probability model, so wrong assumptions give wrong bounds. Confusing information with meaning is common: entropy measures surprise, not importance. Compression cannot beat entropy on average, and random data is incompressible. Capacity results are asymptotic and need long codes, which add delay. Use log base 2 for bits and be careful with zero probabilities.

Where it fits in the course

Information Theory is topic 46 of 51 in Theory & Discrete Math, rated Advanced. It follows Lambda Calculus. The next topic is Kolmogorov Complexity.

Practice and explore

How to study this topic

  1. Read the explanation above and restate the definition in your own words.
  2. Open the interactive lesson and answer its mini quiz.
  3. Read the common pitfall, then write a short example that avoids it.
  4. Check your understanding in the Theory & Discrete Math quiz, and revisit the topic if you miss a question.

Frequently asked questions

What is Information Theory?
Quantifying information and entropy. It belongs to Theory & Discrete Math and is an advanced-level topic.
Where do people use Information Theory?
Data compression, error-correcting codes, cryptography, machine-learning loss functions, decision tree splitting, telecommunications and neuroscience use information theory.
What is the most common mistake with Information Theory?
Entropy depends on the probability model, so wrong assumptions give wrong bounds.
What should I learn before this topic?
Start with Lambda Calculus, the topic just before it in Theory & Discrete Math.
How can I practice it?
Answer the mini quiz in the interactive lesson, then take the Theory & Discrete Math quiz.
Is Information Theory hard to learn?
It is an Advanced topic. Expect to read the explanation more than once and to connect it with earlier topics. Working through a small example by hand helps most.
How long does it take to learn Information Theory?
Most learners can read the explanation and finish the interactive lesson in under an hour. Fluency comes from applying the idea, so plan a few short practice sessions with the quiz.
Which topics are related to Information Theory?
Lambda Calculus, Kolmogorov Complexity, Parameterized Complexity are closely connected. The full list is in the related topics section of this page.
What should I study after Information Theory?
Continue with Kolmogorov Complexity, the next topic in Theory & Discrete Math.

Related topics