Entropy and Limit theorem in Probability Theory ^{∗}

Shigeki Aida

1 Introduction

What is entropy? Entropy represents the uncertainty of probabilistic phenomena. The following definition is due to Shannon.

Definition 1.1 (Shannon) Let us consider a finite set E = {A_{1}, …, A_{N}}. A nonnegative function P on E is called a probability distribution if ∑_{i=1}^{N} P ({A_{i}}) = 1. Each A_{i} is called a fundamental event. Subset of E is called event. Then, for this probability distribution P, we define the entropy by

H(P) = − ∑_{i=1}^{N} P ({A_{i}}) log P ({A_{i}}).  (1.1)

Remark 1.2 We use the convention, 0 log 0 = 0. If we do not mention about the base of the logarithmic function, we mean by log the natural logarithm, log_{e}. We define for a nonnegative sequence {p_{i}}_{i=1}^{N},

H(p_{1}, …, p_{N}) = − ∑_{i=1}^{N} p_{i} log p_{i}.  (1.2)

Example 1.3 (1) Coin tossing:

E = {H, T } and P_{1}({H}) = P_{1}({T }) = 1/2. We have H(P_{1}) = log 2.

(2) Dice: E = {1, 2, 3, 4, 5, 6}. P_{2}({i}) = 1/6 (1 ≤ i ≤ 6). Then we have H(P_{2}) = log 6.

(3) Unfair Dice: E = {1, 2, 3, 4, 5, 6}. P_{3}({1}) = 9/10, P_{3}({i}) = 1/50 (2 ≤ i ≤ 6).

H(P_{3}) = log [(\frac{10}{9})^{9/10} (50)^{1/10}] ≤ log (\frac{10}{9} · \frac{3}{2}) < log 2 = H(P_{1})  (1.3)

