Exponential decay of entropy in the Random Transposition and Bernoulli-Laplace models

Fuqing Gao ^{∗}  Jeremy Quastel ^{†}
Hubei University University of Toronto

Abstract

We give bounds on the exponential decay rate of entropy in the random transposition model and the Bernoulli-Laplace model which are independent of the number of sites and the number of particles. This is then used to give a bound on the time to stationarity in the total variation norm.

1 Introduction

This article concerns the decay of entropy and time to stationarity in two models of continuous time interacting random walks: The random transposition model and the Bernoulli-Laplace model.

Random transposition model. The state space S_{n} is the permutation group of n objects. The random transposition model is the Markov process uniquely characterized by an initial distribution on S_{n} and the Markov generator L_{n} given by

(L_{n}f)(σ) = \frac{1}{n} ∑_{i,j=1}^{n}[f(σ^{ij}) − f(σ)]

where f is a function on S_{n} and (σ^{ij})_{i} = σ_{j}, (σ^{ij})_{j} = σ_{i} and (σ^{ij})_{k} = σ_{k} for k ≠ i or j. We can think of n distinct particles, numbered 1 through n, placed in n distinct sites numbered 1 through n. S_{n} is the set of configurations with σ_{i} the number of the particle in site i. At rate one, a particle chooses uniformly from the n sites and exchanges position with the particle at that site. The model is symmetric and irreducible and has the uniform distribution μ_{n}(σ) = \frac{1}{n!} as unique stationary distribution. The associated expectation will be denoted E_{n}.

∗Research supported by the National Natural Science Foundation of China (19971025)

†Research supported by the NSERC, Canada

Bernoulli-Laplace model. The Bernoulli-Laplace model has two parameters n and r, 1 ≤ r ≤ n, the number of distinct sites and the number of identical particles. A site can be occupied by at most one particle. So the state space, denoted by C_{n,r} is the space of all subsets of the n sites with r elements. For η ∈ C_{n,r}, denote by η_{i} the number of particles at the site i. The Bernoulli-Laplace model is the Markov process with the state space C_{n,r} and with the Markov generator L_{n,r} given by

(L_{n,r}f)(η) = \frac{1}{n} ∑_{i,j=1}^{n} η_{i}(1 − η_{j})[f(η^{ij}) − f(η)] = \frac{1}{n} ∑_{i<j}[f(η^{ij}) − f(η)]

where f is a function on C_{n,r} and (η^{ij})_{i} = η_{j}, (η^{ij})_{j} = η_{i} and (η^{ij})_{k} = η_{k} for k ≠ i, j. Each particle, at rate one, picks a site with uniform probability, and jumps there as long as it is unoccupied. The model is symmetric and irreducible and has the uniform distribution μ_{n,r}(η) = \binom{n}{r}^{−1} as unique stationary distribution. The associated expectations will be denoted E_{n,r}.

Let L be an ergodic Markov process on a finite state space S symmetric with respect to invariant measure μ. Let P_{t} = e^{tL} denote the associated semigroup. If ν is the initial distribution then P_{t}ν → μ. We are interested in the speed of convergence. There are several choices of norm. Suppose that ν << μ and f = \frac{dν}{dμ}. The V^{(p)} norm is defined

V^{(p)}(ν, μ) = E_{μ}[|f − 1|^{p}]^{1/p}

if f ∈ L^{p}(μ), and +∞ otherwise. \frac{1}{2}V^{(1)}, the total variation norm, is most common, but V^{(2)} is used as well. The relative entropy is defined by

H(ν, μ) = E_{μ} [f log f]

if f log f ∈ L^{1}(μ), and +∞ otherwise. If μ is the invariant measure we will use H(f) or H_{μ}(f) for H(fμ, μ).

The time to stationarity, τ^{(p)} is defined by

τ^{(p)} = inf{t > 0 : sup_{ν} V^{(p)}(P_{t}ν, μ) ≤ e^{−1}}.

