1Introduction SebastianMentemeier AnoteonKesten’sChoquet-Denylemma

(1)

ISSN:1083-589X in PROBABILITY

A note on Kesten’s Choquet-Deny lemma

^∗

Sebastian Mentemeier

^†

Abstract

Letd >1and(An)_n∈Nbe a sequence of independent identically distributed random d×dmatrices with nonnegative entries. This induces a Markov chainMn=AnMn−1

on the coneR^d≥\ {0}=S^≥×R>. We study harmonic functions of this Markov chain.

In particular, it is shown that all bounded harmonic functions inC_b(S^≥)⊗ C_b(R>) are constant. The idea of the proof is originally due to Kesten [Renewal theory for functionals of a Markov chain with general state space. Ann. Prob. 2 (1974), 355 – 386], but is considerably shortened here. A similar result for invertible matrices is given as well.

Keywords:Choquet-Deny Lemma; Markov Random Walks; Products of Random Matrices.

AMS MSC 2010:Primary 60K15; 60B15, Secondary 46A55.

Submitted to ECP on February 22, 2013, final version accepted on July 30, 2013.

1 Introduction

Letd >1. WriteR^d≥= [0,∞)^dfor the cone ofd-vectors with nonnegative entries and S≥ := {x ∈R^d≥ : |x| = 1} for its intersection with the unit sphere S^{, where} |·| is the euclidean norm onR^d^{. A matrix}a∈ M+:=M(d×d,R≥)is calledallowable, if it has no zero line or column. Any allowable matrix leavesV :=R^d≥\ {0}invariant and one can define its action onS≥by

a·x:= ax

|ax|, x∈S≥.

If µ is a probability distribution on allowable matrices in M+ thenV is µ-a.s. invariant. Let(An)n∈Nbe a sequence of independent identically distributed (iid) random matrices with lawµ, thenMn=AnMn−1defines a Markov chain onV.

The aim of this note is to study the bounded harmonic functions of(M_n)_n∈_N₀ under some additional equicontinuity condition on the functions. Besides being of interest in its own right, the absence of nontrivial bounded harmonic functions appears promi- nently in the proof of Kesten’s renewal theorem [8] and has been recently used in [10] to determine the set of fixed points of the multivariate distributional equation associated with the random matrices(T1, . . . ,TN)∈ M^N₊,

Y =^d T₁Y₁+. . .T_NY_N, (1.1)

whereN ≥2is fixed,Y, Y₁, . . . , Y_N are iidR^d≥-valued random variables and independent of(T₁, . . . ,T_N).

∗The author was supported by the Deutsche Forschungsgemeinschaft (SFB 878).

†University of Münster, Germany E-mail:[email protected]

(2)

The idea of proof is based on the Choquet-Deny lemma used by Kesten in the proof of his renewal theorem [8, Lemma 1]. By restricting to the more specialized setting of Markov chains generated by the action of nonnegative matrices and using recent results on products of random matrices from Buraczewski, Damek and Guivarch [3], this proof can be considerably shortened and, as we hope, thereby made more illuminating.

2 Statement of Results

The Markov chain (Mn)_n∈N₀ will be studied in the decompositionMn =e^SⁿXn for Xn∈S≥andSn∈R. Note that up to an exponential transform, this corresponds to the decompositionV =S≥×R>, whereR>= (0,∞). One easily deduces that

X_n=A_n·X_n−1, S_n−S_n−1= log|A_nX_n−1|,

hence(Xn, Sn)_n∈N₀ is a Markov chain onS≥×Rthat carries the additional structure of a Markov random walk.

Writing int(A) for the topological interior of a set A, recall that by the Perron- Frobenius Theorem, anya ∈ int(M+)possesses a unique largest eigenvalue λ_a ∈R>

with corresponding normalized eigenvectorw_a∈int(S≥).

Definition 2.1. A subsemigroupΓ⊂ M₊is said to satisfy condition(C), if 1. everya∈Γis allowable

