Proof. $H[X|Y]={\sum }_y\mathbb{P}[Y=y]H[X|Y=y]$.

Since $X$ and $Y$ are independent, the distribution of $X$ is unaffected by knowing $Y$ (so by invariance, $H[X|Y=y]=H[X]$), so

for all $y$, which gives the result. □

Proof. Lemma 1.1 and obvious induction. □

Proof. The case $n=2$ is additivity. In general,

so we are done by induction. □

Proof. The map $g:x\mapsto (x,f(x))$ is a bijection, and $(X,Y)=g(X)$. So the first statement follows by invariance. For the second statement:

Proof. $X$ and $X$ are independent. Therefore, by Lemma 1.1, $H[X,X]=2H[X]$. But by invariance, $H[X,X]=H[X]$. So $H[X]=0$. □

Proof. Let $X_1,\dots ,X_n$ be independent random variables uniformly distributed on $\{0,1\}$. By Corollary 1.2 and normalisation, $H[X_1,\dots ,X_n]=n$. But $(X_1,\dots ,X_n)$ is uniformly distributed on ${\{0,1\}}^n$, so by invariance, the result follows. □

Proof. Let $r$ be a positive integer and let $X_1,\dots ,X_r$ be independent copies of $X$.

Then $(X_1,\dots ,X_r)$ is uniform on $A^r$ and

Now pick $k$ such that $2^k\le n^r\le 2^{k+1}$. Then by invariance, maximality, and Proposition 1.6, we have that

So

Therefore, $H[X]=\log n$ as claimed. □

Proof. First we do the case where all $p_a$ are rational (and then can finish easily by the continuity axiom).

Pick $n\in \mathbb{N}$ such that for all $a$, there is some $m_a\in \mathbb{N}\cup \{0\}$ such that $p_a=\frac{m_a}{n}$.

Let $Z$ be uniform on $[n]$. Let $(E_a:a\in A)$ be a partition of $[n]$ into sets with $|E_a|=m_a$. By invariance we may assume that $X=a⟺Z\in E_a$. Then

Hence

By continuity, since this holds if all $p_a$ are rational, we conclude that the formula holds in general. □

Proof. Immediate consequence of Theorem 1.8. □

Proof. $H[X]=H[X,Y]=H[Y]+H[X|Y]$. But $H[X|Y]\ge 0$. □

Proof. Note that for any two random variables $X,Y$ we have

Next, observe that $H[X|Y]\le H[X]$ if $X$ is uniform on a finite set. That is because

By the equivalence noted above, we also have that $H[X|Y]\le H[X]$ if $Y$ is uniform.

Now let $p_{ab}=\mathbb{P}[(X,Y)=(a,b)]$ and assume that all $p_{ab}$ are rational. Pick $n$ such that we can write $p_{ab}=\frac{m_{ab}}{n}$ with each $m_{ab}$ an integer. Partition $[n]$ into sets $E_{ab}$ of size $m_{ab}$. Let $Z$ be uniform on $[n]$. Without loss of generality (by invariance) $(X,Y)=(a,b)⟺Z\in E_{ab}$.

Let $E_b={\cup }_a{E}_{ab}$ for each $b$. So $Y=b⟺Z\in E_b$. Now define a random variable $W$ as follows: If $Y=b$, then $W\in E_b$, but then $W$ is uniformly distributed in $E_b$ and independent of $X$ (or $Z$ if you prefer).

So $W$ and $X$ are conditionally independent given $Y$, and $W$ is uniform on $[n]$.

Then

By continuity, we get the result for general probabilities. □

Proof (Without using formula). By Subadditivity, $H[X|X]\le H[X]$. But $H[X|X]=0$. □

Proof. Induction using Subadditivity. □

Proof. Calculate:

Proof.

Proof. Submodularity says:

which implies the result since $Z$ depends on $X$ and $Y$. □

Proof. Let $p_a=\mathbb{P}[X=a]$. Then

The function $x\mapsto x\log \frac{1}{x}$ is concave on $[0,1]$. So, by Jensen’s inequality this is at most

Equality holds if and only if $a\mapsto p_a$ is constant – i.e. $X$ is uniform. □

Proof. We go through the proof of Subadditivity and check when equality holds.

Suppose that $X$ is uniform on $A$. Then

with equality if and only if $H[X|Y=y]$ is uniform on $A$ for all $y$ (by Lemma 1.17), which implies that $X$ and $Y$ are independent.

At the last stage of the proof we used

where $W$ was uniform. So equality holds only if $X$ and $W$ are independent, which implies (since $Y$ depends on $W$) that $X$ and $Y$ are indpendent. □