Often the bound τ^{(1)} ≤ τ^{(2)} is used. The Dirichlet form is defined by

D(f, g) = −E_{μ}[fLg], D(f) ≡ D(f, f).

The logarithmic Sobolev constant α is defined by

α = sup\{H(f)/D(\sqrt{f}) : f ≥ 0; E_{μ}[f] = 1\}.

It is known [4] that c_{1}α ≤ τ^{(2)} ≤ c_{2}α where c_{1} = 0.5 and c_{2} = 1 + \frac{1}{4} log log \frac{1}{μ^{∗}} where μ^{∗} = min_{x∈S} μ(x).

On the other hand, if one is interested in convergence of H(P_{t}ν, μ) let f_{t} = dP_{t}ν/dμ and note that

\frac{d}{dt}H(f_{t}) = −D(f_{t}, log f_{t}).

The entropy contant β is defined by

β = sup{H(f)/D(f, log f) : f ≥ 0; E_{μ}[f] = 1}.

Therefore

H(P_{t}ν, μ) ≤ e^{−t/β}H(ν, μ).

The entropy constant was obtained for Poisson measure in [3]. From the general inequality,

(\sqrt{b} − \sqrt{a})^{2} ≤ \frac{1}{4}(b − a)(log b − log a),

valid for a, b ≥ 0, we have D(\sqrt{f}) ≤ \frac{1}{4}D(f, log f) and hence β ≤ 4α. Since H ≥ V^{(1)} it is easy to check that

τ^{(1)} ≤ β(1 + log log \frac{1}{μ^{∗}}).

The relative entropies and Dirichlet forms for the random transposition model and Bernoulli-Laplace models are given respectively by

H_{n}(f) = \frac{1}{n!} ∑_{σ∈S_{n}} f(σ) log f(σ),

D_{n}(f, g) = \frac{1}{n!2n} ∑_{σ∈S_{n}} ∑_{i,j=1}^{n}[f(σ^{ij}) − f(σ)][g(σ^{ij}) − g(σ)]

H_{n,r}(f) = \frac{1}{\binom{n}{r}} ∑_{η∈C_{n,r}} f(η) log f(η),

D_{n,r}(f, g) = \frac{1}{2n\binom{n}{r}} ∑_{η∈C_{n,r}} ∑_{1≤i<j≤n}[f(η^{ij}) − f(η)][g(η^{ij}) − g(η)].

Let α_{n} and β_{n} denote the logarithmic Sobolev constant and entropy constant of the random transposition model on S_{n}, and α_{n,r} and β_{n,r} denote the logarithmic Sobolev constant and entropy constant of the Bernoulli-Laplace model on C_{n,r}. In [4], [14] it is shown that there exists 0 < c < ∞ such that for any n ≥ 2,

c^{−1} log n ≤ α_{n} ≤ c log n,

and for any r = 1, …, n − 1,

c log \frac{n^{2}}{r(n − r)} ≤ α_{n,r} ≤ \frac{2}{log 2} log \frac{n^{2}}{r(n − r)}.

The upper bound on τ_{n}^{(2)} for the random transposition, and τ_{n,r}^{(2)} for the Bernoulli-Laplace models then read

τ_{n}^{(2)} ≤ C(log n)^{2}, τ_{n,r}^{(2)} ≤ C log \frac{n^{2}}{r(n − r)} log log \binom{n}{r}.

Our purpose in this paper is to bound the entropy constants for the two models of random walks. We obtain the bound which is independent of the numbers of sites and the numbers of particles. The method used is the martingale method of [15]. The main results of this article are

Theorem 1 (Random transposition model). For any n ≥ 2,

1/2 ≤ β_{n} ≤ 1.

In particular, for any probability measure ν_{n} on S_{n}, for n ≥ 2,

H(P_{t}ν_{n}, μ_{n}) ≤ e^{−t}H(ν_{n}, μ_{n}),

and for some C < ∞,

τ_{n}^{(1)} ≤ (1 + log log n!) ≃ log n.

