NIS2337 Information Theory Notes (1): Source and Information Entropy

This section introduces the classification of sources and their mathematical models, and defines basic concepts such as self-information, mutual information, entropy, and relative entropy for both discrete and continuous sources.

Other parts of the NIS2337 Fundamentals of Information Theory course notes: 1. Source and Information Entropy (this article) 2. Channel and Channel Capacity 3. Rate-Distortion Function 4. Source Coding 5. Channel Coding

Supplementary information can be found in Beyond 2337.

Classification of Sources and Mathematical Models

A single-symbol source refers to a source that outputs one symbol at a time. Those with discrete amplitudes are called single-symbol discrete sources, while those with continuous amplitudes are called single-symbol continuous sources.

A single-symbol discrete source is typically described by the probability distribution of a random variable , whose sample space is the source’s symbol set .

where and .

A single-symbol continuous source is described by a probability density function , whose sample space is the set of real numbers:

where and .

Memoryless Symbol-Sequence Sources

A source emits a symbol sequence at each instance, where each is a single-symbol source. It is often described by the joint probability density function .

Memoryless. That is, for any , .

Stationary. The statistical properties of the sequence emitted by the source do not change with the shift of time. - Strictly stationary: The joint probability distribution of the source output at any dimension does not vary with time. That is, for any , . - Weakly stationary: The mean of the source output sequence is independent of the starting time; the covariance function depends only on the time interval and not on the starting time.

In a discrete memoryless source, if each symbol output by the source is statistically independent and shares the same probability space, then the source is called a discrete stationary memoryless source, also known as an independent and identically distributed (i.i.d.) source.

Memory Symbol-Sequence Sources

Dependencies exist among symbols within a symbol sequence, but the sequences themselves are mutually independent.

Markov Sources

Markov source. When the memory length of a source is , the symbol emitted at a given instant is correlated with at most preceding symbols and is independent of symbols further back. This is called an -th order Markov source.

Homogeneous Markov source. For a first-order Markov source, we have . If the above conditional transition probabilities are independent of the time origin, the source is called a homogeneous Markov source.

State. For an -th order Markov source, the state is defined as the combination of the symbols preceding the -th time instant, i.e., . The state space of an -th order Markov source is .

State Transition Probabilities

For a general Markov source, the state transition probability from state at time to state at time is defined as:

Typically, we are more concerned with the case , and thus define the one-step transition probability or basic transition probability as:

For a homogeneous Markov chain, the state transition probability depends only on the current state and is independent of time, i.e., . Clearly, satisfies non-negativity and normalization.

Similarly, the -step transition probability can be defined as:

More generally, for a homogeneous Markov source, the Chapman-Kolmogorov equation holds:

It should be clarified that stationarity means the probability distribution of the source output is independent of time; the probability distribution of the source output is identical regardless of the sampling time. In contrast, homogeneous means the transition probability distribution of the source is independent of time, but the probability distribution of the source output at different time instants may differ due to different preceding conditions. Therefore, homogeneity does not necessarily imply stationarity.

For a stationary Markov source, since its output probability distribution is independent of time, its transition probability distribution is also independent of time. Hence, a stationary Markov source is necessarily homogeneous.

For an -th order Markov source, the state transition matrix is an matrix, where the element in the -th row and -th column is the transition probability from state to state :

Clearly, the sum of the elements in the -th row equals 1, i.e., ; the sum of the elements in the -th column does not necessarily equal 1.

Furthermore, the -step transition probability matrix is the -th power of the state transition matrix, i.e., . Therefore, for a homogeneous Markov source, the -step transition probabilities depend only on the single-step state transition matrix.

Stationary Distribution

Introducing the initial probability , we have . If exists, it is called the stationary distribution. At this point, the source reaches a steady state, where the probability distribution of all states is and is independent of the initial state.

Solving for directly from the definition is typically difficult. The stationary distribution is generally obtained by solving a system of equations derived from the limiting condition of state transitions:

In fact, the existence of a non-trivial solution to the above equations does not guarantee the existence of a stationary distribution. A stationary distribution requires the following conditions:

• The system of equations above has a solution;
• Irreducible: For any states and , there exists a positive integer such that ;
• Aperiodic: For any state , among all positive integers such that , there is no common divisor greater than 1.

Discrete Source Entropy and Mutual Information

Self-Information

The self-information carried by a symbol with probability is defined as:

The unit of information depends on the base of the logarithm. Common units include bits (base 2) and nats (base , natural logarithm).

Self-information is additive. Let two symbols occur jointly with probability : - If and are independent, then . - If and are dependent, define the conditional self-information . Then .

Entropy

The entropy of a discrete source is defined as the average self-information of the source symbols:

