Random Dynamics and its Applications

Yuri Kifer

Abstract. Random transformations emerge in a natural way as a model for description of a physical system whose evolution mechanism depends on time in a stationary way. This leads to the study of actions of compositions of different maps chosen from a typical sequence of transformations. The question whether such actions are chaotic can be dealt with employing the random thermodynamic formalism developped in recent years. This theory has nice applications to random networks, fractal dimensions of random sets and other models.

1991 Mathematics Subject Classification: Primary 58F11; Secondary 60J99, 60F15 Keywords and Phrases: random transformations, thermodynamic formalism, limit theorems

1. Introduction

Evolution of many physical systems can be better described by compositions of different maps, i.e. time dependent transformations, rather than by repeated application of exactly the same transformation. It is natural to study such problems for typical in some sense sequences of maps which leads to the framework of random transformations.

This set up was discussed already in Ulam and von Neumann [UN] and in Kakutani [Ka] in connection with random ergodic theorems. Later this topic was studied in the framework of the relativized ergodic theory (Thouvenot [Th], Ledrappier and Walters [LW]) but the real push this subject received in 80-ies when stochastic flows appearing as solutions of stochastic differential equations provided a rich source of random diffeomorphisms (see references and the historical review in Arnold [Ar]). This prompted, in particular, the book [Ki1] which, in turn, played a role in motivating other work such as the general relativized variational principle (Bogenschütz [Bo]) and some results in smooth random dynamics. Further developments of the latter included random invariant manifolds, Lyapunov exponents, and a random bifurcation theory (see Arnold [Ar] and references there), random versions of the Margulis-Ruelle entropy inequality (see Kifer [Ki1], Liu and Qian [LQ], Bahnmüller and Bogenschütz [BB]) and of the Pesin entropy formula and the corresponding characterization of the random Sinai-Ruelle-Bowen measures ( see Ledrappier and Young [LY], Liu and Qian [LQ], Bahnmüller and Liu [BL]), and the random thermodynamic formalism (see Kifer [Ki2], Bogenschütz and Gundlach [BG], Khanin and Kifer [KK]).

The formal set up consists of a probability space (Ω, A, P) together with a P −preserving ergodic invertible map θ : Ω → Ω, of another measurable space (X, B), and of a measurable subset X of X×Ω with fibers X^{ω} = {x ∈ X : (x, ω) ∈ X} ∈ B. The dynamics is given by a mesurable map τ : X → X which is a skew product transformation τ(x, ω) = (F_{ω}x, θω) where the fiber maps F_{ω} : X^{ω} → X^{θω} with the composition rule F_{ω}^{n} = F_{θ^{n−1}ω} ∘ ⋯ ∘ F_{θω} ∘ F_{ω} : X^{ω} → X^{θ^{n}ω} are called random transformations.

Theory of random transformations concerns mainly with actions of F_{ω}^{n} for typical ω ∈ Ω, i.e. except of ω′s forming a set of zero P −measure. I shall discuss here only certain aspects of ergodic theory of random transformations related mainly to the random thermodynamic formalism which is crucial in describing chaotic (stochastic) spatial behaviour of compositions F_{ω}^{n} for typical ω. Familiar signs of stochastic behavior are the central limit theorem (CLT), the law of iterated logarithm (LIL), large deviations (LD) etc. which hold true for some classes of random transformations such as random expanding in average maps, random subshifts of finite type and certain random hyperbolic diffeomorphisms. The theory has applications to random networks, computations of fractal dimensions of random sets, and to random walks with stationarily changing distributions which also will be discussed in this paper. Recently random diffeomorphisms were employed in some models of statistical physics (see Ruelle [Rue]).

2. Random Thermodynamic Formalism

Let P_{P} (X) be the space of probability measures on X whose marginal on Ω coincides with P. I assume that all spaces under consideration are Borel subsets of Polish spaces, and so any μ ∈ P_{P} (X) has an essentially unique desintegration μ(dx, dω) = μ^{ω}(dx)P (dω) with μ^{ω}, ω ∈ Ω being a measurable family of probability measures on X^{ω}. It is easy to see that μ is τ−invariant if and only if F_{ω}μ^{ω} = μ^{θω} P −almost surely (a.s.). Accordingly, a measurable set A ⊂ X is τ−invariant if and only if its fibers A^{ω} = {x : (x, ω) ∈ A} satisfy F_{ω}A^{ω} = A^{θω} P −a.s.

Given μ ∈ P_{P} (X) the relativized or fiber entropy h_{μ}^{(r)}(τ) of τ can be defined as the conditional entropy of τ with respect to the σ−algebra π^{−1}A where π : X → Ω is the natural projection to the second factor (see [LW], [Ki1], [Bo]). Another way to obtain h_{μ}^{(r)}(τ), somewhat similar to the deterministic case, is via finite partitions R = {R_{1}, ..., R_{n}} of X into measurable sets. Set R_{i}^{ω} = {x : (x, ω) ∈ R_{i}} and R^{ω} = {R_{1}^{ω}, ..., R_{n}^{ω}} then P −a.s.,