Theorem 2 (Bernoulli-Laplace model). For any n ≥ 2 and any 1 ≤ r ≤ n − 1,

1 ≤ β_{n,r} ≤ 2.

In particular, for any probability measure ν_{n,r} on C_{n,r}, for n ≥ 2, and 1 ≤ r ≤ n − 1,

H(P_{t}ν_{n,r}, μ_{n,r}) ≤ e^{−t/2}H(ν_{n,r}, μ_{n,r}),

and for some C < ∞,

τ_{n,r}^{(1)} ≤ 2(1 + log log \binom{n}{r}).

The main conclusion is that the commonly used bound τ^{(1)} ≤ τ^{(2)} gives the wrong order for the time to stationarity in the total variation sense in the random transposition model and in the Bernoulli-Laplace model at high or low densities.

The upper bounds on β_{n} and β_{n,k} are proved in sections 2 and 3 respectively. The lower bounds are obtained from the general inequality [2],

β ≥ λ/2

where λ is the Poincaré constant (= 1/spectral gap),

λ = sup\{V ar(f)/D(\sqrt{f})\},

where V ar(f) = E[(f −E[f])^{2}]. The spectral gap can be computed for both models [7],[8],[16]. In the random transposition model λ_{n} = 1 and for the Bernoulli-Laplace model λ_{n,r} = 2.

2 Random transposition model

To prove the upper bound for β_{n}, using martingale methods as in [14] we will derive an inequlity involving β_{n+1} and β_{n}. First of all we give an entropy inequality as follows.

Lemma 1. Let μ be the uniform distribution on {1, 2, …, n} and f a probability density function relative to μ. Then for all n ≥ 2,

H_{μ}(f) ≤ \frac{1}{2n^{2}} ∑_{x,y=1}^{n}(f(y) − f(x))(log f(y) − log f(x)).

Proof. Set

f(x_{1}, ⋯, x_{n}) = ∑_{i,j=1}^{n}(x_{i} − x_{j})(log x_{i} − log x_{j}) − 2n ∑_{i=1}^{n} x_{i} log x_{i}

where x_{1} …, x_{n} ≥ 0. The lemma is equivalent to f(x_{1}, ⋯, x_{n}) ≥ 0 for any x_{1}, …, x_{n} ≥ 0 with x_{1}+⋯+x_{n} = n. Since under the condition x_{1}+⋯+x_{n} = n,

f(x_{1}, ⋯, x_{n}) = −2n ∑_{i=1}^{n} log x_{i},

we need only prove that \frac{1}{n} ∑_{i=1}^{n} log x_{i} ≤ 0 for any x_{1}, …, x_{n} ≥ 0 with x_{1} + ⋯ + x_{n} = n which is an obvious consequence of the concavity of the logarithm.

Proof of Theorem 1. Let f be a the probability density function relative to the uniform distribution μ_{n+1} on S_{n+1}. Let f_{i} be the marginal probability density function of σ_{i} and f(·|σ_{i}) be the conditional the probability density function given σ_{i}. Define

I_{1,i,j,k}(f) = E_{n+1}[f_{i}(σ_{i})E_{n+1}[(f(σ^{jk}|σ_{i}) − f(σ|σ_{i}))(log f(σ^{jk}|σ_{i}) − log f(σ|σ_{i}))|σ_{i}]]

I_{1,i} = ∑_{i,j≠k} I_{1,i,j,k} = E_{n+1}[ ∑_{j,k≠i}(f(σ^{jk}) − f(σ))(log f(σ^{jk}) − log f(σ))],

I_{2,i}(f) = E_{n+1}[f_{i}(σ_{i}) log f_{i}(σ_{i})],

I_{l}(f) = \frac{1}{n + 1} ∑_{i=1}^{n+1} I_{l,i}(f), l = 1, 2.

Then

H_{n+1}(f) = E_{n+1}[f_{i}(σ_{i})E_{n+1}[f(.|σ_{i}) log f(.|σ_{i})|σ_{i}]] + I_{2,i} .