• Entropy is non-negative.
• By convention, when , we set ; for a deterministic source, i.e., , the entropy is .

Conditional entropy. Let and be two discrete sources. Conditional entropy is defined as the average self-information of given knowledge of :

Joint entropy. Let and be two discrete sources. Joint entropy is defined as:

It is easy to see that .

Mutual Information

Mutual information. Let and be two discrete sources. The single-symbol mutual information is defined as:

Single-symbol mutual information can be positive or negative. The average mutual information is defined as:

Average mutual information can be viewed as a distance measure between the prior probability distribution and the posterior probability distribution . If the posterior distribution exactly matches the prior, the information gained through this “verification” is zero; if they are completely different, then all information about is obtained through this “verification”, i.e., .

The figure above illustrates the relationships among entropy, conditional entropy, and mutual information. Through the channel, the information we learn about is , but at the same time, the noise in the channel is also introduced. Only of the total information in is transmitted through the channel; the remaining is the information that cannot be transmitted due to channel limitations, and is called the equivocation.

We now introduce conditional mutual information, which is the mutual information between and given , defined as:

Thus, the average mutual information on a three-dimensional joint set can be defined as:

With the introduction of three-variable mutual information, the notation for mutual information becomes somewhat confusing. When symbols such as , , and are mixed, the priority of the conditioning symbol is set to the highest, the comma to the second highest, and the semicolon to the lowest. That is, denotes the mutual information between and given ; while denotes the mutual information between and given .

In the figure, denotes ; denotes ; denotes ; denotes ; denotes ; denotes ; denotes .

Changes in Information during Data Processing

Multi-stage Processing: Information Does Not Increase

Suppose the original information undergoes two stages of processing satisfying the Markov condition, ultimately yielding , i.e., . Then:

Since this processing forms a Markov chain, and are conditionally independent given , i.e., . Therefore:

That is, processing of information does not increase the amount of information.

On the conditional independence of and given :

Therefore, we can obtain some extended conclusions.

• If forms a Markov chain, then also forms a Markov chain, and also forms a Markov chain.

The information diagram of the Markov chain is shown above.

Multi-stage Observation: Information Does Not Decrease

Suppose the original information is observed times, yielding . Then:

Relative Entropy and Mutual Information

Relative entropy measures the dissimilarity between a random variable with true distribution and a random variable with assumed distribution . The relative entropy (also known as the Kullback-Leibler divergence) between two probability density functions and is defined as:

In the above definition, we adopt the conventions and .

Relative entropy is asymmetric; its computation essentially treats as the true distribution and uses it as the weight to compute a distance measure between and .

For joint probability density functions and , the conditional relative entropy is defined as:

The non-negativity of relative entropy, i.e., , with equality if and only if , can be proved using Jensen’s inequality.

By introducing relative entropy, we can reinterpret the definition of mutual information. For two discrete sources and , we can view their prior distribution as , i.e., assuming they are independent by default, and the learned posterior distribution as . Then the mutual information can be seen as the relative entropy from the default independent distribution to the learned dependent distribution, i.e.:

Properties of Entropy

Non-negativity, determinism, and symmetry are obvious.

Shannon’s auxiliary theorem. For any probability vectors and :

This verifies the non-negativity of relative entropy. It also shows that if we need to encode a source with probability distribution , the optimal coding scheme is based on the probability distribution , rather than on the probability distribution .

Maximum entropy principle. For any probability vector :

Expansibility. For any probability vector :

Although a source may have many possible values, if the probabilities corresponding to these values are very small (close to 0), the entropy of the source remains unchanged. That is, although low-probability events carry more information to the receiver, in terms of the mathematical expectation of information, the contribution of these events ultimately converges to 0 as the probability decreases.

Additivity (Incrementality). For any probability vector :

This property indicates that if one element in the original source is split into multiple elements, the entropy increases.

Chain Rules

Chain rule for entropy. For any random variables jointly distributed according to :

Chain rule for mutual information. For any random variables and jointly distributed according to :

Chain rule for relative entropy. For any random variables and jointly distributed according to :

Convexity of Relative Entropy, Entropy, and Mutual Information

Convexity of relative entropy. For any probability vectors and , and any :

This can be proved using the log-sum inequality, by setting , , , .

Concavity of entropy. is a concave function of the probability distribution .

This can be proved via the relative entropy between and the uniform distribution.

Convexity/concavity of mutual information. For any probability distributions and , is a concave function of ; for any probability distributions and , is a convex function of .

Fano’s Inequality

For any estimator satisfying :

where is the probability of estimation error and is the alphabet of .

Furthermore, the above inequality can be weakened to .

Corollary: For any two random variables and :