In the above examples (1) and (2), the entropies are nothing but log(# all fundamental events), because all fundamental events have equal probabilities. The notion of entropy appeared in statistical mechanics also. Of course, the discovery is before that in the information theory. The following is a basic property of the entropy.

Theorem 1.4 Suppose that |E| = N. Then for any probability distribution P, we have

0 ≤ H(P) ≤ log N.  (1.4)

Then the minimum value is attained by probability measures such that P ({A_{i}}) = 1 for some i. The maximum is attained by the uniform distribution P, namely, P (A_{i}) = 1/N for all 1 ≤ i ≤ N.

∗This is one of lectures of “Introduction to Engineering Science” in Graduate School of Engineering Science in Osaka University on June 30, 2003.

We refer the proof to the proof of Theorem 3.1 in the next section.

The notion of entropy is used to solve the following problem:

Problem Here are eight gold coins and a balance. One of coins is an imitation and it is slightly lighter than the others. How many times do you need to use the balance to find the imitation?

Solution: In information theory, the entropy stands for the quantity of the information. In the above problem, we have eight equal possibilities such that each coin may be imitation. So the entropy is log 8. We get some information by using the balance. By using the balance one time, we can get the following three informations: 1.The same weight, 2.The left one is lighter, 3.The right one is lighter. So it contains information log 3. Thus, by using k-times of the balance, we get information which is amount of k log 3. So if k log 3 < log 8, we do not get full information. So we need k ≥ 2 . Also it is not difficult to see that two times is enough. If the number of coins N satisfies 3^{n−1} < N ≤ 3^{n}, then n-times is enough. We refer the detail and other various examples to [11].

In order to get into the detail, we recall basic notions in probability theory.

2 Basic notions in probability theory

Mathematically, probability space is defined to be a measure space whose total measure equals

1. We refer the audiences to some text books (e.g. [10], [9], [7]) for the precise definition. We loosely define probability spaces.

Definition 2.1 (1) Let Ω be a set and F be a set of some subsets of Ω. A nonnegative function P : F → [0, 1] is called a probability measure on Ω if P (Ω) = 1 holds. A ∈ F is called an event and P (A) is called the probability of A. The triplet (Ω, F, P) is called a probability space.

(2) A function X on Ω is called a random variable if for any I = [a, b], X^{−1}(I) := {ω ∈ Ω | X(ω) ∈ I} ∈ F holds. For random variable X, define

μ_{X}(I) = P (X^{−1}(I)) ,  (2.1)

where I denotes an interval on ℝ. μ_{X} is also a probability on ℝ and it is called the law of X or the distribution of X.

Below, we consider the following kind of random variables only.

(1) The case where X is a discrete-type random variable:

Namely, X takes finite number values {a_{1}, …, a_{n}}. Then p_{i} := P ({ω ∈ Ω | X(ω) = a_{i}})(=: P (X = a_{i})) satisfies that ∑_{i=1}^{n} p_{i} = 1. The probability distribution μ_{X} of X is given by μ_{X}({a_{i}}) = p_{i} (1 ≤ i ≤ n).

(2) The case where X has a density function:

That is, there exists a nonnegative function f(x) on ℝ such that

P ({ω ∈ Ω | X(ω) ∈ [a, b]}) = ∫_{a}^{b} f(x)dx

for any interval [a, b].

Definition 2.2 For a random variable X, we denote the expectation, the variance by m and σ^{2} respectively. Namely,

(i) The case where X is a discrete-type random variable and takes values a_{1}, …, a_{n}:

m = E[X] = ∑_{i=1}^{n} a_{i}P (X = a_{i}),  (2.2)

σ^{2} = E[(X − m)^{2}] = ∑_{i=1}^{n}(a_{i} − m)^{2}P (X = a_{i}).  (2.3)

(ii) The case where X is a continuous-type random variable which has the density function f:

m = E[X] = ∫_{ℝ} xf(x)dx,  (2.4)
σ^{2} = E[(X − m)^{2}] = ∫_{ℝ}(x − m)^{2}f(x)dx.  (2.5)

Definition 2.3 (Independence of random variables) Let {X_{i}}_{i=1}^{N} be random variables on a probability space (Ω, F, P). N is a natural number or N = ∞. {X_{i}}_{i=1}^{N} are said to be independent if for any {X_{i_{k}}}_{k=1}^{m} ⊂ {X_{i}}_{i=1}^{N} (m ∈ ℕ) and −∞ < a_{k} < b_{k} < ∞, the following hold:

P (X_{i_{1}} ∈ [a_{1}, b_{1}], ⋯, X_{i_{m}} ∈ [a_{m}, b_{m}]) = ∏_{i=1}^{m} P (X_{i_{k}} ∈ [a_{k}, b_{k}]).  (2.6)

Definition 2.4 Let {X_{i}}_{i=1}^{∞} be independent random variables and the probability distribution of X_{i} is equal to μ for all i. Then {X_{i}} is said to be i.i.d. (=independent and identically distributed) random variables with the distribution μ.

3 Entropy and Law of large numbers (Shannon and McMillan’s theorem)

Suppose we are given a set of numbers A = {1, …, N} ⊂ ℕ. We call A the alphabet and the element is called a letter. A finite sequence {ω_{1}, ω_{2}, …, ω_{n}} (ω_{i} ∈ A) is called a sentence with the length n. The set of the sentences whose length are n is the product space A^{n} := {(ω_{1}, …, ω_{n}) | ω_{i} ∈ A}. Let P be a probability distribution on A. We denote P ({i}) = p_{i}. In this section, we define the entropy of P by using the logarithmic function to the base N:

H(P) = − ∑_{i=1}^{N} P ({i}) log_{N} P ({i}).  (3.1)

We can prove that

Theorem 3.1 For every P, 0 ≤ H(P) ≤ 1 holds. H(P) = 0 holds if and only if P ({i}) = 1 for some i ∈ A. H(P) = 1 holds if and only if P is the uniform distribution, that is, p_{i} = 1/N for all i.

Lemma 3.2 Let f(x) = x log x, or f(x) = − log x. Then for any {m_{i}}_{i=1}^{N} with m_{i} ≥ 0 and ∑_{i=1}^{N} m_{i} = 1 and nonnegative sequence {x_{i}}_{i=1}^{N}, we have

f (∑_{i=1}^{N} m_{i}x_{i}) ≤ ∑_{i=1}^{N} m_{i}f(x_{i}).  (3.2)

Furthermore, when m_{i} > 0 for all i, the equality of (3.2) holds if and only if x_{1} = ⋯ = x_{N}.

Proof of Theorem 3.1: First, we consider the lower bound. Applying (3.2) to the case where m_{i} = x_{i} = p_{i} and f(x) = − log x, we have

H(p_{1}, …, p_{N}) ≥ − log (∑_{i=1}^{N} p_{i}^{2})
≥ − log 1 = 0.  (3.3)

Clearly, in (3.3), the equality holds if and only if p_{i} = 1 for some i. Next, we consider the upper bound. By applying Lemma 3.2 to the case where m_{i} = 1/N, x_{i} = p_{i} and f(x) = x log x, for any nonnegative probability distribution {p_{i}}, we have

f (\frac{1}{N} ∑_{i=1}^{N} p_{i}) ≤ \frac{1}{N} ∑_{i=1}^{N} f(p_{i}).  (3.4)

Since ∑_{i=1}^{N} p_{i} = 1, this implies

−\frac{1}{N} log N ≤ \frac{1}{N} ∑_{i=1}^{N} p_{i} log p_{i}.

Thus, − ∑_{i=1}^{N} p_{i} log p_{i} ≤ log N and − ∑_{i=1}^{N} p_{i} log_{N} p_{i} ≤ 1. By the last assertion of Lemma 3.2, the equality holds iff p_{i} = 1/N for all i. □

Now we consider the following situation. Here is a (memoryless) information source S which sends out the letter according to the probability distribution P at each time independently. Namely, mathematically, we consider i.i.d. {X_{i}}_{i=1}^{∞} with the distribution P. We consider coding problem of the sequence of letters.

Basic observation: (1) Suppose that P ({1}) = 1 and P ({i}) = 0 (2 ≤ i ≤ N). Then the random sequence X_{i} is, actually, a deterministic sequence {1, 1, …, 1, …}. Thus, the variety of sequence is nothing. In this case, we do not need to send the all sequences. In fact, if we know that the entropy of P is 0, then immediately after getting the first letter, we know that subsequent all letters are 1. Namely, we can encode all sentences, whatever the lengths are, to just one letter.

(2) Suppose that N ≥ 2 and consider a probability measure such that P ({1}) = P ({2}) = 1/2 and P ({i}) = 0 for 3 ≤ i ≤ N. Then note that the sequences contain i(≥ 3) are not sent out. Thus the number of possible sequences under P whose lengths are n are 2^{n}. Note that the number of all sequences of alphabet A whose lengths are k is N^{k}. Thus, if N^{k} ≥ 2^{n}(⟺ \frac{k}{n} ≥ log_{N} 2 = H(P)), then all possible sentences whose lengths are n can be encoded into the sentences whose lengths are k(≤ n). Also the decode is also possible. More precisely, we can prove the following claim.

Claim If \frac{k}{n} ≥ H(P), then there exists an encoder φ : A^{n} → A^{k} and a decoder ψ : A^{k} → A^{n} such that

P (ψ(φ(X_{1}, …, X_{n})) ≠ (X_{1}, …, X_{n})) = 0.  (3.5)

The probability P (ψ(φ(X_{1}, …, X_{n})) ≠ (X_{1}, …, X_{n})) is called the error probability. For general P, we can prove the following theorem [3].

Theorem 3.3 (Shannon and McMillan) Take a positive number R > H(P). For any ε > 0, there exists M ∈ ℕ such that for all n ≥ M and k satisfying that \frac{k}{n} ≥ R, there exists φ : A^{n} → A^{k} and ψ : A^{k} → A^{n} such that

P (ψ(φ(X_{1}, …, X_{n})) ≠ (X_{1}, …, X_{n})) < ε.  (3.6)

R is called the coding rate. We need the following estimates for the proof of the above theorem.

Lemma 3.4 Let {Z_{i}}_{i=1}^{∞} be i.i.d. Suppose that E[|Z_{i}|] < ∞ and E[|Z_{i}|^{2}] < ∞. Then

P (|\frac{Z_{1} + ⋯ Z_{n}}{n} − m| ≥ δ) ≤ \frac{σ^{2}}{nδ^{2}} ,  (3.7)

where m = E[Z_{i}], σ^{2} = E[(Z_{i} − m)^{2}].

This lemma immediately implies the following weak law of large numbers.

Theorem 3.5 Assume the same assumption on {Z_{i}} as in Lemma 3.4. Then

lim_{n→∞} P (|\frac{Z_{1} + ⋯ Z_{n}}{n} − m| ≥ δ) = 0.  (3.8)

Proof of Theorem 3.3: Take n ∈ ℕ. The probability distribution of the i.i.d. subsequence {X_{i}}_{i=1}^{n} is the probability distribution P_{n} defined on A^{n} such that for any {a_{i}}_{i=1}^{n},

P_{n} ({ω_{1} = a_{1}, …, ω_{n} = a_{n}}) = ∏_{i=1}^{n} P ({a_{i}}) .  (3.9)

Let us consider random variables on A^{n}, Z_{i}(ω) = − log_{N} P ({ω_{i}}) (1 ≤ i ≤ n). Then {Z_{i}}_{i=1}^{n} are i.i.d. and the expectation and the variance are finite. In fact, we have

m = E[Z_{i}] = − ∑_{i=1}^{n} P ({ω_{i}}) log_{n} P ({ω_{i}}) = H(P)

σ = E[(Z_{i} − E[Z_{i}])^{2}] = ∑_{i=1}^{n} (log_{N} p_{i})^{2} p_{i} − H(P)^{2}.  (3.10)

Take δ > 0 such that R > H(P) + δ. By Lemma 3.4,

P_{n} (\frac{1}{n} ∑_{i=1}^{n} (− log_{N} P (\{ω_{i}\})) ≥ H(P) + δ) ≤ \frac{σ}{nδ^{2}} .  (3.11)

Hence, for any ε > 0, there exists M ∈ ℕ such that

P_{n} (\frac{1}{n} ∑_{i=1}^{n} (− log_{N} P (\{ω_{i}\})) ≥ H(P) + δ) ≤ ε  for all n ≥ M.  (3.12)

Noting

\{(ω_{1}, …, ω_{n}) | \frac{1}{n} ∑_{i=1}^{n} (− log_{N} P (\{ω_{i}\})) < H(P) + δ\}

= {(ω_{1}, …, ω_{n}) | ∏_{i=1}^{n} P ({ω_{i}}) > N^{−n(H(P)+δ)}}

⊂ {(ω_{1}, …, ω_{n}) | ∏_{i=1}^{n} P ({ω_{i}}) ≥ N^{−nR}} =: S_{n},  (3.13)

by (3.12), we have, for n ≥ M,

P ((X_{1}, …, X_{n}) ∈ S_{n})

= P_{n} ({(ω_{1} …, ω_{n}) ∈ A^{n} | ∏_{i=1}^{n} P ({ω_{i}}) ≥ N^{−nR}})

≥ P_{n} ({(ω_{1}, …, ω_{n}) ∈ A^{n} | ∏_{i=1}^{n} P ({ω_{i}}) ≥ N^{−n(H(P)+δ)}}) ≥ 1 − ε  (3.14)

On the other hand, we have

1 = P_{n} ({(ω_{1}, …, ω_{n}) ∈ A^{n} | ∏_{i=1}^{n} P ({ω_{i}}) ≥ N^{−nR}})

+P_{n} ({(ω_{1}, …, ω_{n}) ∈ A^{n} | ∏_{i=1}^{n} P ({ω_{i}}) < N^{−nR}})

≥ |S_{n}|N^{−nR}.  (3.15)

Hence we have

|S_{n}| ≤ N^{nR}.  (3.16)

By this estimate, if k ≥ nR, then, there exists an injective map ϕ : S_{n} → A^{k} and a map ψ : A^{k} → S_{n} such that

ψ(ϕ(ω_{1}, …, ω_{n})) = (ω_{1}, …, ω_{n}) for any (ω_{1}, …, ω_{n}) ∈ S_{n}.

By taking a map φ : A^{n} → A^{k} which satisfies φ|_{S_{n}} = ϕ, we have

P (ψ(φ(X_{1}, …, X_{n})) ≠ (X_{1}, …, X_{n})) ≤ P ((X_{1}, …, X_{n}) ∉ S_{n}) ≤ ε.  (3.17)

This completes the proof. □

4 Entropy and central limit theorem

Let {X_{i}}_{i=1}^{∞} be i.i.d. such that m = E[X_{i}] = 0 and σ^{2} = E[X_{i}^{2}] = 1. Let

S_{n} = \frac{X_{1} + ⋯ X_{n}}{\sqrt{n}} .

Then we have

Theorem 4.1 (Central limit theorem=CLT) For any −∞ < a < b < ∞,

lim_{n→∞} P (S_{n} ∈ [a, b]) = ∫_{a}^{b} \frac{1}{\sqrt{2π}} e^{− \frac{x^{2}}{2}} dx.  (4.1)

The probability distribution whose density is G(x) = \frac{1}{\sqrt{2π}} e^{− \frac{x^{2}}{2}} dx is called a normal distribution (Gaussian distribution) with mean 0 and variance 1 and the notation N(0, 1) stands for the distribution. A standard proof of CLT is given by using the characteristic function of S_{n}, φ(t) = E[e^{\sqrt{−1}tS_{n}}] (t ∈ ℝ). Below, we assume

Assumption 4.2 The distribution of X_{i} has the density function f, namely,

P (X_{i} ∈ [a, b]) = ∫_{a}^{b} f(x)dx.

Then, we can prove that the distribution of S_{n} also has the density function f_{n}(x) by Lemma 4.3 (1). In this case, (4.1) is equivalent to

lim_{n→∞} ∫_{a}^{b} f_{n}(x)dx = ∫_{a}^{b} G(x)dx.  (4.2)

By using the entropy of S_{n}, we can prove a stronger result

lim_{n→∞} ∫_{ℝ} |f_{n}(x) − G(x)|dx = 0  (4.3)

under additional assumptions on f. For the distribution P which has the density f(x), and a random variable X whose distribution is P, we define the entropy H and Fisher’s information I by

H(P) = H(X) = − ∫_{ℝ} f(x) log f(x)dx,  (4.4)
I(P) = I(X) = ∫_{ℝ} \frac{f′(x)^{2}}{f(x)} dx.  (4.5)

We summarize basic results on H and I.

Lemma 4.3 (1) If random variables X and Y have the density functions f and g respectively

then a(X + Y) (a > 0) has the density function h(x) = \frac{1}{a} ∫_{ℝ} f (\frac{x}{a} − y) g(y)dy.

(2) (Gibbs’s lemma) Let f(x) be a density of a probability whose mean 0 and the variance is 1, that is,

∫_{ℝ} xf(x)dx = 0,  (4.6)
∫_{ℝ} x^{2}f(x) = 1.  (4.7)

Then we have,

H(f) ≤ H(G).  (4.8)

The equality holds if and only if f(x) = G(x) for all x.

(3) (Shannon-Stam’s inequality) Let X, Y be independent random variables whose density functions satisfy (4.6) and (4.7). Then for a, b ∈ ℝ with a^{2} + b^{2} = 1, we have

a^{2}H(X) + b^{2}H(Y) ≤ H(aX + bY).  (4.9)

The equality holds iff the laws of X and Y are N(0, 1).

(4) (Blachman-Stam’s inequality) Let X, Y be independent random variables whose density functions satisfy (4.6) and (4.7). Then for a, b ∈ ℝ with a^{2} + b^{2} = 1,

I(aX + bY) ≤ a^{2}I(X) + b^{2}I(Y).  (4.10)

(5) (Csiszár-Kullback-Pinsker) For a probability density function f satisfying (4.6) and (4.7), we have

(∫_{ℝ} |f(x) − G(x)|dx)^{2} ≤ 2 (H(G) − H(f))  (4.11)

By Lemma 4.3 (1), S_{n} has a density function f_{n}. Also note that H(S_{nm}) ≥ H(S_{n}) for any n, m ∈ ℕ. We can prove f_{n} converges to G.

Theorem 4.4 Assume that f is C^{1}-function and I(f) < ∞. Then for any n, f_{n} is a continuous function. Moreover we have

lim_{n→∞} f_{n}(x) = G(x)  for all x  (4.12)
lim_{n→∞} H(f_{n}) = H(G),  (4.13)
lim_{n→∞} ∫_{ℝ} |f_{n}(x) − G(x)|dx = 0.  (4.14)

Sketch of Proof: By Shannon-Stam’s inequality, we can prove that (4.13). This and Csiszár-Kullback-Pinsker inequality implies (4.14). On the other hand, Blachman-Stam inequality implies I(f_{n}) ≤ I(f). This and (4.14) implies (4.12). See [4] and references in it for the detail. □

5 Boltzmann’s H-theorem, Markov chain and entropy

We recall kinetic theory of rarefied gases. Let (v_{x}^{i}(t), v_{y}^{i}(t), v_{z}^{i}(t)) be the velocity of the ith molecule at time t (1 ≤ i ≤ N). N denotes the number of molecules. The velocities v^{i}(t) = (v_{x}^{1}(t), v_{y}^{i}(t), v_{z}^{i}(t)) obey Newton’s equation of motion, but N is very big and it is almost meaningless to know each behavior of v^{i}(t). Boltzmann considered the probability distribution of the velocity, say, f_{t}(v_{x}, v_{y}, v_{z})dv_{x}dv_{y}dv_{z} and derived the following his H-theorem:

Theorem 5.1 (Boltzmann) Let

H(t) = − ∫_{ℝ^{3}} f_{t}(v_{x}, v_{y}, v_{z}) log f_{t}(v_{x}, v_{y}, v_{z})dv_{x}dv_{y}dv_{z}.

Then \frac{d}{dt}H(t) ≥ 0.

Remark 5.2 (1) In statistical mechanics, the entropy is nothing but kH(t), where k is the Boltzmann’s constant (=1.38 × 10^{−23}J · K^{−1}). Therefore, the above theorem implies that the entropy increases.

(2) Some people raised questions about the H-theorem.

(i) Newton’s equation of motion for the particles x(t) = (x_{i}(t))_{i=1}^{N} moving in a potential U reads as follows:

m_{i}ẍ_{i}(t) = −\frac{∂U}{∂x_{i}}(x(t))  (5.1)
x_{i}(0) = x_{i,0},  (5.2)
ẋ_{i}(0) = v_{i},  (5.3)

where (x_{i,0}), (v_{i}) are initial positions and the initial velocities. m_{i} is the mass of x_{i}. The time reversed dynamics x(−t) is the solution of (5.1) with initial velocity −v_{i}. Clearly, it is impossible that both entropies of x(t) and x(−t) increase. This is a contradiction. (ii) The second question is based on Poincaré’s recurrence theorem:

• There exists a time t_{0} such that x(t_{0}) is close to x(0).

Then at that time t_{0}, the entropy also should be close to each other. Therefore, the monotone property of entropy does not hold.

The reason why the above paradox appeared is in the statistical treatment of rarefied gases. We refer the recent progress based on probabilistic models to [2].

Note: Poincaré’s recurrence theorem holds under some additional assumptions on U.

From now on, we consider stochastic dynamics which are called Markov chains and prove that the entropy of the dynamics increases when time goes on.

Example 5.3 There are datum on the weather in a certain city.

Today  Tomorrow

Fine day [figure: Fine day ⋯ Probability \frac{2}{3}; Rainy day ⋯ Probability \frac{1}{3}]

9 Rainy day [figure: Fine day ⋯ Probability \frac{1}{2}; Rainy day ⋯ Probability \frac{1}{2}]

Today(=0-th day)is fine, then how much is the probability that the n-th day is also fine? Solution:

Let p_{k} be the probability that the k-th day is fine and set q_{k} = 1 − p_{k}, that is the probability that k-th day is rainy day. Then (p_{k}, q_{k}) satisfies the following recurrence relation:

(p_{k}, q_{k}) = (p_{k−1}, q_{k−1}) ( \begin{matrix}\frac{2}{3} & \frac{1}{3} \\ \frac{1}{2} & \frac{1}{2} \end{matrix} ) .  (5.4)

So we obtain

(p_{k}, q_{k}) = (1, 0) ( \begin{matrix}\frac{2}{3} & \frac{1}{3} \\ \frac{1}{2} & \frac{1}{2} \end{matrix} )^{k} .

Definition 5.4 Let E = {S_{1}, …, S_{N}} be a finite set. E is called a state space. We consider a random motion of a particle on S. Let {p_{ij}}_{i,j∈E} be nonnegative numbers satisfying that

∑_{j=1}^{N} p_{ij} = 1  for all 1 ≤ i ≤ N.  (5.5)

p_{ij} denotes the probability that the particle moves from S_{i} to S_{j}. If the probability that the particle locates at S_{i} is π_{i} (1 ≤ i ≤ N) at the time n, then the probability that the particle locates at S_{j} at the time n + 1 is ∑_{i=1}^{N} π_{i}p_{ij}. That is, if the initial distribution of the particle is π(0) = (π_{1}, …, π_{N}), then the distribution π(n) = (π_{1}(n), …, π_{N}(n)) at time n is given by

π(n) = π(0)P^{n},  (5.6)

where P denotes the N × N matrix whose (i, j)-element is p_{ij}. Below, we denote by p_{ij}^{(n)} the (i, j)-element of P^{n}.

We prove the following.

Theorem 5.5 Assume that

(A1) ∑_{i=1}^{N} p_{ij} = 1 for all 1 ≤ j ≤ N.

(A2) (Mixing property of the Markov chain) There exists n_{0} ∈ ℕ such that p_{ij}^{(n_{0})} > 0 for any i, j ∈ {1, …, N},.

Then for any initial distribution π = (π_{1}, …, π_{N}), we have

lim_{n→∞} π(n)_{i} = \frac{1}{N} .  for all 1 ≤ i ≤ N.  (5.7)

Note that (π(n)_{i})_{i=1}^{N} = π(n) = πP^{n}.

Remark 5.6 (A1) is equivalent to

(1, …, 1) = (1, …, 1)P.

Also (A1) holds if p_{ij} = p_{ji} for all i, j ∈ E.

This theorem can be proved by using the entropy of π(n) and Lemma 3.2. Recall

H(π) = − ∑_{i=1}^{N} π_{i} log π_{i}.

Lemma 5.7 Let Q = (q_{ij}) be a (N, N)-probability matrix, that is, q_{ij} ≥ 0 for all i, j and ∑_{j=1}^{N} q_{ij} = 1 for all i. Assume ∑_{i=1}^{N} q_{ij} = 1 for any j. Then for any π, H(πQ) ≥ H(π). In addition, if q_{ij} > 0 for all i, j, then, H(πQ) > H(π) for all π ≠ (1/N, …, 1/N).

Proof.

H(πQ) = − ∑_{i=1}^{N}(πQ)_{i} log (πQ)_{i}

= − ∑_{i=1}^{N} (∑_{k=1}^{N} π_{k}q_{ki}) log (∑_{k=1}^{N} π_{k}q_{ki}) .  (5.8)

Since ∑_{k=1}^{N} q_{ki} = 1, by applying Lemma 3.2 to the case where m_{k} = q_{ki}, x_{k} = π_{k},

(∑_{k=1}^{N} π_{k}q_{ki}) log (∑_{k=1}^{N} π_{k}q_{ki}) ≤ ∑_{k=1}^{N} q_{ki}π_{k} log π_{k}.  (5.9)

(5.8), (5.9) and ∑_{i=1}^{N} q_{ki} = 1 imply H(πQ) ≥ H(π). The last assertion follows from the last assertion of Lemma 3.2. □

By using this lemma, we prove Theorem 5.5.

Proof of Theorem 5.5 Since π(n) moves in a bounded subset in ℝ^{N}, there exist the accumulation points. That is, there exist x = (x_{1}, …, x_{N}) and a subsequence {π(n(k))}_{k=1}^{∞} such that lim_{k→∞} π(n(k)) = x. x is also a probability and satisfies that H(x) = lim_{k→∞} H(π(n(k))). Note that P^{n_{0}} is a probability matrix and all elements of P^{n_{0}} are positive. So if x ≠ (1/N, …, 1/N), then H(xP^{n_{0}}) > H(x). But xP^{n_{0}} = lim_{k→∞} πP^{n(k)+n_{0}} and H(xP^{n_{0}}) = lim_{k→∞} H(πP^{n(k)+n_{0}}). Since H(π(n)) is an increasing sequence, H(xP^{n_{0}}) = H(x). This is a contradiction. So x = (1/N, …, 1/N) which completes the proof. □

Addendum:

We consider the relative Fisher’s information and relative entropy for the probability density function f and g:

I(f|g) := ∫_{ℝ} [\frac{d}{dx} (\sqrt{\frac{f(x)}{g(x)}})]^{2} g(x)dx  (5.10)
H(f|g) := ∫_{ℝ} f(x) log (\frac{f(x)}{g(x)}) dx.  (5.11)

Then in the case where g = G (normal distribution), it holds that

H(f|G) ≤ 2I(f|G) for any f.  (5.12)

This inequality is called a logarithmic Sobolev inequality and it is used to prove semiboundedness of Hamiltonian which appeared in quantum field theory. My recent work is related to semiclassical problem of such kind of Hamiltonians and I used logarithmic Sobolev inequality to determine the asymptotic behavior of the ground state energy (=the lowest eigenvalue of the Hamiltonian) under the semiclassical limit ℏ → 0. You can find my research papers in my URL:

http://www.sigmath.es.osaka-u.ac.jp / aida/index-j.html

References

[1] E. Carlen, Super additivity of Fisher’s Information and logarithmic Sobolev inequalities, Journal of Functional Analysis, 101 (1991), 194–211.

[2] 内山耕平, 舟木直久著, ミクロからマクロへ, 2. 格子気体の流体力学極限, シュプリンガーフェアラーク東京, 2002 年

[3] A.I. Khinchin, Mathematical foundations of information theory, Dover books on advanced mathematics, 1957.

[4] P.L. Lions and G. Toscani, A strengthened central limit theorem for smooth densities, Journal of Functional Analysis, 129 (1995), 148–167.

[5] C.E. Shannon, The mathematical theory of communication, Bell Syst, Techn. Journ. 27, 379–423, 623–656 (1948).

[6] A.J. Stam, Some inequalities satisfied by the quantities of information of Fisher and Shannon, Information and Control 2 (1959), 101–112.

[7] D. Williams, Probability with martingales, Cambridge Mathematical Textbooks, 1991.

[8] K. Yoshida, Markoff process with a stable distribution, Proc. Imp. Acad. Tokyo, 16 (1940), 43–48.

[9] 熊谷隆, 確率論, 共立出版株式会社.

[10] 西尾真喜子, 確率論, 実教出版.

[11] ヤグロム, 情報理論入門, みすず書房.(邦訳)