Since the uniform distribution on S_{n+1}, given σ_{i}, is the uniform distribution on S_{n}, from the definition of β_{n} we have that

H_{n+1}(f) ≤ \frac{β_{n}}{2n}I_{1,i} + I_{2,i},

thus

H_{n+1}(f) ≤ \frac{β_{n}}{2n}I_{1} + I_{2}.  (2.1)

Note that

I_{1}(f) = 2(n − 1)D(f, log f).  (2.2)

Applying Lemma 1 to f_{i} we get

I_{2,i}(f) ≤ \frac{1}{2(n + 1)^{2}} ∑_{x,y=1}^{n+1}(f_{i}(y) − f_{i}(x))(log f_{i}(y) − log f_{i}(x)).  (2.3)

Since f_{i}(x) = E_{n+1}[f(σ)|σ_{i} = x)] and the function: (a, b) → (a − b)(log a − log b) is convex for a, b ≥ 0, Jensen’s inequality implies (with E[·] = E_{n+1}[·]),

(f_{i}(y) − f_{i}(x))(log f_{i}(y) − log f_{i}(x)) = (E[f(σ)|σ_{i} = y)] − E[f(σ)|σ_{i} = x)])(log E[f(σ)|σ_{i} = y)] − log E[f(σ)|σ_{i} = x)]) = (E[f(σ^{xy})|σ_{i} = x)] − E[f(σ)|σ_{i} = x)])(log E[f(σ^{xy})|σ_{i} = x)] − log E[f(σ)|σ_{i} = x)])

≤ (n + 1)E[(f(σ^{xy}) − f(σ))(log f(σ^{xy}) − log f(σ)))|σ_{i} = x].  (2.4)

Combining (2.3) and (2.4) we have

I_{2,i} ≤ \frac{1}{2(n + 1)}E_{n+1}( ∑_{x,y=1}^{n+1}(f(σ^{xy}) − f(σ))(log f(σ^{xy}) − log f(σ)))).

Therefore

I_{2} ≤ \frac{1}{(n + 1)}D(f, log f).  (2.5)

By the definition of the Entropy constant β_{n+1}, the inequalities (2.1), (2.2) and (2.5) now imply

β_{n+1} ≤ \frac{(n − 1)β_{n}}{n} + \frac{1}{(n + 1)}.  (2.6)

The desired upper bound is got from (2.6) by an induction on n ≥ 2. The initial check for n = 2 follows from the n = 2 case of Lemma 1 which gives β_{2} ≤ 1/2. Assuming that β_{n} ≤ 1, the last inequality yields

β_{n+1} ≤ \frac{n − 1}{n} + \frac{1}{(n + 1)} < 1.

3 Bernoulli-Laplace model

Lemma 2. Let μ_{ρ} be the Bernoulli measure on {0, 1}, 0 < ρ < 1. Then for any probability density function f on {0, 1}, relative to the Bernoulli measure,

H_{μ_{ρ}}(f) ≡(1 − ρ)f(0) log f(0) + ρf(1) log f(1)
≤ρ(1 − ρ)(f(0) − f(1))(log f(0) − log f(1)).

(3.1)

Proof. If (1 − ρ)x + ρy = 1, x ≥ 0, y ≥ 0, one can check easily that

f(x, y) =ρ(1 − ρ)(x − y)(log x − log y) − (1 − ρ)x log x − ρy log y
= − (1 − ρ) log x − ρ log y
≥0.

Proof of Theorem 2. We will prove theorem 2 by induction. Let f be a the probability density function relative to the uniform distribution μ_{n,r} on C_{n,r} and denote by f_{i} the marginal probability density function of σ_{i} and by f(·|η_{i}) the conditional the probability density function of η given η_{i}. Define