2. no subspaceW (R^d^withW ∩R^d≥6={0}satisfiesΓW ⊂W and 3. Γ∩int(M+)6=∅.

Denote by [suppµ] the smallest closed semigroup of M+ generated bysuppµ and writeC_b(E)for the set of bounded continuous functions on the spaceE. Abbreviating Π_n =A_n. . .A₁, define for eachx∈S≥ a probability measurePxon the path space of (X_n, S_n)_n∈_N₀by

P^x

(X0, S0, . . . , Xn, Sn)∈B

=P

(x,0, . . . ,Πn·x,log|Πnx|)∈B

for alln∈Nand measurableB. The corresponding expectation symbol is denoted by E^x^.

Theorem 2.2. Let[suppµ]satisfy(C). Assume thatL∈ C_b(S≥×R)satisfies (a) L(x, s) =E^xL(X1, s−S1)for all(x, s)∈S≥×R^{, and}

(b) for allz∈int(S≥),

y→zlimsup

t∈R

|L(y, t)−L(z, t)|= 0.

ThenLis constant.

It is interesting to observe that (b) is an equicontinuity property for the family (L(·, t))t∈R of functions inCb(S≥). In fact, the Arzelà-Ascoli theorem is applicable and yields that for allt∈R

lims→tsup

y∈R

|L(y, s)−L(y, t)|= 0.

Each pair of functions f ∈ C_b(S≥), h ∈ C_b(R) defines a composite function f ⊗h ∈ C_b(S≥×R) by(f ⊗h) (u, s) := f(u)h(s). WriteC_b(S≥)⊗ C_b(R) for the set of all finite linear combinations of such functions (tensor product). Then the following corollary is obvious:

(3)

Corollary 2.3. Let[suppµ]satisfy condition(C). IfL∈ C_b(S≥)⊗ C_b(R)is harmonic for the Markov chain(X_n, S_n)_n∈_N₀, thenLis constant.

The further organisation of the paper is as follows. At first, we repeat for the readers convenience important implications of(C), based on [3]. Then we turn to the proof of the main theorem. It will be assumed throughout thatd >1 and that[suppµ]satisfies (C). In Section 5 we provide some examples for which condition(C)is satisfied and discuss its role in the proof of Kesten’s renewal theorem. Finally, we describe briefly how to extend the result to Markov chains onR^d generated by the action of invertible matrices.

3 Implications of Condition (C)

Under eachPx,x∈S≥,(X_n)_n∈_N₀ constitutes a Markov chain with transition opera- torP :C_b(S≥)→ C_b(S≥)defined by

P f(y) = Z

f(a·y)µ(da) =Ef(A₁·y), y∈S≥. AbbreviatingΓ = [suppµ], write

W(Γ) ={wa :a∈Γ∩int(M+)}

for the closure of the set of normalized Perron-Frobenius eigenvectors, and Λ(Γ) ={logλa : a∈Γ∩int(M+)}

for the logarithms of the corresponding Perron-Frobenius eigenvalues.

Proposition 3.1([3, Propositions 3.1 & 3.2]).The setΛ(Γ)generates a dense subgroup ofR. There is a uniqueP- stationary probability measureνonS≥, andsuppν =W(Γ).

SinceS≥is compact, the uniqueness ofνimplies the following ergodic theorem (see [1])

n→∞lim 1 n

n

X

k=1

f(X_k) = Z

f(y)ν(dy) Px-a.s. (3.1)

for allx∈S≥,f ∈ C_b(S≥).

Proposition 3.1 also implies the following “weak” aperiodicity property of(Sn)n∈N0, which is an adaption of conditionI.3in [8]. As usual,B_ε(z) :={y∈E:|y−z|< ε} for ε >0,z∈E.

Lemma 3.2. There exists a sequence (ζ_i)_i∈_N ⊂ Rsuch that the group generated by (ζ_i)_i∈_Nis dense inRand such that for eachζ_ithere existsz∈int(S≥)with the following properties:

1. ν B_ε(z)

>0for allε >0.

2. For allδ >0there isεδ >0such that for allε∈(0, εδ)there arem∈N^andη >0, such that forB:=Bε(z):

Px(X_m∈B, |Sm−ζ_i|< δ)≥η for allx∈B. (3.2) The first property together with (3.1) entails thatB is a recurrent set for(X_n)_n∈_N. By a geometric trials argument (see e.g. [2, Problem 5.10]), it follows that for allδ >0 and sufficiently smallε >0there ism∈N^{such that}

P^x(|Xn−z|< ε,|Xn+m−z|< ε,|Sn−(Sn+m−ζi)|< δi.o.) = 1 (3.3) We repeat the short proof of Lemma 3.2 from [3, Prop. 5.5], for it clarifies the importance of Proposition 3.1 and moreover, we want to strengthen the result a bit.

(4)

Proof. By Prop. 3.1, the setΛ(Γ)generates a dense subgroup ofR, hence it contains a countable sequence(ζ_i)which still generates a dense subgroup. Fixζ_i. Thenζ_i= logλ_a for somea∈Γ∩int(M+), set

z:=wa∈W(Γ)∩int(S≥).

Referring again to Prop. 3.1,z∈suppν, thus (1) follows.

Now fixδ > 0. Then for all ε >0 sufficiently small, sincewais a Perron-Frobenius eigenvector,

a·B_ε(w_a)⊂B_ε/2(w_a),

|logλa−log|ax||< δ/2 for allx∈Bε(wa).

Sincea ∈[suppµ], there ism ∈N ^{such that}a =a_m. . .a₁, a_j ∈suppµ,1 ≤j ≤m, hence for allγ >0,

P(An· · ·A1∈Bγ(a)) =ηγ >0.

Ifγ >0is chosen sufficiently small, then for alla⁰∈Bγ(a), a⁰·Bε(wa)⊂Bε(wa),

|logλa−log|a⁰x||< δ for allx∈Bε(wa).

Consequently, for allx∈Bε(wa),

P(|Πn·x−wa|< ε, |log|Πnx| −logλa|< δ)≥ηγ >0.

Recalling the definition ofP^x, this gives (3.2).

4 Proof of the Main Theorem

LetL∈ C_b(S≥×R). For a compactly supported functionh∈ C_b(R)define Lh(x, s) =

Z

L(x, s+r)h(r)dr.

If for each suchh,Lhis constant, then the same holds true forLitself – this can be seen by choosing a sequencehnof probability densities, such thathn(r)drconverges weakly towards the dirac measure in 0.

Lemma 4.1. LetL∈ C_b(S≥×R)satisfy properties (a),(b) of Theorem 2.2. Then for any compactly supportedh∈ C_b(R),L_hstill satisfies (a),(b) and moreover:

(c) For allz∈int(S≥),

y→zlimlim

δ↓0 sup

|t−t⁰|<δ

|Lh(z, t)−Lh(y, t⁰)|= 0.

Proof. That(a)and(b)persist to hold forLh is a simple consequence of Fubini’s theorem resp. Fatou’s lemma.

In order to prove(c), let|L| ≤C. Consider lim

δ→0 sup

y∈S≥

sup

|t−t⁰|<δ

|L_h(y, t)−L_h(y, t⁰)|

= lim

δ→0 sup

y∈S≥

sup

|t−t⁰|<δ

Z

L(y, t⁰+r)h(r−(t−t⁰))dr− Z

L(y, t⁰+r)h(r)dr

≤lim

δ→0 sup

|t−t⁰|<δ

C Z

|h(r−(t−t⁰))−h(r)|dr= 0,

(5)

where the uniform continuity ofhwas taken into account for the last line. Combine this with(b)to obtain for allz∈int(S≥),

y→zlimlim

δ↓0 sup

|t−t⁰|<δ

|L_h(z, t)−L_h(y, t⁰)|

≤lim

y→zlim

δ↓0 sup

|t−t⁰|<δ

h|Lh(z, t)−Lh(y, t)|+|Lh(y, t)−Lh(y, t⁰)|i

≤lim

y→zsup

t∈R

|L_h(z, t)−L_h(y, t)|+ lim

δ→0 sup

y∈S≥

sup

|t−t⁰|<δ

|L_h(y, t)−L_h(y, t⁰)|= 0.

Consequently, in order to proof Theorem 2.2, we may w.l.o.g. assume thatLsatisfies properties(a)−(c).

Proof of Theorem 2.2. The burden of the proof is to show that for all the ζ_i of Lemma 3.2,

L(x, s) =L(x, s+ζ_i) for all(x, s)∈S≥×R. (4.1) If this holds true, then for anyσ=PN

i=1ciζi withci∈N⁰^,N ∈N L(x, s) =L(x, s+σ) for all(x, s)∈S≥×R. But the set ofσ’s is dense inR, thus by the continuity ofL,

L(x, s) =L(x,0) for all(x, s)∈S≥×R.

HenceL(x, s)reduces to a function L˜ onS≥, which is then bounded harmonic for the ergodic Markov chain(X_n)_n∈_N₀ (see (3.1)), thusL˜is constant.

Now we are going to prove (4.1). Considering (a), L(X_n, s−S_n)_n∈_N₀ constitutes a bounded, hence a.s. convergent martingale under eachPxwith

L(x, s) =Ex lim

n→∞L(X_n, s−S_n) for all(x, s)∈S≥×R. (4.2) Fix anyζ_i and the correspondingz ∈ int(S≥), defined in Lemma 3.2. Referring to(c), for allξ >0, there areδ, ε >0such that

sup

u,y∈Bε(z)

sup

|t−t⁰|<δ

|L(u, t)−L(y, t⁰)|< ξ.

Combining this with (3.3), we infer that for alls∈R^,

Px(|L(Xn, s−S_n)−L(X_n+m, s+ζ_i−S_n+m)|< ξi.o.) = 1.

Hence for all(x, s)∈S≥×R^,

n→∞lim L(X_n, s−S_n) = lim

n→∞L(X_n, s+ζ_i−S_n) Px-a.s.

and consequently, using (4.2), it follows for all(x, s)∈S≥×R L(x, s) =Ex lim

n→∞L(X_n, s−S_n) =Ex lim

n→∞L(X_n, s+ζ_i−S_n) =L(x, s+ζ_i).

(6)

5 On Conditon (C)

5.1 Comparison with Kesten’s Assumptions

Since Kesten’s renewal theorem is formulated for Markov chains on a general state space, his Choquet-Deny lemma [8, Lemma 1] holds for a broader class of Markov chains than just those generated by random matrices. Nevertheless, the latter ones provide by far the most important applications, hence condition(C)should be compared to the assumptions of Kesten’s renewal theorem for products of random matrices [7, Theorem A].

Firstly, in [7, Theorem A] it is assumed that the matrices in suppµ do not have a zero row, instead of no zero rowand now zero column. But the latter assumption has the advantage of being invariant under taking the transpose. In fact, if(C)holds forΓ, than it holds forΓ^>as well, condition(2)being translated by considering the orthogonal spaces

W^⊥={y∈R^d : hx, yi= 0∀x∈W}.

Secondly, Kesten’s assumption [7, (1.11)] requests (3) as well, while the “nonlattice”

part of [7, (1.11)] is replaced by the more natural assumption (2) that the problem may not be reduced to a lower dimensional one.

5.2 Examples

A convenient way to check the irreducibility assumption (2) is to consider the eigenspaces of matrices generated byµ. In dimensiond= 2, for example, it is sufficient that there are two matrices the eigenvectors of which are pairwise independent: Any proper subspace W is onedimensional, and if it is invariant for [suppµ], then it is in particular invariant for any matrixa∈suppµ, i.e. an eigenspace ofa.

Hence a simple example of a distribution satisfying (C)is given by the probability law that puts massesp,1−q >0on the two matrices

a:=

1 1 1 1

, b:=

1 1 2 2

,

the eigenvectors being(1,1)^>,(−1,1)^>resp.(1,2)^>,(−1,1)^>. Though the second eigenvectors are the same, the corresponding linear spaces do not intersect the positive cone except in{0}, thus (2) is satisfied, as well as (1) and (3) obviously are.

A second example where (C) holds is when µ has a density with respect to the Lebesgue measure onM+, seen as a subset ofR^d×d≥ . Again conditions (1) and (3) are obviously satisfied. If nowW is an invariant subspace, consider a set of independent vectorsv₁, . . . , v_k generating the orthogonal spaceW^⊥. W being invariant then implies that for any fixedx∈W,

hax, v1i=· · ·=hax, vki= 0 forµ-a.e.a.

But the set of matrices satisfying this set of equations has entries from ak×d-dimensional subspace ofR^d×d, hence has mass zero under the Lebesgue measure.

Finally, a negative example satisfying the assumptions of [7, Theorem A], but not conditon(C), is given by the law that puts massesq,1−q >0on

a⁰ := 1/2 e e

e e

, b⁰:= 1/2

e^π e^π e^π e^π

.

6 Invertible Matrices

Let us finally mention that a result similar to Theorem 2.2 holds for invertible matrices: In the following, letµbe a distribution onGL(d,R).

(7)

Definition 6.1. A subsemigroupΓ∈GL(d,R)is said to beirreducible-proximal (i-p), if 1. no finite unionW =Sn

i=1W_iof proper subspaces{0}(W_i(R^d^satisfiesΓW ⊂W (irreducibility) and

2. there isg∈Γhaving a algebraically simple dominant eigenvalueλg∈R^{such that}

|λg|= limn→∞kgⁿk^1/n(proximality).

This condition has been studied intensively by Guivarc’h and Le Page [4, 5, 6]. Con- sidering conditioni-p, Proposition 3.1, on which our proof rests, can be replaced by [4, Proposition 2.5] which is the corresponding result fori-p matrices. Then following the lines of the proof of Theorem 2.2, one obtains the following:

Theorem 6.2. Let[suppµ]satisfyi-p. Assume thatL∈ C_b(S×R)satisfies (a) L(x, s) =ExL(X₁, s−S₁)for all(x, s)∈S×R^{, and}

(b) for allz∈S^,

y→zlimsup

t∈R

|L(y, t)−L(z, t)|= 0.

ThenLis constant.

References

[1] Leo Breiman, The strong law of large numbers for a class of Markov chains, Ann. Math.

Statist.31(1960), 801–803. MR-0117786

[2] Leo Breiman,Probability, Addison-Wesley, 1968. MR-0229267

[3] Dariusz Buraczewski, Ewa Damek, and Yves Guivarc’h,On multidimensional Mandelbrot’s cascades, arXiv:1109.1845.

[4] Yves Guivarc’h and Émile Le Page,Spectral gap properties and asymptotics of stationary measures for affine random walks, arXiv:1204.6004.

[5] Yves Guivarc’h and Émile Le Page, Simplicité de spectres de Lyapounov et propriété d’isolation spectrale pour une famille d’opérateurs de transfert sur l’espace projectif, Ran- dom walks and geometry, Walter de Gruyter GmbH & Co. KG, Berlin, 2004, pp. 181–259.

MR-2087783

[6] Yves Guivarc’h and Émile Le Page,Homogeneity at infinity of stationary solutions of multivariate affine stochastic recursions, Random Matrices and Iterated Random Functions:

Münster, October 2011 (Matthias Löwe Gerold Alsmeyer, ed.), Springer Proceedings in Mathematics & Statistics, vol. 53, Springer, 2013.

[7] Harry Kesten, Random difference equations and renewal theory for products of random matrices, Acta Math.131(1973), 207–248. MR-0440724

[8] Harry Kesten,Renewal theory for functionals of a Markov chain with general state space, Ann. Prob.2(1974), no. 3, 355–386. MR-0365740

[9] Claudia Klüppelberg and Serguei Pergamenchtchikov, Renewal theory for functionals of a Markov chain with compact state space, Ann. Prob. 31(2003), no. 4, 2270–2300. MR- 2016619

[10] Sebastian Mentemeier,On Multivariate Stochastic Fixed Point Equations: The Smoothing Transform and Random Difference Equations, Ph.D. thesis, University of Münster, 2013.

1Introduction SebastianMentemeier AnoteonKesten’sChoquet-Denylemma

A note on Kesten’s Choquet-Deny lemma

Sebastian Mentemeier

1 Introduction

2 Statement of Results

3 Implications of Condition (C)

4 Proof of the Main Theorem

5 On Conditon (C)

6 Invertible Matrices

References

Electronic Communications in Probability

Advantages of publishing in EJP-ECP

• Very high standards

• Free for authors, free for readers

• Quick publication (no backlog)

Economical model of EJP-ECP

• Low cost, based on free software (OJS

)

• Non profit, sponsored by IMS

, BS

, PKP

• Purely electronic and secure (LOCKSS

)

Help keep the journal free and vigorous

• Donate to the IMS open access fund

(click here to donate!)

• Submit your best articles to EJP-ECP

• Choose EJP-ECP over for-profit journals