where is the error probability between and , i.e., .

If and are independent and identically distributed random variables:

If they are not independent and identically distributed, let the symbol distributions of and be and , respectively:

Entropy of Discrete Sequence Sources

Entropy of Discrete Memoryless Sources

Assume the random sequence output by the source is , where each single-symbol variable in the sequence . The sequence entropy of the source is defined as:

where denotes the -th possible value of the sequence , i.e., .

When the sequence satisfies the memoryless condition, . When the sequence is stationary, ; in this case, the average entropy per symbol is .

Entropy of Discrete Sources with Memory

For discrete sources with memory, the concept of conditional entropy must be introduced, and meaningful conclusions can only be drawn in some special cases.

If the source outputs a symbol sequence of length , its entropy is:

Concerning , there are some interesting conclusions. In the following derivations, denote a symbol sequence of length as .

• is monotonically non-increasing: ;
• is monotonically non-increasing: .

That is, for a sequence source with memory, the longer the message sequence length , the smaller the incremental entropy, and the smaller the average entropy per symbol. Therefore, the entropy rate is defined as:

For a finite-length sequence source with memory, the sequence entropy and the average entropy per symbol only account for the correlation among the symbols, while the correlation between symbol sequences is neglected. This is clearly inadequate for practical applications.

In reality, considering that the source continuously emits signals, the statistical dependencies among symbols extend infinitely far. Hence, the entropy rate is the true entropy of a source with memory.

However, solving the probability distribution in infinite dimensions is a rather difficult task. When the above source satisfies the -th order Markov property, we have:

That is, the entropy rate of an -th order Markov source equals its conditional entropy, which is very useful in engineering.

The average symbol entropy of a Markov source is:

Entropy of Continuous Sources

The entropy of a continuous source, i.e., the differential entropy, is defined as:

The physical meaning of the entropy of a continuous source is different from that of a discrete source. The uncertainty of a continuous source should be infinite; however, the definition of differential entropy takes into account that practical problems often involve the difference between the entropies of different continuous sources (mutual information). Therefore, the infinite term in the definition cancels out in the difference calculation.

Consequently, the entropy of a continuous source is relative – the physical meaning of information (such as non-negativity) only emerges when taking the difference between two entropies.

The definitions of joint differential entropy and conditional differential entropy are given below:

It can be shown that the relationship between joint differential entropy and conditional differential entropy is analogous to that in the discrete case:

Thus, the mutual information for continuous sources can be defined as:

Entropy of Waveform Sources

In practical systems, the input and output are often not continuous single-symbol sources, but rather waveforms that are continuous in amplitude, time, and frequency. Stationary random processes and can be used to describe the input and output.

For a stationary random process, through sampling (refer to the relevant content on the sampling theorem in Signals and Systems: Applications of Fourier Transform), it can be transformed into a stationary random sequence that is discrete in time or frequency but continuous in amplitude (i.e., a mapping from a discrete set to a continuous interval), describing the input and output.

Let the stationary random vectors and be the input and output random sequences, respectively. Their continuous entropy and continuous conditional entropy are defined as:

For random waveform sources, the definitions of entropy and conditional entropy can be introduced by taking the limit of the above definitions:

According to the sampling theorem, for a signal with bandwidth and duration , a -dimensional vector can be used for representation. This converts a continuous-time process with both limited bandwidth and limited duration into a finite-dimensional, time-discrete stationary random sequence, whose entropy and conditional entropy can be determined using the definitions from the preceding sections.

Maximum Entropy Theorems

A continuous source has different maximum entropies under different constraints. For example, without any constraints, the entropy is infinite. In practical applications, certain constraints are typically imposed, such as peak-power-limited source output (i.e., peak amplitude constraint) or average-power-limited source output (i.e., average power constraint).

Under the peak-power constraint, the maximum entropy theorem for peak-power-limited sources states: among continuous sources satisfying a peak-power constraint, the probability density function that achieves maximum entropy is the uniform distribution.

Under the average-power constraint, the maximum entropy theorem for average-power-limited sources states: among continuous sources satisfying an average-power constraint, the probability density function that achieves maximum entropy is the Gaussian distribution.

Source Redundancy

Let the entropy rate of a general stationary source be . Its redundancy is defined as:

where is the maximum possible entropy of the source.

That is, under ideal conditions (i.e., infinitely long messages), the channel only needs to transmit information at a rate of . However, because the probability distribution of the information cannot be fully known or is too complex, the actual transmission capacity needs to reach .

The subsequent chapters on Source Coding and Channel Coding are closely related to redundancy. Source coding aims to improve coding schemes to eliminate redundancy, while channel coding aims to improve coding schemes to exploit redundancy for resisting channel noise.