I_{1,i}(f) =E_{n+1,r}[f_{i}(η_{i})E_{n+1,r}[β_{n,r−η_{i}} ∑_{j,k≠i}(f(η^{jk}|η_{i}) − f(η|η_{i}))
× (log f(η^{jk}|η_{i}) − log f(η|η_{i}))|η_{i}]]
=E_{n+1,r}[ ∑_{j,k≠i} β_{n,r−η_{i}}(f(η^{jk}) − f(η))(log f(η^{jk}) − log f(η)))],
I_{2,i}(f) =E_{n+1,r}[f_{i}(η_{i}) log f_{i}(η_{i})],
I_{l}(f) =\frac{1}{n + 1} ∑_{i=1}^{n+1} I_{l,i}(f), l = 1, 2.

Simple calculation yields

H_{n+1}(f) = E_{n+1,r} [f_{i}(η_{i})E_{n+1,r}[f(·|η_{i}) log f(·|η_{i})|η_{i}]] + I_{2,i}.  (3.3)

Since if η_{i} = 0 or 1, then the inner expectation is with respect to μ_{n,r} or μ_{n,r−1}, respectively, from the definition of β_{n,r} and I_{1,i} we have that

H_{n+1,r}(f) ≤ \frac{1}{2n}I_{1,i} + I_{2,i},

and hence

H_{n+1,r}(f) ≤ \frac{1}{2n}I_{1} + I_{2}, 2 ≤ r ≤ n − 1.  (3.4)

We have,

I_{1,i}(f) =β_{n,r}E_{n+1,r}[ ∑_{j,k≠i}(f(η^{jk}) − f(η))(log f(η^{jk}) − log f(η)) | η_{i} = 0]

+ β_{n,r−1}E_{n+1,r}[ ∑_{j,k≠i}(f(η^{jk}) − f(η))(log f(η^{jk}) − log f(η)) | η_{i} = 1],

and so

I_{1} = \frac{1}{n + 1} ∑_{i=1}^{n+1} I_{1,i} = 2((n − r)β_{n,r} + (r − 1)β_{n,r−1})D_{n+1,r}(f, log f). (3.5)

Now applying Lemma 2 with ρ = \frac{r}{n+1} to f_{i} we get

I_{2,i}(f) ≤ \frac{r(n + 1 − r)}{(n + 1)^{2}}(f_{i}(0) − f_{i}(1))(log f_{i}(0) − log f_{i}(1)).  (3.6)

Now

f_{i}(0) = E_{n+1,r}[f(η)|η_{i} = 0] = \frac{1}{n − r + 1} ∑_{j≠i} E_{n+1,r} [(1 − η_{j})f(η^{ij})|η_{i} = 1] .

(a, b) → (a − b)(log a − log b) is convex for a, b ≥ 0 so by Jensen’s inequality, (f_{i}(0) − f_{i}(1))(log f_{i}(0) − log f_{i}(1))

≤ \frac{1}{n − r + 1} ∑_{j≠i} E_{n+1,r} [(1 − η_{j})(f(η^{ij}) − f(η))(log f(η^{ij}) − log f(η))|η_{i} = 1] .

Summing over i and writing out the conditional expectation we get

∑_{i=1}^{n+1}(f_{i}(0) − f_{i}(1))(log f_{i}(0) − log f_{i}(1))

≤\frac{n + 1}{r(n + 1 − r)} ∑_{i≠j} E_{n+1,r} [η_{i}(1 − η_{j})(f(η^{ij}) − f(η))(log f(η^{ij}) − log f(η))] . (3.7)

Combining (3.6) and (3.7) we have

I_{2} ≤ \frac{2}{n + 1}D_{n+1,r}(f, log f).  (3.8)

By the definition of the entropy constant and (3.4), (3.5) and (3.8)

β_{n+1} ≤ \frac{(n − r)}{n}β_{n,r} + \frac{(r − 1)}{n}β_{n,r−1} + \frac{2}{n + 1}.  (3.9)

Now we prove the upper bound by (3.8) and an induction on n ≥ 2. The initial case n = 2, r = 1 is a consequence of Lemma 2. Suppose β_{k,j} ≤ 2 for any 2 ≤ k ≤ n and 2 ≤ j ≤ k − 1. Then

