INFOTH Note 1: Axioms & Def of Entropy
1.1 Definition of the Shannon Entropy
To (re)invent the entropy, we need to let this quantity follow some axioms. Let the entropy be \(H(\cdot)\).
\(H\) can also wrap distribution like \(p_1,...,p_n\), or just be fed with a distribution tuple \(p\), or a random variable \(X\).
Def 1.1.1 Shannon Entropy
Consider a discrete probability distribution \(p=(p_1,\dots,p_n)\) on the set \(\mathcal X=\{1,\dots,n\}\).
The Shannon Entropy of \(p\) is defined by
\[ H(p)=-\sum_{x\in\cal X}p_x\log p_x. \]- \(\log:=\log_2\), as this is Shannon’s convention (and also will be ours)
- We have defined the entropy only on a finite set.
- We also allow \(H\) to wrap a tuple like this: \(H(p)=H(p_1,\dots,p_n)\).
Def 1.1.2 Entropy of a Random Variable
Given a discrete r.v. \(X\) over a finitely many set \(\cal X\), we write the entropy as
\[ H(X)=H(p_X)=-\sum_{x\in\cal X}p_x\log p_x=-\sum_{x=1}^dP(X=x)\log P(X=x). \]We can also write this in an expectation form:
\[ H(X)=E[-\log p_X(X)]=E[1/\log P(X)] \]Surprisal / Information Content
We can see the expectation of a thing is the entropy. And the thing is called the information content / surprisal for one event \(X=x\):
\[ I_X(x)=-\log p_X(x);\quad H(X)=E[I_X(X)]. \]Lemma 1.1.3
For the entropy defined in 1.1.2, \(H(X)\ge 0\).
Lemma 1.1.4
\[ H_b(X)=(\log_b a)H_a(X) \]where \(H_y(X)\) is the entropy where the log base is \(y\). Of course, \(H_y(X)=(\log_y 2)H(X)\).
- When we want to maximize / minimize an entropy, we can easily exchange the log base to make it convenient w/o a constant.
1.2 Motivation of the Shannon Entropy: Axioms
1.2.1 Axiom 1:
Fair Coin Toss: Random Var \(X\in\{H,T\}\), \(P(X=H)=P(X=T)=1/2\).
We attribute 1 as \(H(X)=1\) with \(H(\frac12,\frac12)=1\)
1.2.2 Axiom 2:
For a finite distribution \(p=(p_1\dots p_n)\),
\[ H(p_1,\cdots,p_n)=H(p_1+p_2,p_3,\cdots,p_n)+(p_1+p_2)H({p_1\over p_1+p_2},{p_2\over p_1+p_2}). \]More generally, for any subset \(A\subseteq\cal X\):
\[ H(p_1\dots p_n)=H(\sum_{x\in A}p_x,\{p_y,y\notin A\})+(\sum_{x\in A}p_x)H(\{p_x/\sum_{x\in A}p_x|x\in A\}) \]- Probability Merging
- 合并的概率体现在第一项里的同时，合并项内部消化需要另外一项
Corollary from Axiom 2: Proposition of Independence
\(X\perp\!\!\!\perp Y\), \(P(X,Y)=P(X)P(Y)\), from Axiom 2, \(H(X,Y)=H(X)+H(Y)\)
Proof:
\[ \begin{align*} H(X,Y)&=H(p_1q_1,p_1q_2,\cdots,p_nq_m) \\&=H(\sum_j p_1q_j,p_2q_1,p_2q_2,\cdots,p_nq_m)+(\sum_jp_1q_j)H({p_1q_1\over \sum_jp_1q_j},\cdots,{p_1q_m\over \sum_jp_1q_j}) \\&=H(p_1,p_2q_1,p_2q_2,\cdots,p_nq_m)+p_1H({p_1q_1\over \sum_jp_1q_j},\cdots,{p_1q_m\over \sum_jp_1q_j}) \\&=p_1H({p_1q_1\over \sum_jp_1q_j},\cdots,{p_1q_m\over \sum_jp_1q_j})+H(p_1,p_2q_1,p_2q_2,\cdots,p_nq_m) \\&=p_1H(q_1,\cdots,q_m)+H(p_1,p_2q_1,p_2q_2,\cdots,p_nq_m) \\&=p_1H(q_1,\cdots,q_m)+p_2H(q_1,\cdots,q_m)+H(p_1,p_2,p_3q_1,p_3q_2,\cdots,p_nq_m) \\&=(\sum_i p_i)H(q_1,\cdots,q_m)+H(p_1,p_2,\cdots,p_n) \\&=H(q)+H(p)=H(p)+H(q)=H(X)+H(Y). \end{align*} \]1.2.3 Axiom 3:
\(p\mapsto H(p,1-p),p\in[0,1)\) should be a continuous function.
1.2.4 Axiom 4:
\(H(p)\) is invariant to permutations of \((p_1,p_2,\cdots, p_n)\).
\[ \forall \sigma=\text{Perm}(p),H(\sigma)=H(p). \]Theorem 1.2.5 Unique Entropy Function
Only one choice for \(H\).
There is only one choice for \(H\) given a finite-state distribution. (for infinitely many states, this will also apply but we will discuss this later).
\[ H(p_1,\cdots,p_n)=-\sum_{x=1}^n p_x\log_2 p_x \]Verification of Axiom 3
\[ p\mapsto H(p,1-p)=-p\log_2p - (1-p)\log_2(1-p) \]- is continuous
- More importantly, it’s convex.
1.3 Concavity of Shannon Entropy
Theorem 1.3.1 Convexity of \(x\log x\)
\[ f:x\mapsto x\ln x~~(x>0),\quad f'(x)=\ln x+1, \quad f''(x)=\frac1x>0. \](We complement here as \(0\log 0=0\) as it’s the limit value)
Def 1.3.2 Convex Set
A subset \(K\subseteq \R^d\) is called a convex set if and only if
\[ \forall v,w\in K,\forall \lambda\in[0,1]\implies \lambda v+(1-\lambda)w\in K. \]Def 1.3.3 Probability Simplex
At \(d\ge 2\), the set of probability functions on \(\mathcal X=\{1,\dots,d\}\) is called the probability simplex or the unit \(d\)-simplex, written as
\[ \Delta_{\cal X}=\{(p(1),\dots,p(d)):p(i)\ge 0,\sum_{i=1}^dp(i)=1\}. \]This simplex is also a convex set, which means every weighted average with weight in \([0,1]\) of the probabilities will fall on this simplex, well defining the convexity/concavity of entropy-related quantities.
Theorem 1.3.4 Concavity of Shannon Entropy
\(H\) is here defined as a function of probability functions \((p(x), x\in{\cal X})\), on the probability simplex for fixed \(d\):
\[ \forall p_0,p_1\in\Delta_{\cal X},\forall \lambda\in[0,1],\quad p_\lambda(x):=\lambda p_1(x)+(1-\lambda)p_0(x), \]then
\[ H(p_\lambda)\ge \lambda H(p_1)+(1-\lambda)H(p_0). \]Proof Sketch
This can be derived from the convexity of \(u\log u\) (i.e. concavity of \(-u\log u\)).
Theorem 1.3.5 Upper Bound of Entropy = Uniform
The uniform distribution on finite \(\{1,\cdots,d\}\) has the largest entropy among probability distributions on this set.
Proof
Let \(S_d\) denote the set of all permutations of \(\mathcal X=\{1,\cdots,d\}\). Then given any probability distribution \(p\) (written as a probability vector)
\[ (1/d,\cdots,1/d)={1\over d!}\sum_{\sigma_{\cal X}\in S_d}(p(\sigma_1),p(\sigma_2),\cdots,p(\sigma_d)), \]where \(\sigma_{\cal X}\) denotes one permutation in the set, and \(\sigma_i\) denote the \(i\)-th entry of that permutation.
The permutations here are equivalent to the permutations of a probability vector.
Here we apply the average of probability vectors, where every dimension of this vector is
\[ {(d-1)!\sum_{i\in\mathcal X}p(i)\over d!}=\frac1d. \]Given \(H\) is concave in 1.3.4,
\[ H(1/d,\cdots,1/d) \ge {1\over d!}\sum_{\sigma\in S_d}H(p(\sigma_1),\cdots,p(\sigma_d)), \]plus from the axiom 4 (1.2.4), the entropy value is invariant to permutations: \(RHS=H(p)\), Q.E.D.
Corollary: Upper Bound Value
\[ \sup_{p_X} H(X)=\log |\cal X|. \]where \(X\) has a distribution \(p_X\) on the domain \(\mathcal X\).
Proof. Just calculate the value of the uniform distribution of dimension \(d\).