(2.1)  h_{μ}^{(r)}(τ) = sup_{R} lim_{n→∞} \frac{1}{n}H_{μ_{ω}} ( ⋁_{i=0}^{n−1}(F_{ω}^{i})^{−1}R^{θ^{i}ω}) .

Existence of this limit follows from Kingman’s subadditive ergodic theorem (see [Ki1]).

Assume now that X is compact and the fibers X^{ω} are Borel subsets of X. For continuous random transformations F_{ω} and any measurable function g on X such that g_{ω}(x) is continuous in x and sup_{x} |g_{ω}(x)| ∈ L^{1}(Ω, P) introduce another useful quantity, called the relativized (fiber) topological pressure Q_{τ} (g), by

(2.2)  Q_{τ} (g) = sup_{μ∈P_{P} (X)}(∫ gdμ + h_{μ}^{(r)}(τ)).

The number Q_{τ} (0) denoted by h_{top}^{(r)}(τ) is called the relativized topological entropy. Actually, similarly to the deterministic case the proper definition of Q_{τ} (g) is via (ω, n, ε)−separated sets (see [Ki1] and [Bo]) and then (2.2), called the relativized variational principle, is derived as a theorem. Under rather general conditions, called (random) expansivity, one can show that h_{μ}(τ) is upper semicontinuous in μ, and so the supremum in (2.2) is attained at some μ ∈ P_{P} (X) which is called an equilibrium state. If a maximizing measure is unique it has usually nice properties. Equilibrium states are related to Gibbs measures and both have their roots in statistical mechanics where g plays the role of a potential.