case (i), for any 2 ≤ r ≤ n − 1,

\frac{1}{2}β_{n+1,r} ≤ \frac{n − r}{n} + \frac{r − 1}{n} + \frac{1}{n + 1} < 1;

case (ii), for r = 1 or r = n, by Lemma 1 we have β_{n+1,1} ≤ \frac{2}{n+1} < 2. Acknowledgment Fuqing Gao would like to thank Jeremy Quastel for his

very kind hospitality at University of Toronto where this work is done.

Jeremy Quastel, Departments of Mathematics and Statistics, University of Toronto, Toronto, ON M5S 3G3, Canada. quastel@math.toronto.edu

Fuqing Gao, Department of Mathematics, Hubei University, Wuhan 430062,

P.R. China. gaofq@hubu.edu.cn

References

[1] C. Ané and M.Ledoux, On logarithmic Sobolev inequalities for continuous random walks on graphs, Probab. Theory Rel. Fields 116 (2000) 573–602.

[2] D. Bakry, L’hypercontactivite et son utilisation en theorie des semi-groupes, Ecole d’eté de probabilités de Saint-Flour XXII, 1992, Lecture Notes in Math., 1581, 1-114. (1994).

[3] S. Bobkov and M. Ledoux, On modified logarithmic Sobilev inequalities for Bernoulli and Poisson measures, J. Funct. Anal., 156 (1998) 347-365.

[4] P. Diaconis and L. Saloff-Coste, Logarithmic Sobolev inequalities for finite Markov chains, Ann. Appl.Prob., 6 (1996) 695-750.

[5] P. Diaconis and L. Saloff-Coste, Random walks on finite groups, Probability measures on groups and related structures XI,44-75, (Oberwolfach, 1994, H.Heyer ed.), World Scientific, Singapore, 1995.

[6] P. Diaconis, L. Saloff-Coste, Comparison theorems for reversible Markov chains. Ann. Appl. Probab. 3 (1993), no. 3, 696–730.

[7] P. Diaconis, M. Shahshahani, Generating a random permutation with random transpositions, Z. Wahr. Verw. Geb., 57 (1981), 159-179.

[8] P. Diaconis, M. Shahshahani, Time to reach stationarity in the Bernoulli-Laplace diffusion model, SIAM Jour. Math. Anal., 18, (1987) 208–218.

[9] P. Dai Pra, A. Paganoni, G. Posta, Entropy inequality for unbounded spin systems, Preprint.

[10] J. Deuschel and D. W. Stroock, Large Deviations, Academic Press, San Diego, 1989.

[11] L. Gross, Logarithmic Sobolev inequalities,Amer. J. Math., 97(1976) 1061-1083.

[12] C. Kipnis, S. Olla, S.R.S. Varadhan, Hydrodynamics and large deviations for simple exclusion processes, Commun. Pure Appl. Math., 42 (1989), 115-137.

[13] M. Ledoux, Concentration of measure and logarithmic Sobolev inequalities, Séminaire de Probab. XXXIII, Lecture Notes in Math. 1709, 120–216, Springer, 1999.

[14] T. Y. Lee and H. T. Yau, Logarithmic Sobolev inequality for some models of random walks, Ann. Probab., 26 (1998) 1855-1873.

[15] S. Lu and H. T. Yau, Spectral gap and logarithmic Sobolev inequality for Kawasaki and Glauber dynamics. Comm. Math. Phys., 156 (1993), no. 2, 399–433.

[16] J. Quastel, Diffusion of color in the simple exclusion process, Commun. Pure Appl. Math., XLV (1992), 623-679.

[17] Liming Wu, A new modified logarithmic Sobolev inequality for Poisson point processes and several applications, Probab. Theory Relat. Fields, 118 (2000) 427–438.

[18] H.T. Yau, Logarithmic Sobolev inequality for generalized simple exclusion processes.Probab. Theory Related Fields 109 (1997), no. 4, 507–538.