Ruzsa Triangle Inequality

Let . Then

Proof

Define functions and by Also define by

We now just need to show that is injective. Suppose . Then

so we conclude

But by definition and , so . It trivially follows that , so is injective.

Theorem

Let , , be Random Variables. Then Mathematical Entropy satisfies:

Proof

By Data Processing Property of the Mutual Information:

and the inequality will follow.

Corollary

Let and be iid. Then

Proof

Firstly, for any :

so taking with iid with and we find

This gives the bound.