Next, I shall describe specific models of random transformations which will appear in the following exposition. I shall start with random subshifts of finite type (see [BG] and [KK]) where X^{ω} = X_{A}^{ω} = {x = (x_{0}, x_{1}, ...) : x_{i} ∈ {1, ..., ℓ(θ^{i}ω)} and a_{x_{i}x_{i+1}}(θ^{i}ω) = 1 ∀i = 0, 1, ...}, ℓ : Ω → ℤ_{+} = {1, 2, ...} satisfies 0 < ∫ log ℓdP < ∞, and A(ω) = ((a_{ij}(ω)), ω ∈ Ω is a measurable family of ℓ(ω)×ℓ(θω)− matrices with 0 and 1 entries such that P −a.s. A(ω) has no zero row. Random transformations F_{ω} act on X^{ω} as left shifts (F_{ω}x)_{i} = x_{i+1}. A random subshift of finite type is called topologically mixing if there exists a ℤ_{+}− valued random variable 0 < N = N_{ω} < ∞ so that P −a.s. A(θ^{−N}ω) ⋯ A(θ^{−2}ω)A(θ^{−1}ω) is a matrix with positive entries. The random Ruelle-Perron-Frobenius (RPF) operator L_{g}^{ω} corresponding to a function g = g_{ω}(x) on X maps functions on X^{ω} to functions on X^{θω} by the formula

(2.3)  L_{g}^{ω}q(x) = ∑_{y∈F_{ω}^{−1}x} e^{g_{ω}(y)}q(y).

Suppose that E sup_{x} |g_{ω}(x)| < ∞ and

(2.4)  |g_{ω}(x) − g_{ω}(y)| ≤ K_{g}(ω)(dist(x, y))^{κ}

for some κ > 0 and a random variable K_{g}(ω) > 0 with E| log K_{g}| < ∞, where dist(x, y) = e^{−min{i≥0:x_{i}≠y_{i}}} and E denotes the expectation on (Ω, A, P). Then the random RPF theorem ([KK], [BG]) yields that there exists a unique positive random variable λ = λ_{ω} with E| log λ| < ∞, a positive function h = h_{ω}(x), and ν ∈ P_{P} (X) having desintegrations ν^{ω} such that

(2.5)  L_{g}^{ω}h_{ω} = λ_{ω}h_{θω}, (L_{g}^{ω})^{∗}ν^{θω} = λ_{ω}ν^{ω}, and ∫_{X^{ω}} h_{ω}dν^{ω} = 1.

Then the relativised topological pressure of g has the form Q_{τ} (g) = ∫ log λ_{ω}dP (ω) and μ ∈ P_{P} (X) having desintegrations μ^{ω} satisfying dμ^{ω} = h_{ω}dν^{ω} is τ−invariant and it is the unique equilibrium state for g.

This set up is quite appropriate to study randomly evolving graphs or random networks N where V (ω) = {1, 2, ..., ℓ(ω)} is the set of vertices for an (evironment) ω and I connect by an arrow i ∈ V (ω) to j ∈ V (θω) iff a_{ij}(ω) = 1. A sequence (i_{0}, i_{1}, ..., i_{n}) is a path in N iff a_{i_{k}i_{k+1}}(θ^{k}ω) = 1 ∀k = 0, 1, ..., n − 1. The topologically mixing condition formulated above yields that for any i ∈ V (ω) and j ∈ V (θ^{n}ω) with n sufficiently large there exists a path of length n in N starting at i and ending at j. In the next section I shall formulate general limit theorems which can be applied, in particular, to describe statistical properties of paths in such random networks. More general models of multidimensional random subshifts of finite type and of random sofic shifts, which also have combinatorial applications, were studied in [Ki3] and [GK2], respectively.

By constructing random Markov partitions and employing random subshifts of finite type one can study also random (spatially uniform) hyperbolic diffeomorphisms which have random expanding and contracting (in average) invariant subbundles (see [Li], [GK1]). As an example of this situation take, for instance, F_{ω} = f_{ω}^{n(ω)} where f_{ω} is a random diffeomorphism whose all realizations belong to a small C^{2} neighborhood of one Anosov diffeomorphism (or a diffeomorphism having a basic hyperbolic set) and n = n(ω) is a random variable taking values 0, 1, 2, ... with 0 < ∫ log(1 + n)dP < ∞. Another interesting example of a random Anosov diffeomorphism is due, essentially, to Arnoux and Fisher. Let σ : Ω → Ω be a P −preserving ergodic invertible map and assume that θ = σ^{2} is also ergodic. Random transformations here are automorphisms

of the torus 𝕋^{2} given by F_{ω} = ( \begin{matrix}1 + n(ω)n(σω) & n(σω) \\ n(ω) & 1 \end{matrix} ) where n = n(ω)

is a ℤ_{+}−valued random variable with log n ∈ L^{1}(ω, P). Denote by [k_{1}, k_{2}, ...]

the continued fraction \frac{1}{k_{1} + \frac{1}{k_{2} + ⋯}} and set a(ω) = [n(ω), n(σω), n(σ^{2}ω), ...],

b(ω) = [n(σ^{−1}ω), n(σ^{−2}ω), ...]. Define ξ(ω) = ( \begin{matrix}a(ω) \\ −1 \end{matrix} ) , η(ω) = ( \begin{matrix}1 \\ b(ω) \end{matrix} ) ,

λ(ω) = a(ω)a(σω) and γ(ω) = (b(σω)b(σ^{2}ω))^{−1}. Then F_{ω}ξ(ω) = λ(ω)ξ(θω), F_{ω}η(ω) = γ(ω)η(θω), λ(ω) < 1, γ(ω) > 1, and so, ξ and η span the contracting and expanding (in average) directions, respectively. Allowing also zero values of n(ω) one can achieve even that the angles between these directions may approach zero arbitrarily close. All these constructions fall into a more general class of random diffeomorphisms having in the tangent bundle random invariant (expanding in average) cone families (see [GK1]).

In the continuous time case the situation is more complicated and, essentially, no ergodic theory of random (spatially uniform) hyperbolic flows exists, as yet, which could provide constructions of equilibrium states via a thermodynamic formalism approach (cf. [GK1]). A successful theory should include natural perturbation models such as a random flow generated by a random vector field whose all realizations are close to a deterministic vector field generating an Anosov flow. Meanwhile, only simple examples can be dealt with. Consider, for instance, a random flow F_{ω}^{t} given by the equation \frac{dF_{ω}^{t}x}{dt} = q_{θ^{t}ω}(F_{ω}^{t}x)B(F_{ω}^{t}x) where θ^{t} is an ergodic P −preserving flow on Ω, q_{ω} is a measurable family of smooth positive functions on a compact Riemannian manifold M, and B is a vector field generating a transitive Anosov flow f^{t} on M. Then F_{ω}^{t} is obtained from f^{t} by the random time change and both flows have the same orbits. Using a Markov partition for f^{t} one can represent F_{ω}^{t} as a suspension over a random subshift of finite type with a random ceiling function bounded away from zero and infinity (see [Ki6]).

Another model I have in mind is the case of expanding in average smooth random maps considered in [KK] which can be studied directly without a symbolic representation. Assume for simplicity that all X^{ω}’s coincide with one compact connected d−dimensional C^{2} Riemannian manifold M and all F_{ω} : M → M are C^{2} endomorphism of M such that log ∥DF_{ω}^{−1}∥, log ∥DF_{ω}∥ ∈ L^{1}(Ω, P) and ∫ log ∥DF_{ω}^{−1}∥dP (ω) < 0 where DF is the differential of F and ∥·∥ is the supremum norm. The random RPF operator L_{g}^{ω} is defined again by (2.3) and if g′_{ω}s are Hölder continuous, i.e. (2.4) is satisfied with an integrable log K_{g}, then the random RPF theorem holds true yielding a random variable λ_{ω} > 0, a function h = h_{ω}(x) > 0 on M ×Ω, and probability measures ν^{ω} on M satisfying (2.5) so that μ ∈ P_{P} (X) with desintegrations μ^{ω} satisfying dμ^{ω} = h_{ω}dν^{ω} is the unique equilibrium state for g. Both in this model and in the case of random Anosov (hyperbolic) diffeomorphisms there are relativized Sinai-Ruelle-Bowen measures μ_{SRB} having special properties which are equilibrium states for the functions φ_{ω}^{u}(x) equal minus logarithm of the Jacobian of either D_{x}F_{ω} (in the expanding case) or of the restriction of D_{x}F_{ω} to the random expanding subbundle (in the hyperbolic case).

3. Limit theorems for random transformations

In this section I shall formulate the LD, CLT, and LIL results for random transformations F_{ω} belonging to one of the specific classes considered in the previous section. Set I_{g}(ν) = Q_{τ} (g)−∫ gdν −h_{ν}^{(r)}(τ) if ν ∈ P_{P} (X) and ν is τ−invariant, while I_{g}(ν) = ∞, otherwise, and put J_{g,q}(r) = inf{I_{g}(ν) : ∫ qdν = r} if a ν ∈ P_{P} (X) satisfying conditions in brackets exists and J_{g,q}(r) = ∞, otherwise.

3.1. Theorem. (cf.[Ki2]) Suppose that Ω is a locally compact space. Let μ ∈ P_{P} (X) with desintegrations dμ(x, ω) = dμ^{ω}(x)dP (ω) be the unique equilibrium state for a function g satisfying conditions of the corresponding RPF-theorem (i.e. (2.4) holds true). Set ζ_{x,ω}^{n} = \frac{1}{n} ∑_{k=0}^{n−1} δ_{τ^{k}(x,ω)}, where δ_{z} is the Dirac measure at z, and S_{n}q(x, ω) = n ∫ qdζ_{x,ω}^{n} = ∑_{k=0}^{n−1} q∘τ^{k}(x, ω). Then for each bounded continuous function q and any numbers r_{1} < r_{2},

(3.1)  − inf_{r∈[r_{1},r_{2}]} J_{g,q}(r) ≥ lim sup_{n→∞} \frac{1}{n} log μ^{ω}\{x ∈ X^{ω} : \frac{1}{n}S_{n}q(x, ω) ∈ [r_{1}, r_{2}]\}

≥ lim inf_{n→∞} \frac{1}{n} log μ^{ω}\{x ∈ X^{ω} : \frac{1}{n}S_{n}q(x, ω) ∈ (r_{1}, r_{2})\} ≥ − inf_{r∈(r_{1},r_{2})} J_{g,q}(r)

P −a.s. The large deviations estimates for occupational measures ζ_{x,ω}^{n}, i.e. the upper and lower bounds for the limits of n^{−1} log μ^{ω}{x ∈ X^{ω} : ζ_{x,ω}^{n} ∈ G}, (with G being a closed or open set of probability measures on X×Ω) hold true, as well, with the rate functional I_{g}(ν). In the case of random expanding in average transformations of a compact Riemannian manifold M or random Anosov diffeomorphisms the results remain true if μ^{ω} is replaced by the normalized Riemannian volume m on M and one takes g_{ω}(x) = φ_{ω}^{u}(x).

Observe, that I_{g}(ν) = 0 and J_{g,q}(r) = 0 if and only if ν = μ and r = ∫ qdμ. Therefore, (3.1) estimates large deviations from the ergodic theorem, i.e. it describes the decay of μ−measure of points having irregular with respect to μ behavior.

In the case of random subshifts of finite type Theorem 3.1 can be modified to become a combinatorial statement on random networks (see [Ki5]). For α = (α_{0}, ..., α_{n}) with a_{α_{i},α_{i+1}}(θ^{i}ω) = 1 ∀i = 0, ..., n − 1 set C_{α}^{ω} = {x ∈ X_{A}^{ω} : x_{i} = α_{i} ∀i = 0, 1, ...n} which is called an n−cylinder set. Denote by Π_{n}^{ω}(a, b) the set of all n−cylinders C_{α_{0},...,α_{n}}^{ω} with α_{0} = a ∈ V (ω) and α_{n} = b ∈ V (θ^{n}ω) and by |R| the cardinality of a set R. Let I(ν) = I_{0}(ν) = h_{top}^{(r)}(τ) − h_{ν}^{(r)}(τ) if ν ∈ P_{P} (X) and ν is τ−invariant, while I(ν) = ∞, otherwise, and put J_{q}(r) = J_{0,q}(r). Then for any bounded continuous function q, a ∈ V (ω), b_{n} ∈ V (θ^{n}ω), x_{α} ∈ C_{α}^{ω}, and numbers r_{1} < r_{2} with probability one as n → ∞, |Π_{n}^{ω}(a, b_{n})|^{−1}|{C_{α}^{ω} ∈ Π_{n}^{ω}(a, b_{n}) : n^{−1}(S_{n}q)(x_{α}, ω) ∈ (r_{1}, r_{2})}| ≍ exp(−n inf_{r∈(r_{1},r_{2})} J_{q}(r)). Here ≍ means that both sides of the formula have the same logarithmic asymptotical behavior in the sense of inequalities in (3.1). In particular, if I assign to each edge e of the network N (ω) its length l_{ω}(e) and set q_{ω}(x) = l_{ω}(x_{0}, x_{1}), which gives a continuous function, then this yields large deviations for the average length of paths with n vertices. The corresponding second level of large deviations estimates |Π_{n}^{ω}(a, b_{n})|^{−1}|{C_{α}^{ω} ∈ Π_{n}^{ω}(a, b_{n}) : ζ_{x_{α},ω}^{n} ∈ G}| ≍ exp(−n inf_{ν∈G} I(ν)) for occupational measures holds true, as well.

Next, I formulate the CLT and the LIL from [Ki6]. Let μ be as in Theorem 3.1 and φ = φ_{ω}(x) satisfying ∫ φ_{ω}dμ^{ω} = 0 be a Hölder continuous in x random function with an exponent κ > 0 and a random variable K_{φ}, i.e. φ satisfies (2.4). For a random variable L = L(ω) and a constant C set Q_{L,C} = {ω : L(ω) ≤ C} and k_{L,C}(ω) = min{n : θ^{n}ω ∈ Q_{L,C}}. I say that the L, C integrability condition for φ holds true if ∫ (∑_{i=0}^{k_{L,C}−1}(∥φ∥ + K_{φ}) ∘ θ^{i})^{2}dP < ∞ where ∥φ∥_{ω} = sup_{x} |φ_{ω}(x)|.

3.2. Theorem. There exist a random variable L = L(ω) and a constant C (which can be written explicitly for specific models above) such that if the L, C integrability condition holds true then P −a.s. the limit σ^{2} = lim_{n→∞} \frac{1}{n} ∫ (∑_{j=0}^{n−1} φ_{θ^{j}ω}∘F_{ω}^{j})^{2}dμ^{ω} exists and for P −a.a. ω and any number a,

(3.2) lim_{n→∞} μ^{ω} \{x ∈ X^{ω} : n^{−1/2} ∑_{i=0}^{n−1}(φ ∘ τ^{i})(x, ω) ≤ a\} = \frac{1}{σ\sqrt{2π}} ∫_{−∞}^{a} e^{− \frac{u^{2}}{2σ^{2}}} du

where in the case σ = 0, the normal distribution in the right hand side of (3.2) should be understood as the Dirac measure at 0.

Assuming that σ > 0 the invariance principle for the LIL holds true. Namely, if ζ(t) = (2t log log t)^{1/2} and η_{n}(t) = (ζ(σ^{2}n))^{−1}(∑_{j=0}^{k−1} φ ∘ τ^{j} + (nt − k)φ ∘ τ^{k}) for t ∈ [\frac{k}{n}, \frac{k+1}{n}), k = 0, 1, ..., n − 1 then μ−a.s. the set of limit points in C[0, 1] of functions η_{n}(t) as n → ∞ coincides with the set of absolutely continuous η ∈ C[0, 1] with ∫_{0}^{1}(η̇(t))^{2}dt ≤ 1.

The role of L = L(ω) emerging in Theorem 3.2 is to offset the nonuniformity in ω of the models above so that, for instance, F_{ω}^{n} will be uniformly expanding for n ≥ L(ω) or, in the case of random subshifts of finite type, all matrices A(ω)A(θω) ⋯ A(θ^{n}ω) will be positive for any n ≥ L(ω). In addition, L(ω) bounds some parameters related to the functions g_{ω} and φ_{ω} appearing in Theorem 3.2.

Observe that Theorem 3.2 yields fiber-wise CLT and LIL for some deterministic skew product transformations. For instance, consider an expanding map of the 3-dimensional torus 𝕋^{3} = 𝕋^{1} × 𝕋^{2} given by the formula τ(x, y) = (F_{y}x, θy) where θ is an ergodic automorphism of 𝕋^{2} and F_{y}x = γ(y) + n(y)x (mod 1) where γ(y) ∈ ℝ, n(y) ∈ ℤ_{+} are measurable functions with 0 < ∫_{𝕋^{2}} log n(y)dy < ∞. Since both θ and F_{y}’s preserve the Lebesgue measures (denoted Leb below) on 𝕋^{2} and on 𝕋^{1}, respectively, I can view F_{y}’s as ”random” expanding maps of 𝕋^{1} with Ω = 𝕋^{2}, P =Leb, M = 𝕋^{1}, and μ^{y} =Leb (which is a ”random” Gibbs measure corresponding to the function g_{y} = log n(y)). Theorem 3.2 yields now that for Leb-a.a.y, Leb\{x : \frac{1}{\sqrt{n}} ∑_{l=0}^{n−1} φ ∘ τ^{l}(x, y) ≤ a\} converges as n → ∞ to the right hand side of (3.2) and the corresponding LIL follows, as well.

4. Fractal dimensions of random sets

Any x ∈ [0, 1) can be represented in the form of a ”random base expansion”

(4.1)  x = ∑_{i=0}^{∞} \frac{x_{i}(ω)}{ℓ(ω)ℓ(θω) ⋯ ℓ(θ^{i}ω)}, x_{i}(ω) ∈ \{0, 1, ..., ℓ(θ^{i}ω) − 1\}

where, again, ℓ is a ℤ_{+}−valued random variable satisfying 0 < ∫ log ℓdP < ∞. To make this representation unique one can forbid the tails of the form x_{i}(ω) = ℓ(θ^{i}ω)−1 ∀i ≥ n. Identify 0 and 1 then F_{ω}x = ℓ(ω)x (mod 1) can be considered as a random expanding transformation of the unit circle 𝕋^{1}. If τ(x, ω) = (F_{ω}x, θω) is the skew product transformation and ϕ(x, ω) = x_{0}(ω) then

(4.2)  x_{i}(ω) = (ϕ ∘ τ^{i})(x, ω).

Observe that all F_{ω} preserve the Lebesgue measure m on [0, 1) and the corresponding measure m × P is τ−invariant, has the (maximal) relativized entropy ∫ log ℓdP, and it is the unique equilibrium state for the function − log ℓ. Moreover, it is ergodic, and so m × P −a.s., lim_{n→∞} \frac{1}{n} ∑_{i=0}^{n−1} x_{i}(ω) = \frac{1}{2} ∫ (ℓ − 1)dP assuming that the right hand side exists. In view of (4.2) and Theorem 3.1 one has the large deviations estimates for m\{x : \frac{1}{n} ∑_{i=0}^{n−1} x_{i}(ω) ∈ [r_{1}, r_{2}]\}. Furthermore, by Theorem 3.2 P −a.s. for any number a, lim_{n→∞} m\{x : n^{−1/2} ∑_{i=0}^{n−1}(x_{i}(ω)− \frac{1}{2}(ℓ(θ^{i}ω)−1)) ≤

a\} = \frac{1}{σ\sqrt{2π}} ∫_{−∞}^{a} e^{− \frac{u^{2}}{2σ^{2}}} du. Moreover, σ can be computed here precisely since, when ω is fixed, x_{0}(ω), x_{1}(ω), ... are independent random variables (with stationarily changing distributions) on the space ([0, 1], m), which gives σ^{2} = \frac{1}{12} ∫ (ℓ^{2} − 1)dP provided the right hand side exists.

Consider the sequence space X^{ω} = {x = (x_{0}, x_{1}, ...) : x_{i} ∈ {0, 1, ..., ℓ(θ^{i}ω) − 1}} and the map π^{ω} : [0, 1) → X^{ω}, π^{ω}(x) = (x_{0}(ω), x_{1}(ω), ...) then F_{ω}π^{ω} = π^{ω}f_{ω} where f_{ω} is the left shift on X^{ω}. Thus π^{ω} is a semi-conjugacy and, in fact, this symbolic representation comes from the random Markov partition of [0, 1) into ℓ(ω) equal subintervals.

A measurable set G ⊂ 𝕋^{1} × Ω is τ−invariant iff F_{ω}G^{ω} = G^{θω} where G^{ω} = {x : (x, ω) ∈ G}. Such sets can be obtained, for instance, considering x whose expansion (4.1) does not contain certain prescribed digits which may be called random Cantor sets. Assuming that all G^{ω} are compact one has the following formula for their Hausdorff dimension (see [Ki4]),

(4.3)  HD(G^{ω}) = \frac{h_{top}^{(r)}(τ, G)}{∫ log ℓdP} P − a.s.

where h_{top}^{(r)}(τ, G) is the relativised tological entropy of τ restricted to G. Next, I consider another class of random invariant sets which are dense in [0, 1). Set N_{kl}^{ω}(x, n) = |{j ≥ 0, j < n : ℓ(θ^{j}ω) = k, x_{j}(ω) = l − 1}| and N_{l}^{ω}(x, n) = ∑_{k∈ℤ_{+}} N_{kl}^{ω}(x, n) where |{·}| denotes the cardinality of a set {·}. Let r = (r_{k}, k ∈ ℤ_{+}) be an infinite probability vector and A = (a_{kl}, k, l ∈ ℤ_{+}) be an infinite probability matrix such that a_{kl} = 0 unless l ≤ k. Define the sets U_{r}^{ω} = \{x ∈ [0, 1) : lim_{n→∞} \frac{1}{n}N_{l}^{ω}(x, n) = r_{l} ∀l ∈ ℤ_{+}\} (i.e. prescribing frequencies of digits) and V_{A}^{ω} = \{x ∈ [0, 1) : lim_{n→∞} \frac{1}{n}N_{kl}^{ω}(x, n) = q_{k}a_{kl} ∀k, l ∈ ℤ_{+}\} where q_{k} = P {ℓ = k}.

4.1. Theorem. ([Ki4]) With probability one,

(4.4)  HD(V_{A}^{ω}) = \frac{− ∑_{k∈ℤ_{+}} q_{k} ∑_{l≤k} a_{kl} log a_{kl}}{∫ log ℓdP} =^{def} H_{A},

and so HD(V_{A}^{ω}) = 1 iff a_{kl} = k^{−1} for all l ≤ k and any k ∈ ℤ_{+} such that q_{k} ≠ 0. In the last case with probability one V_{A}^{ω} has also the Lebesgue measure one. The sets U_{r}^{ω} have the Lebesgue measure one for P -a.a.ω iff r_{l} = ∑_{k≥l} q_{k}k^{−1} for all l ∈ Z_{+} (which is a random version of Borel’s normal number theorem). Furthermore, for P -a.a.ω, HD(U_{r}^{ω}) = sup_{A∈A_{qr}} H_{A} =^{def} H, where the supremum is taken over the set A_{qr} of all infinite probability matrices A = (a_{kl}) such that a_{kl} = 0 unless l ≤ k and qA = r with q and r considered as the row vectors. The set A_{qr} is nonempty iff ∑_{l∈F} q_{l} ≥ ∑_{l∈F} r_{l} for any filter F ∈ F in ℤ_{+}, (i.e. if l ∈ F and l ≤ k then k ∈ F). If A_{qr} is empty then with probability one U_{r}^{ω} is empty too.

The expression in the numerator of the right hand side of (4.4) is the fiber entropy of certain random Bernoulli measure which emerges naturally in the proof. Computations of dimensions of different other invariant sets of random tranformations, as well as multidimensional generalizations, can be found in [Ki4].

5. ”Random” random walks on groups

Markov chains with random transition probabilities emerge directly from random subshifts of finite type taken with random Markov measures but also they are closely related ideologically to random transformations (cf. [Ki6]). In this section I consider random walks with stationarily changing distributions on discrete groups and demonstrate how a relativized entropy like characteristic describes their asymptotic behavior.

Let G be a discrete group and μ^{ω}, ω ∈ Ω be a measurable family of probability measures on G. Next, I consider the Markov chain X_{n}^{ω} with random transitions on G, which I call ”random” random walk, with n−step transition probabilities

(5.1)  P^{ω}(n, g_{1}, g_{2}) = μ^{ω} ∗ μ^{θω} ∗ ⋯ ∗ μ^{θ^{n−1}ω}(g_{2}g_{1}^{−1})

where ∗ denotes the usual convolution of measures on groups. Following [Rub] call a measurable in ω and x function h random harmonic if

(5.2)  ∑_{r∈G} P^{ω}(1, g, r)h_{θω}(r) = ∑_{r∈G} h_{θω}(rg)μ^{ω}(r) = h_{ω}(g).

The next natural goal is to describe spaces of random harmonic functions which is related to the asymptotic behavior of X_{n}^{ω}.

Suppose that h is random harmonic and c(ω) = sup_{x} |h_{ω}(x)| < ∞. Since I assume that θ is ergodic it follows from (5.2) that c is constant P −a.s., and so h is bounded. Let e be the identity of G and P^{ω} be the path distribution of the Markov chain X_{n}^{ω}, n ≥ 0, X_{0}^{ω} = e. Is is easy to see that h_{θ^{n}ω}(gX_{n}^{ω}) is a martingale under P^{ω}, and so for all g ∈ G and P^{ω}−a.a. paths ξ ∈ G^{ℤ_{+}} the limit lim_{n→∞} h_{θ^{n}ω}(gX_{n}^{ω}) = φ_{ω}(gξ) exists where gξ = (gξ_{0}, gξ_{1}, ...) for ξ = (ξ_{0}, ξ_{1}, ...) determines the action of G on paths ξ ∈ G^{ℤ_{+}}. Moreover, for any g ∈ G, P −a.a.ω, and P^{ω}−a.a.ξ one has φ_{ω}(gξ) = φ_{θω}(gσξ) where σ is the left shift. Let τ(ξ, ω) = (σξ, θω) and F be the σ−algebra of τ−invariant measurable sets from G^{ℤ_{+}} × Ω. Set F^{ω} = {A^{ω} = {ξ : (ξ, ω) ∈ A} : A ∈ F} and let π_{ω} be the factorizing map of (G^{ℤ_{+}}, P^{ω}) to the quotient space corresponding to the measurable partition attached to F^{ω}. Then one has a Poisson type representation h_{ω}(g) = ∫ φ_{ω}∘π_{ω}dgν^{ω} where ν^{ω} = π_{ω}P^{ω} satisfying μ^{ω} ∗ ν^{θω} = ν^{ω} is naturally to call a random harmonic measure.

For any probability measure η on G set H(η) = − ∑_{g∈suppη} η(g) log η(g) and assume that ∫ H(μ^{ω})dP (ω) < ∞. Let μ_{n}^{ω} = μ^{ω} ∗μ^{θω} ∗⋯ μ^{θ^{n−1}ω} and h_{n}^{ω} = H(μ_{n}^{ω}). Then h_{n+m}^{ω} ≤ h_{n}^{ω} + h_{m}^{θ^{n}ω} and by the subadditive ergodic theorem P −a.s. the limit, called the fiber (or relativized) Avez entropy, h(G, μ) = lim_{n→∞} \frac{1}{n}h_{n}^{ω} exists and it is not random. Let G^{ω} be the support of the measure ∑_{n=1}^{∞} 2^{−n}μ_{n}^{ω} and assume that G^{ω} = G P −a.s.

5.1. Theorem. (i) For P −a.a.ω P^{ω}−a.s., lim_{n→∞} \frac{1}{n} log μ_{n}^{ω}(X_{n}^{ω}) = −h(G, μ); (ii) h(G, μ) = 0 iff there are no random bounded harmonic functions except μ−a.s. constants (where dμ(ξ, ω) = dμ^{ω}(ξ)dP (ω)).

In some cases, for instance, when G is a free group, one can also obtain Hausdorff dimensions of random harmonic measures via h(G, μ) and the speed of convergence of X_{n}^{ω} to infinity. Other results concerning this set up will appear in a forthcoming paper joint with Kaimanovich and Rubshtein. Results on ”random” random walks on continuous groups, in particular, products of independent random matrices with stationarily changing distributions will appear elsewhere.

818 Yuri Kifer

References

[Ar] L. Arnold., Random Dynamical Systems, Springer Verlag, Berlin, 1998.

[Bo] T. Bogenschütz, Entropy, pressure, and a variational principle for random dynamical systems, Random&Comp.Dyn. 1 (1992), 99-116.

[BB] J. Bahnmüller and T. Bogenschütz, A Margulis–Ruelle inequality for random dynamical systems, Arch. Math. 64 (1995), 246-253.

[BG] T. Bogenschutz and V. M. Gundlach, Ruelle’s transfer operator for random subshifts of finite type, Ergod. Th.& Dynam. Sys. 15 (1995), 413-447.

[BL] J.Bahnmüller and P.-D. Liu, Characterization of measures satisfying Pesin’s entropy formula for random dynamical systems, J. Dynam. and Diff. Equat. 10 (1998).

[GK1] V. M. Gundlach and Y. Kifer, Random hyperbolic systems, Preprint, 1998.

[GK2] V. M. Gundlach and Y. Kifer, Random sofic shifts, Preprint, 1998.

[Ka] S. Kakutani, Random ergodic theorems and Markoff processes with a stable distribution, Proc. 2nd Berkeley Symp. on Math. Stat. and Probab., 1951, pp. 247-261.

[Ki1] Y. Kifer, Ergodic Theory of Random Transformations, Birkhäuser, Boston, 1986.

[Ki2] Y. Kifer, Equilibrium states for random expanding transformations, Random&Comp. Dynam. 1 (1992), 1-31.

[Ki3] Y.Kifer, Multidimensional random subshifts of finite type and their large deviations, Probab. Th. Rel. Fields 102 (1995), 223-248.

[Ki4] Y. Kifer, Fractal dimensions and random transformations, Trans. Amer. Math. Soc. 348 (1996), 2003-2038.

[Ki5] Y. Kifer, Large deviations for paths and configurations counting, Ergodic Theory of ℤ^{d}- Actions (M, Pollicott and K. Schmidt, eds.), London Math. Soc. Lecture Note Series, vol. 228, Cambridge University Press, Cambridge, 1996, pp. 415-432.

[Ki6] Y. Kifer, Limit theorems for random transformations and processes in random environments, Trans.Amer.Math.Soc. 350 (1998), 1481-1518.

[KK] K. Khanin and Y. Kifer, Thermodynamic formalism for random transformations and statistical mechanics, in: Sinai’s Moscow Seminar on Dynamical Systems (L.A.Bunimovich, B.M.Gurevich, Ya.B.Pesin, eds.), vol. 171, American Mathematical Society Translations–Series 2, 1996, pp. 107-140.

[Li] P.-D. Liu, Random perturbations of Axiom A basic sets, J. Stat. Phys. 90 (1998), 467-490.

[LQ] P.-D. Liu and M. Qian., Smooth Ergodic Theory of Random Dynamical Systems, Lecture Notes in Math., vol. 1606, Springer Verlag, Berlin, 1995.

[LW] F. Ledrappier and P. Walters, A relativized variational principle for continuous transformations, J. London Math. Soc. (2) 16 (1977), 568-576.

[LY] F. Ledrappier and L.-S. Young, Entropy formula for random transformations, Probab. Th. Rel. Fields 80 (1988), 217-240.

[Rub] B.-Z. Rubshtein, Convolutions of random measures on compact groups, J. of Theoret. Probab. 8 (1995), 523-538.

[Rue] D. Ruelle, Positivity of entropy production in the presence of a random thermostat, J. Stat. Phys. 86 (1997), 935-951.

[Th] J.-P. Thouvenot, Quelques proprietes des systemes dynamiques qui se decomposent en un produit de deux systemes dont l’un est un schema de Bernoulli, Isr. J. Math. 21 (1975), 177-207.

[UN] S.M. Ulam and J. von Neumann, Random ergodic theorems, Bull. Amer. Math. Soc. 51 (1945), 660.

Yuri Kifer

Institute of Mathematics,

Hebrew University of Jerusalem, Givat Ram, Jerusalem 91904, ISRAEL