Entropy, Information, and Coding TODO

Math · Day 49 / 52 · December — Cryptography & Information Theory (Day 44-52)

Concept

The information content of an event is defined as the log of the reciprocal of its probability, and entropy is the expected value of that quantity — the average uncertainty of a distribution. When the log base is 2, the unit is bits, and for a fixed number of outcomes, entropy is maximized by the uniform distribution. The source coding theorem says the average length of a lossless code can never be shorter than the entropy, and Huffman or arithmetic coding can approach that limit arbitrarily closely. Relative entropy (KL divergence) is the extra cost paid for encoding under an incorrect assumed distribution, and mutual information is how much one variable's uncertainty is reduced by knowing another. This maximum-entropy view is the standard by which key and randomness strength is measured, in bits.

The theoretical limits of compression, the actual entropy of seeds and passwords, and judging the information content of logs or features all hinge on this — overestimating entropy leads to using randomness that feels secure but isn't.

Code & Formula

# 엔트로피·정보·코딩 — 사건 하나의 정보량 -log2(p), 그리고 분포 전체의 섀넌 엔트로피.

import math

def entropy(probs: list[float]) -> float:
    return -sum(p * math.log2(p) for p in probs if p > 0)


fair_coin = [0.5, 0.5]
biased_coin = [0.9, 0.1]
fair_die = [1 / 6] * 6

for name, dist in [("공정한 동전", fair_coin), ("치우친 동전(0.9/0.1)", biased_coin), ("주사위", fair_die)]:
    h = entropy(dist)
    print(f"{name:20} H = {h:.4f} bits  (최대 = log2({len(dist)}) = {math.log2(len(dist)):.4f})")

# 치우친 분포일수록 "다음 결과가 뭘지 이미 어느 정도 안다" → 엔트로피(불확실성)가 낮다.

docs/code/math/math-49.py

Exercise

Compute the entropy from character frequencies in a text file, compare it to its gzip compression ratio, and directly calculate the entropy in bits carried by a 12-word mnemonic.

Practical Connection

The security of private keys and seeds is ultimately defined by their entropy in bits, and the fact that LMSR's cost function takes a log-sum-exp form comes from the same mathematical root — entropy and exponential families.

If you study this on a given day, add a note link and a ✅ to this line in the source curriculum (docs/knowledge/math-50-curriculum.md) and this spot will lead straight to the note body. You can also write directly on this page — but regenerating overwrites it, so it's safer to keep anything you want to save as markdown under docs/algorithms/.

한국어

엔트로피·정보·코딩 TODO

Math · Day 49 / 52 · 12월 — 암호학·정보이론 (Day 44–52)

개념

한 사건의 정보량은 그 확률의 역수에 로그를 취한 값으로 정의되고, 엔트로피는 그 기대값이라 분포의 평균 불확실성을 나타낸다. 로그의 밑이 2이면 단위는 비트이고, 원소 수가 정해졌을 때 균등분포에서 엔트로피가 최대가 된다. 소스 코딩 정리에 따르면 무손실 부호의 평균 길이는 엔트로피보다 짧아질 수 없고, 허프만이나 산술부호화로 그 한계에 임의로 가깝게 접근할 수 있다. 상대 엔트로피(KL 발산)는 틀린 분포를 가정하고 부호화했을 때 치르는 추가 비용이고, 상호정보량은 한 변수를 알았을 때 줄어드는 다른 변수의 불확실성이다. 이 최대 엔트로피 관점이 키와 난수의 강도를 비트 수로 재는 기준이 된다.

압축의 이론적 한계, 시드·패스워드의 실제 엔트로피, 로그나 특징의 정보량 판단이 모두 여기 걸려 있어서, 엔트로피를 과대평가하면 안전하다고 착각한 난수를 쓰게 된다.

코드 · 수식

# 엔트로피·정보·코딩 — 사건 하나의 정보량 -log2(p), 그리고 분포 전체의 섀넌 엔트로피.

import math

def entropy(probs: list[float]) -> float:
    return -sum(p * math.log2(p) for p in probs if p > 0)


fair_coin = [0.5, 0.5]
biased_coin = [0.9, 0.1]
fair_die = [1 / 6] * 6

for name, dist in [("공정한 동전", fair_coin), ("치우친 동전(0.9/0.1)", biased_coin), ("주사위", fair_die)]:
    h = entropy(dist)
    print(f"{name:20} H = {h:.4f} bits  (최대 = log2({len(dist)}) = {math.log2(len(dist)):.4f})")

# 치우친 분포일수록 "다음 결과가 뭘지 이미 어느 정도 안다" → 엔트로피(불확실성)가 낮다.

docs/code/math/math-49.py

연습

텍스트 파일의 문자 빈도로 엔트로피를 계산해 gzip 압축률과 비교하고, 니모닉 12단어가 갖는 엔트로피 비트 수를 직접 계산해보라.

실무 · Verex 연결

개인키와 시드의 안전성은 결국 엔트로피 비트 수로 정의되며, LMSR 비용함수가 log-sum-exp 형태를 갖는 것도 엔트로피와 지수족이라는 같은 수학적 뿌리에서 나온다.

공부한 날 원본 커리큘럼(docs/knowledge/math-50-curriculum.md)의 이 줄에 노트 링크와 ✅ 를 붙이면, 이 자리는 노트 본문으로 바로 이어집니다. 노트 없이 이 페이지에 바로 적어도 됩니다 — 다만 다시 생성하면 덮어쓰이므로, 남길 글은 docs/algorithms/ 의 마크다운으로 쓰는 편이 안전합니다.