# Entropy Entropy is a metric to describe how likely a distribution will "surprise" when sampled. It is larger if there are many events with small probability and few with large probabilities. Given a discrete random variable $X$ with $n$ events, with probability $p_i$ for the i-th event - the Entropy is defined as $H(X):=-\sum_{i=0}^n p_i\log(p_i)$ . Entropy is the expectation of a distribution's uncertainty which is defined by $-\log (p_i)$. The intuition is that if uncertainty is high , the probability $p_i$ is very small and $-\log (p_i)$ is very large. if uncertainty is low e.g., when event has the probability of 1 then $-\log (1)=0$ . Note: 1) The english letters in text has entropy of ~1 compared to uniform over 26 letters plus space character $\log(27)$ ~ 4.75 2) Entropy is not changed when permuting letters. Entropy does not care what the events value are but only their histogram (i.e., probability distribution) ## Entropy is maximized for uniform distribution For uniform distribution with $n$ events, $H(X)=\log(n)$. Jensen’s Inequality for concave $f(x)$ i.e., $\frac{1}{n}\sum f(x_i)\le f(\frac{1}{n}\sum x_i)$. For $f(x)=-x\log(x)$ which is concave in $[0,1]$ and $x_i=p_i$ , we have $-\frac{1}{n}\sum p_i\log(p_i)\le -\frac{1}{n}\log(\frac{1}{n})$ as $\sum x_i=1$ . Therefore, $H(X)=-\sum p_i\log(p_i)\le -\sum \frac{1}{n}\log(\frac{1}{n})=\log(n)=H(\text{uniform})$ and we get $H(X)\le H(\text{Uniform})$ and equality is achieved only by the uniform distribution. This can be proved by Lagrange multipliers. ## How random is a string of bits? It can be used to define randomness level of a string (i.e., how much it is "similar" to uniform distribution) by computing the distribution of the letters based on a single long string. If the value is close to the entropy of uniform distribution then it more reasonable to treat the string as random. this can be repeated for computing the entropy of bigrams and trigrams and so on. increasing the size block to k (k-grams) requires $2^k$ blocks i.e., for large values of $k$ long strings are required. Tag: #math ## Created 2026-03-06 19:49