Subadditivity of entropy for stochastic matrices

Wojciech Słomczyński^{1}

PREPRINT 2001/16

Abstract

The entropy of irreducible stochastic matrix measures its mixing properties. We show that this quantity is subadditive and strongly subadditive.

1Instytut Matematyki Uniwersytet Jagielloński Reymonta 4, 30-059 Kraków, Poland mail: slomczyn@im.uj.edu.pl 1 Preliminaries

Let N ∈ ℕ. We denote the simplex of probability vectors (finite probability distributions) by

Δ_{N} = {p ∈ ℝ^{N} : p_{i} ≥ 0 for i = 1, …, N and ∑_{i=1}^{N}p_{i} = 1}

and its interior by

Δ_{N}^{∘} = {p ∈ ℝ^{N} : p_{i} > 0 for i = 1, …, N and ∑_{i=1}^{N}p_{i} = 1} .

The extreme points of the simplex will be denoted by e^{k} = (0, ..., 1_{k}, ...0) (k = 1, ..., N).

We define the function η : ℝ^{+} → ℝ by the formula

η (x) = \{ \begin{matrix}−x ln x & for x ≠ 0 \\ 0 & for x = 0 \end{matrix} .

Then η is continuous and strictly concave. Moreover η|_{[0,1]} is nonnegative.

The Boltzmann-Shannon entropy h : Δ_{N} → ℝ^{+} is defined by the formula

h (p) = ∑_{i=1}^{N}η (p_{i})

for p ∈ Δ_{N}. The quantity h (p) can be interpreted as a measure of uncertainty of p and it changes from 0 for e^{k} (k = 1, ..., N) to ln N for the uniform vector (1/N, …, 1/N). It is easy to check that h is continuous and concave.

We call a nonnegative matrix P = (p_{ij})_{i,j=1,...,N} stochastic iff ∑_{j=1}^{N}p_{ij} = 1 for each i = 1, …, N. We say that a stochastic matrix P = (p_{ij})_{i,j=1,...,N} is irreducible iff for every i, j = 1, …, N there exists k ∈ ℕ such that (P^{k})_{ij} > 0. We denote the set of all irreducible stochastic matrices by I_{N}. It is well known (see e.g. [1]) that a stochastic matrix P is irreducible, iff it is ergodic, i.e., iff there exists a unique probability (row) vector p ∈ Δ_{N}^{∘} such that pP = p, where (pP)_{j} := ∑_{i=1}^{N} p_{i}p_{ij} for j = 1, …, N (i.e. p is the normalized left eigenvector of P corresponding to the eigenvalue 1). We call such a vector stationary.

2 Definitions

To measure the amount of chaos generated by an irreducible stochastic matrix P one may consider its entropy.

Definition 1 For P = (p_{ij})_{i,j=1,...,N} ∈ I_{N} we define the entropy of P by the formula

H (P) := − ∑_{i,j=1}^{N} p_{i}p_{ij} ln p_{ij} ,

where p ∈ Δ_{N}^{∘} is the stationary vector for P.

Note that this quantity is equal to the Kolmogorov-Sinai entropy of the Markov shift generated by P and p (see [2]), and varies from 0 for permutation matrices to ln N for the matrix all of whose elements are 1/N. To estimate the entropy increase we will also use another quantity - the weighted entropy of a stochastic matrix with respect to a probability vector.

Definition 2 Let P = (p_{ij})_{i,j=1,...,N} be a stochastic matrix, y ∈ Δ_{N}. We define the weighted entropy of P with respect to y by the formula

H_{y} (P) := ∑_{k=1}^{N}y_{k}h (e^{k}P ) .

If P ∈ I_{N} and p is its stationary vector, then H (P) = H_{p} (P).

3 Results

Our main result is the following

Theorem 1 (subadditivity of entropy) Let B and C be two irreducible stochastic matrices with common stationary vector p. Then

H (C) ≤ H (BC) ≤ H (B) + H (C) .  (1)

The elementary proof of the theorem is based on several auxiliary lemmas and propositions.

Lemma 1 Let λ_{i} ≥ 0, a_{i} > 0, and d_{i} ∈ ℝ for i = 1, ..., N. Then

(∑_{i=1}^{N} λ_{i}d_{i})^{2} ≤ (∑_{i=1}^{N} λ_{i}a_{i}) · (∑_{i=1}^{N} λ_{i} \frac{(d_{i})^{2}}{a_{i}} ) .  (2)

Proof. Put α_{i} = \sqrt{λ_{i}a_{i}} and β_{i} = d_{i}\sqrt{λ_{i}/a_{i}} for i = 1, ..., N. Then the inequality (2) follows from the Cauchy-Schwartz inequality

(∑_{i=1}^{N} α_{i}β_{i})^{2} ≤ (∑_{i=1}^{N} α_{i}^{2}) · (∑_{i=1}^{N} β_{i}^{2}).

Lemma 2 Let C = (c_{ij})_{i,j=1,...,N} ∈ I_{N}, y ∈ Δ_{N}^{∘}, x ∈ ℝ^{N}. Then

∑_{j=1}^{N} \begin{matrix}(xC) & {2 \atop j} \\ (yC) & j \end{matrix} ≤ ∑_{j=1}^{N} \frac{x_{j}^{2}}{y_{j}}  (3)

(note that (yC)_{j} ≠ 0 for j = 1, ..., N due to the irreducibility of matrix C).

Proof. Let j = 1, ..., N. Put λ_{i} = c_{ij}, a_{i} = y_{i}, and d_{i} = x_{i}. Applying Lemma 1 we get (xC)_{j}^{2} / (yC)_{j} ≤ ∑_{i=1}^{N} c_{ij}x_{i}^{2}/y_{i}. Summing these inequalities over j = 1, ..., N and using the identities ∑_{j=1}^{N} c_{ij} = 1 (i = 1, ..., N) we obtain the desired conclusion.

The above inequality has a simple geometrical meaning. Let us recall that the natural Fisher-Mahalonobis-Bhattacharyya metric on Δ_{N}^{∘} is given by the Riemannian form g_{ij}(p) = δ_{ij}p_{j}^{−1} for p ∈ Δ_{N}^{∘} and i, j = 1, ..., N (see e.g. [3], some authors call it also the Shahshahani metric [4]). The Riemannian geometry of Δ_{N}^{∘} is that of 1/2^{N} portion of the sphere of radius two in ℝ^{N}. Using the Riemannian form we can rewrite the inequality (3) as

∥xC∥_{yC} ≤ ∥x∥_{y}  (4)

for y ∈ Δ_{N}^{∘} and x ∈ T_{y}Δ_{N}^{∘} ∼ {x ∈ ℝ^{N} : ∑_{i=1}^{N}x_{i} = 0}. Consequently, we obtain

Proposition 1 If C ∈ I_{N}, then the map Δ_{N}^{∘} ∋ x → xC ∈ Δ_{N}^{∘} is a contraction on Δ_{N}^{∘} endowed with the Fisher-Mahalonobis-Bhattacharyya metric.

In fact, Chentsov [5] proved that this property characterizes the Fisher-Mahalonobis-Bhattacharyya metric among all Riemannian metrics on Δ_{N}^{∘} (see also [6] and [7]).

From Lemma 2 we deduce

Proposition 2 Let C = (c_{ij})_{i,j=1,...,N} be a stochastic matrix. Then the function F_{C} : Δ_{N} → ℝ given by F_{C} (y) = h (yC) − h (y) for y ∈ Δ_{N} is convex.

Proof. Observe first that the function (C, y) → F_{C} (y) is continuous in both variables. We first assume that C is irreducible. Let y ∈ Δ_{N}^{∘}. Then, it is easy to check that \frac{∂F_{C}}{∂y_{k}} (y) = ln y_{k} − ∑_{j=1}^{N}c_{kj} ln (yC)_{j} for k = 1, ..., N, and so

\frac{∂^{2}F_{C}}{∂y_{k}∂y_{m}} (y) = ∑_{j=1}^{N} \frac{(e^{k})_{j} (e^{m})_{j}}{y_{j}} − ∑_{j=1}^{N} \frac{(e^{k}C)_{j} (e^{m}C)_{j}}{(yC)_{j}}

for k, m = 1, ..., N. Hence the quadratic form related to the second order differential of F_{C} at y is given by

(D_{y}^{2}F_{C}) (x, x) = ∑_{j=1}^{N} \frac{x_{j}^{2}}{y_{j}} − ∑_{j=1}^{N} \begin{matrix}(xC) & {2 \atop j} \\ (yC) & j \end{matrix}  (5)

for x ∈ ℝ^{N}. Applying (3) and (5) we see that the Hessian matrix (\frac{∂^{2}F_{C}}{∂y_{k}∂y_{m}} (y))_{k,m=1,...,N} is nonnegative definite. Consequently, F_{C} is convex

on Δ_{N}^{∘}, and so on Δ_{N}. If C is not irreducible, then one can approximate it by irreducible matrices.

Our next claim is that the weighted entropy estimates the entropy increase from above (the result was announced without proof in [8]). Namely, we have

Proposition 3 Let (C_{ij})_{i,j=1,...,N} be a stochastic matrix, y ∈ Δ_{N}. Then

H_{y} (C) ≤ h (yC) ≤ H_{y} (C) + h (y) .  (6)

Proof. Let y ∈ Δ_{N}. Clearly, y = ∑_{k=1}^{N}y_{k}e^{k}. The first inequality follows from the fact that the function Δ_{N} ∋ y → h (yC) ∈ ℝ is concave. The second inequality follows from Proposition 2 and from the equalities h (e^{k}) = 0 for k = 1, …, N.

We are now in a position to show the main theorem.

Proof of the subadditivity of entropy. Let n = 1, …, N. Put (y_{n})_{k} = b_{nk} for k = 1, …, N. Then y_{n} ∈ Δ_{N}. Applying Proposition 3 we get

H_{y_{n}} (C) ≤ h (y_{n}C) ≤ H_{y_{n}} (C) + h (y_{n}) .

Hence

∑_{k=1}^{N}b_{nk}∑_{j=1}^{N}η (c_{jk}) ≤ ∑_{k=1}^{N}η (∑_{j=1}^{N}b_{nj}c_{jk})

and

∑_{k=1}^{N}η (∑_{j=1}^{N}b_{nj}c_{jk}) ≤ ∑_{k=1}^{N}b_{nk}∑_{j=1}^{N}η (c_{kj}) + ∑_{k=1}^{N}η (b_{nk}) .

Multiplying these inequalities by p_{n} and summing over n = 1, …, N we get the required result.

Analogously, one can show even stronger result.

Theorem 2 (strong subadditivity of entropy) Let A, B, and C be irreducible stochastic matrices with common stationary vector p. Then

H (ABC) + H (B) ≤ H (AB) + H (BC) .  (7)

Proof. From Proposition 2 it follows that the function F_{B,C} : Δ_{N} → ℝ given by F_{B,C} (y) = h (yBC) − h (yB) for y ∈ Δ_{N} is convex. Hence, as in the proof of Proposition 3, we get the inequality h (yBC) − h (yB) ≤ H_{y} (BC) − H_{y} (B) for y ∈ Δ_{N}. Then we proceed in the same manner as in the proof of Theorem 1.

Remark 1 Theorems 1 and 2 still hold if we drop the assumption of the irreducibility of matrices. However, in this case the entropy depends both on a matrix and on a stationary vector, which need not be unique.

Remark 2 We call a stochastic matrix P = (p_{ij})_{i,j=1,...,N} bistochastic (or doubly stochastic) iff ∑_{i=1}^{N}p_{ij} = 1 for each j = 1, …, N. If a bistochastic matrix is irreducible, then its only stationary vector is the uniform vector (1/N, …, 1/N). It is well known that the action of bistochastic P on probability vectors increases the uncertainty, i.e., h (p) ≤ h (pP) for p ∈ Δ_{N} - this fact is the first step in the proof of the famous H-theorem [9]. From this inequality, as in the proof of Theorem 1, we get the inequality H (B) ≤ H (BC) for irreducible bistochastic matrices B and C.

Acknowledgments. I am indebted to K. Życzkowski for suggesting the problem and for stimulating conversations, and to A. Urbański for helpful remarks. Financial support from Polski Komitet Badań Naukowych Grant no 2P 03B 07219 and British-Polish Joint Research Collaboration Programme Grant no WAR 341 204 is gratefully acknowledged.

References

[1] Berman, A. and Plemmons, R. J., Nonnegative Matrices in the Mathematical Sciences (Academic Press, New York, 1979).

[2] Walters, P., An Introduction to Ergodic Theory (Springer-Verlag, New York, 1982).

[3] Antonelli, P. L., The information dynamics of the diffusion processes of population genetics. Open Syst. Inf. Dyn. 4, 101-117 (1997).

[4] Akin, E., The Geometry of Population Genetics (Springer-Verlag, Berlin, 1979).

[5] Čencov, N. N., Statisticheskie reshayushchie pravila i optimal’nye vyvody (Nauka, Moscow, 1972) (in Russian), English transl.: Statistical decision rules and optimal inferences. Translation of Math. Monog. 53 (Amer. Math. Soc., Providence, R. I., 1982).

[6] Čencov, N. N., On basic concepts of mathematical statistics, in: Mathematical statistics. Banach Center Publ., vol. 6 (PWN, Warsaw, 1980), pp. 85-94.

[7] Campbell, L. L., An extended Čencov characterization of the information metric. Proc. Amer. Math. Soc. 98, 135-141 (1986).

[8] Życzkowski, K., Słomczyński, W., and Kuś, M., Random unistochastic matrices, to appear.

[9] Lasota, A. and Mackey M. C., Chaos, Fractals, and Noise. Stochastic Aspects of Dynamics (Springer-Verlag, New York, 1994).