1 of 4

Your RightSignal

Algorithms · 10 of 131 / 3

Entropy

The concept

Why a fair coin flip is worth exactly one bit

Entropy measures how surprising a source of symbols is on average, in bits. The surprise of one outcome with probability p is −log₂ p bits: a sure thing (p = 1) tells you 0 bits, and a 1-in-8 event tells you 3 bits.

A fair coin has two outcomes at p = ½, so each flip carries exactly 1 bit: one yes-or-no answer. A coin that lands heads 99% of the time carries far less, because you could almost always guess the result before seeing it.

Entropy is the weighted average of those surprises over all outcomes. It is highest when every outcome is equally likely and drops as the source gets more predictable.

What it’s forMeasures the average surprise of a source whose outcomes have known probabilities.

H = −Σ pᵢ · log₂ pᵢ

H
the entropy, in bits per symbol
pᵢ
the probability of outcome i, e.g. 0.5 for heads on a fair coin
−log₂ pᵢ
the surprise of outcome i in bits; rarer outcomes give bigger numbers
Σ
add up over every possible outcome

What it givesThe average number of bits of real news each symbol carries.

  1. Letters A, B, C, D with p = ½, ¼, ⅛, ⅛ have surprises 1, 2, 3, 3 bits
  2. H = ½·1 + ¼·2 + ⅛·3 + ⅛·3 = 0.5 + 0.5 + 0.375 + 0.375
  3. H = 1.75 bits per letter, less than the 2 bits a fixed code would use