Posted onEdited onWord count in article: 3.6kReading time ≈13 mins.
Supplementary material on information theory. This document collects
the proofs of key theorems and derivation details referenced in the main
text, organized into five sections: Mathematical Tools, Channel,
Rate-Distortion Function, Source Coding, and Channel Coding. All
conclusions marked “see Appendix for proof” in the main text can be
found here.
This section presents two fundamental inequalities repeatedly used in
information theory. They underpin a series of core results including the
non-negativity of relative entropy, entropy maximization, and the
convexity of mutual information.
Jensen’s Inequality
Convex function. For any and any , if the following
inequality holds: then the function is
said to be a convex function on the interval . If the inequality above holds only
when or , then is said to be a strictly convex
function on .
If a function has a
non-negative (positive) second derivative on an interval, then is (strictly) convex on that
interval.
Jensen’s Inequality. For any convex function and random variable , we have:
Jensen’s inequality can be used to prove the non-negativity of
relative entropy.
Log Sum Inequality
Log sum inequality. For non-negative numbers and non-negative
numbers , we
have:
Equality holds if and only if .
Channel
The
Decomposability Property of Quasi-Symmetric Discrete Memoryless
Channels
The channel capacity of a Symmetric Discrete Memoryless Channel
(Symmetric DMC) can be solved very elegantly. However, for a
Quasi-Symmetric Discrete Memoryless Channel (Quasi-Symmetric DMC), must
we resort exclusively to the Lagrange multiplier method for solving the
nonlinear optimization problem?
In fact, by cleverly applying the algebraic properties of matrix
partitioning, this nonlinear optimization problem can be transformed
into an extremal problem involving probability grouping and conditional
entropy. This is a lemma from the textbook, but unfortunately the
textbook does not provide a proof.
Prerequisites
First, it is unfortunate that the definition of quasi-symmetric DMC
in the information theory textbook used at SJTU Information Security is
not rigorous. In fact, the probability transition matrix of a
quasi-symmetric DMC as defined in the textbook is not necessarily
decomposable. For example, the following matrix conforms to the
textbook’s definition of a quasi-symmetric DMC, yet it cannot be
decomposed:
In the rigorous information theory definition, the decomposability of
the probability transition matrix is written into the definition of a
quasi-symmetric DMC. Therefore, there is no need to dwell on whether the
matrix can be decomposed – this is a prerequisite and not a lemma that
concerns us.
Let the channel input be , the output be , and the transition probability matrix be
.
Assume that the columns of the probability transition matrix can be
partitioned into mutually
disjoint submatrices . In the -th submatrix
(of dimension ), the sum of elements in
each row is a constant, denoted by ; the sum of elements in each column
is a constant, denoted by .
Based on the conservation of the total sum of matrix elements,
summing all elements of any submatrix yields an identity:
Conditional Entropy
The mutual information is computed as . Since each row of
the matrix contains exactly the same probability elements, merely in a
different order, the conditional entropy for any given input is a constant independent of the
input distribution: This is a conclusion from the textbook. Since is fixed, to maximize the channel
capacity , our sole
objective is to maximize the output entropy .
Theoretical Upper Bound
Introduce a random variable indicating that the channel output falls into the -th submatrix . Regardless of how the input
distribution varies, the
probability that the output
falls into the -th submatrix is
constant:
Since in the submatrix the
row sum is constant , i.e.,
,
substituting into the above expression yields:
Since the probability distribution of is completely fixed (i.e., ), we can expand using the chain rule:
To maximize , the
conditional entropy must
be maximized. Given that the output falls into the -th submatrix (with possible outputs), the entropy is
maximized when these outputs
are equally likely, yielding a maximum value of .
Therefore, the theoretical upper bound of is:
Substituting the identity derived earlier:
Since (the
probabilities in an entire row sum to 1), expanding gives:
Thus,
Conditions for Achieving
the Maximum
The theoretical upper bound has been obtained. According to the KKT
conditions, the input distribution that attains the theoretical maximum
channel capacity is not unique. We prove below that the uniform input
distribution is one such input distribution satisfying the KKT
conditions.
Consider the -th submatrix. We
have: which satisfies the condition for achieving the theoretical
upper bound discussed above.
Other Cases
For asymmetric DMCs, the solution is obtained via the KKT conditions
and the Blahut-Arimoto algorithm.
Rate-Distortion Function
This section proves two fundamental analytical properties of : convexity and monotonicity, which
form the theoretical basis for understanding the shape of the
rate-distortion function curve.
Convexity of the
Distortion Function
To prove that is a convex
function, we need to show that for any two admissible distortions and , and any real number , the following
inequality holds:
By the definition of , it is
the minimum mutual information subject to a distortion constraint.
Suppose that for distortion ,
there exists an optimal conditional probability distribution that exactly attains the
minimum of the rate-distortion function, i.e.:
and it satisfies the distortion constraint: . Similarly, for
distortion , there exists an
optimal conditional probability distribution such that:
and it satisfies the distortion constraint:
Using the parameter , we
mix these two distributions to construct a new conditional probability
distribution :
Since and are both valid probability
distributions and , their convex combination is clearly also a valid
probability distribution. Substituting into the formula for the
expected distortion:
Expanding this and using the previous constraint conditions:
This shows that: the mixed distribution lies exactly within
the feasible region for distortion .
The rate-distortion function seeks the minimum mutual
information among all distributions satisfying the constraint . Since is merely one
candidate distribution in this feasible region, the true minimum must be less than or equal to the
mutual information produced by :
However, the mutual information is convex in . Therefore, the
mutual information of the mixed distribution is always less than or
equal to the mixture of the mutual informations of the original
distributions:
Finally, substituting the results from the second step ( and ) into the above
expression and connecting these two inequalities:
Monotonicity of the
Distortion Function
For a given source and
distortion measure ,
the rate-distortion function
is defined as the minimum of the mutual information over all conditional
probability distributions (i.e., test channels) that satisfy an average
distortion not exceeding :
where is the set of all
conditional probability distributions satisfying the distortion
constraint (i.e., the feasible region):
Proof of Non-Increasing
Property
Suppose we have two given admissible distortion levels and , satisfying:
Consider the distortion-constrained sets and . If a conditional probability
distribution belongs
to , this means it
satisfies:
This implies that
also satisfies the distortion constraint for , and therefore also belongs to . In set-theoretic terms, this
means is a
subset of :
is defined as the
minimum of over the feasible region. Mathematically,
taking the minimum over a larger set always yields a result less
than or equal to the minimum over a smaller subset.
Therefore, we can directly conclude:
That is:
This completes the mathematical proof. Since whenever , we have , is a monotonically non-increasing
function of .
Strictly Decreasing
Property for
The proof of this property requires the convexity of . Suppose there exist two distortion
values and satisfying ; we
need to prove .
Since , there must exist a constant such that:
By the convexity of ,
substituting the above convex combination into yields:
Source Coding
This section provides a complete proof of the Kraft inequality
(necessary and sufficient condition for the existence of instantaneous
codes) and the derivation of the upper and lower bounds of Shannon’s
first theorem (lossless source coding theorem).
Kraft Inequality
For any -ary prefix
code with codewords, let
the set of codeword lengths be . Then it must satisfy: Conversely, if a set of positive integers satisfies this
inequality, then there necessarily exists a -ary prefix code with these codeword
lengths.
Necessity
Assume a -ary prefix code
exists with codeword lengths . Consider an infinite-depth full -ary tree, where the root node is at
level and each node has branches. The -th level of the tree has nodes in total.
Map each codeword of the prefix code to a node on the tree. A
codeword of length corresponds
to a specific node at level of
the tree. Since the code is a prefix code, no node corresponding
to any codeword is an ancestor of a node corresponding to another
codeword.
Let the maximum codeword length be .
Consider the -th level of
the tree, which has
nodes.
For any codeword node at level , the subtree rooted at that node
extends to leaf
nodes at level . Since no
codeword is a prefix of another, the subtrees generated by these codewords at level are mutually
disjoint.
This means that the total number of leaf nodes “covered” by these
codewords at level cannot exceed the total number of
nodes at that level. Therefore we have:
Dividing both sides of the inequality by , we obtain:
Sufficiency
Given a set of positive integers (sorted in non-decreasing order without
loss of generality) satisfying .
This is a constructive proof. We aim to show that on a full -ary tree, we can always sequentially
find nodes satisfying the prefix condition for these codewords.
Step 1: For the first codeword of length , we choose any node at level . Since level has nodes, clearly , so this step is always
feasible.
Step : Assume we have
successfully assigned the first
codewords (). We now
need to assign a node for the -th
codeword (of length ).
To ensure the prefix condition is satisfied, the -th codeword must not lie within any
subtree generated by the first
codewords. Since , the total number of nodes “consumed” at level by the first assigned codewords is:
By the given condition, all codeword lengths satisfy the Kraft
inequality, and all terms are positive. Therefore, the partial sum of
the first terms is strictly
less than 1 (since and the
final term ):
Multiplying both sides of the above inequality by yields:
That is, .
The left-hand side is the number of nodes covered by the first codewords (an integer), and the
right-hand side is the total number of nodes at level . Since the number of covered nodes is
strictly less than the total number of nodes, this proves that at level
there exists at least
one node not yet covered by any previous codeword.
We can safely choose this free node as the -th codeword without violating the
prefix rule. By mathematical induction, this process can proceed all the
way to the -th codeword.
Sufficiency is thus proved.
Proof of Shannon’s First
Theorem
Proof of the Lower Bound
Compute the difference between the information entropy and the
average code length:
Proof of the Upper Bound
To prove the upper bound, we only need to construct a prefix code
whose average code length is less than .
For each symbol of the
source with probability , we can
always find a unique integer code length that falls precisely within the
following interval:
It can be shown that since this length assignment satisfies the Kraft
inequality, it can be realized by a prefix code:
Therefore,
Channel Coding
This section proves Fano’s inequality, which relates the channel
equivocation to the decoding error probability, serving as a key tool in
the analysis of the channel coding theorem.