Central Limit Theorem for Random “Contractive” Functions on Interval

Let (S, d) be a compact metric space, and let P : ℳ(S) → ℳ(S) be a Feller operator defined on finite Borel measures on this space.

Then P has at least one invariant probability measure, i.e., there exists a measure μ ∈ ℳ₁(S) such that for any A ∈ ℬ(S), PμA=μA. P\mu \left( A \right) = \mu \left( A \right).

Let ω→gωnn≥0 \omega \to {\left( {g_\omega ^n} \right)_{n \ge 0}} be a non-degenerate random walk generated by a subgroup G ⊂ Homeo([0, 1]), such that:

• (1)

  There is no non-trivial interval I ⊂ [0, 1] invariant under G.

• (2)

  There exists at least one probability measure μ on (0, 1) that is stationary for the random walk.

ginIx≤qn for every n∈ℕ. \left| {g_i^n\left( {{I_x}} \right)} \right| \le {q^n}\;\;\;for\;every\;n \in {\mathbb{N}}.

x∈infsupp μ,supsupp μ. x \in \left( {\inf \left( {{\rm{supp}}\;\mu } \right),\sup \left( {{\rm{supp}}\;\mu } \right)} \right).

Note that the theorem is also true on the interval [a, b].

There exists a q < 1 such that for every x ∈ (0, 1), there exists a neighborhood I_x of x, such that for ℙ almost all i ∈ Σ, the following holds: finIx≤qn for every n∈ℕ. \left| {f_i^n\left( {{I_x}} \right)} \right| \le {q^n}\;\;\;for\;every\;n \in {\mathbb{N}}.

Let g_i ∈ Homeo([−ε, 1 + ε]), such that for x ∈ [0, 1] we have g_i(x) = f_i(x). This family does not satisfy the first assumption of the previous theorem, because [0, 1] is invariant under G. We will prove that there exists a stationary measure for the random walk generated by G.

By Krylov–Bogoliubov’s theorem, we know that the Markov operator generated by the family (f₁, . . . , f_n, p₁, . . . , p_n) has an invariant measure μ. Let μ^∗ ∈ M([−ε, 1 + ε]) be defined by μ^∗(A) = μ(A ∩ [0, 1]). It is easy to verify that μ_∗ is an invariant measure for the operator P_G generated by G. We will show that μ^∗ is a stationary measure for the random walk generated by G. We need to show that for every measurable set A, the following holds: ∫−ε,1+επx,Adμ*x=μ*A. \int_{\left[ { - \varepsilon ,1 + \varepsilon } \right]} {\pi \left( {x,A} \right)d{\mu ^*}\left( x \right) = {\mu ^*}\left( A \right)} . However, ∫−ε,1+επx,Adμ*x=∫−ε,1+εPGδxAdμ*x=∑i=1npi∫−ε,1+εδxgi−1Adμ*x. \int_{\left[ { - \varepsilon ,1 + \varepsilon } \right]} {\pi \left( {x,A} \right)d{\mu ^*}\left( x \right)} = \int_{\left[ { - \varepsilon ,1 + \varepsilon } \right]} {{P_G}{\delta _x}\left( A \right)d{\mu ^*}\left( x \right)} = \sum\limits_{i = 1}^n {{p_i}} \int_{\left[ { - \varepsilon ,1 + \varepsilon } \right]} {{\delta _x}\left( {g_i^{ - 1}A} \right)d{\mu ^*}\left( x \right)} . But the last integral is μ*gi−1A {\mu ^*}\left( {g_i^{ - 1}A} \right) , so μ^∗ is a stationary measure. From the definition of μ^∗, it follows that supp(μ^∗) = supp(μ), and later in the work, we will prove that {0, 1} ∈ supp(μ), so by the previous theorem, the statement holds.

Every invariant measure of the operator P is atomless.

Suppose there exists an invariant measure μ^∗ for the operator P that has an atom. Let a ∈ (0, 1) be a point such that μ*a= supx∈0,1 μ*x. {\mu ^*}\left( {\left\{ a \right\}} \right) = \;{\rm{\;}}\mathop {{\rm{sup}}}\limits_{x \in \left( {0,1} \right)} {\rm{\;}}{\mu ^*}\left( {\left\{ x \right\}} \right). Then a is an atom of the measure μ^∗, which means that μ^∗({a}) > 0. Since μ^∗ is invariant under the operator P, we know that μ*a=∑i=1npiμ*fi−1a. {\mu ^*}\left( {\left\{ a \right\}} \right) = \sum\limits_{i = 1}^n {{p_i}{\mu ^*}\left( {\left\{ {f_i^{ - 1}\left( a \right)} \right\}} \right)} . For each function f_i, there is a point fi−1a f_i^{ - 1}\left( a \right) such that the measure μ^∗ assigns the same value μ({a}), because fi−1a f_i^{ - 1}\left(\{a\} \right) for i ∈ Σ^∗ forms an infinite set of points mapped to a. This means that for each i, we have μ*fi−1a=μ*a {\mu ^*}\left( {\left\{ {f_i^{ - 1}\left( a \right)} \right\}} \right) = {\mu ^*}\left( {\left\{ a \right\}} \right) , which suggests that μ({a}) should be split between infinitely many different points fi−1a f_i^{ - 1}\left( a \right) . However, this leads to a contradiction with the property that μ^∗ is a finite measure, as it would imply that μ^∗((0, 1)) = ∞, which is impossible. Thus, we arrive at a contradiction, and therefore the measure μ^∗ cannot have atoms. Hence, every invariant measure of the operator P is atomless.

Every invariant measure of the operator P contains the points 0 and 1 in its support.

Suppose that 0 ∉ supp(μ). Then, by the atomlessness of μ, there exists the largest a > 0 such that μ([0, a]) = 0. However, from the invariance of μ, we obtain: 0=μ0,a=∑i=1npiμfi−10,a. 0 = \mu \left( {\left[ {0,a} \right]} \right) = \sum\limits_{i = 1}^n {{p_i}\mu \left( {f_i^{ - 1}\left( {\left[ {0,a} \right]} \right)} \right)} . This implies that for every i, we have μfi−10,a=0 \mu \left( {f_i^{ - 1}\left( {\left[ {0,a} \right]} \right)} \right) = 0 . However, there exists some i for which f_i(a) < a, which implies that 0,a⊂fi−10,a \left[ {0,a} \right] \subset f_i^{ - 1}\left( {\left[ {0,a} \right]} \right) , contradicting the maximality of a. A similar proof can be conducted for 1.

Let S be a compact metric space. We say that a Feller operator P has the e-property at the point x ∈ S if for every Lipschitz function ϕ: S → ℝ, the following holds: limy→x supn∈ℕ Unϕx−Unϕy=0. \mathop {\lim }\limits_{y \to x} {\rm{\;}}\mathop {\sup }\limits_{n \in {\mathbb{N}}} {\rm{\;}}\left| {{U^n}\phi \left( x \right) - {U^n}\phi \left( y \right)} \right| = 0. If P has the e-property at every point, we say that P has the e-property.

Let P be a Feller operator that possesses the e-property. Then for any two distinct ergodic measures μ, ν ∈ M₁(S), the following holds: supp μ∩supp ν=∅. {\rm{supp}}\;\mu \cap {\rm{supp}}\;\nu = \emptyset {\rm{.}} In particular, from the proof of the lemma, it follows that if P has the e-property at x, then x ∉ supp μ ∩ supp ν.

There exists exactly one invariant measure for the Feller operator P.

We know that if μ is an invariant measure, then 0 ∈ supp μ. Therefore, we only need to check that the operator P has the e-property at 0. Let ε > 0 be given. We need to show that there exists a δ > 0 such that if h < δ, then for every n ≥ N₀, the following holds: ∑i∈Σnpifih−∑i∈Σnpifi0=∑i∈Σnpifi0,h<ε. \left| {\sum\limits_{i \in {\Sigma _n}} {{p_i}{f_i}\left( h \right)} - \sum\limits_{i \in {\Sigma _n}} {{p_i}{f_i}\left( 0 \right)} } \right| = \sum\limits_{i \in {\Sigma _n}} {{p_i}\left| {{f_i}\left( {\left[ {0,h} \right]} \right)} \right| < \varepsilon } . Let N₁ be large enough such that (1 − p_d)^N₁ < ε/3. Let Σn1=i∈Σn:fik≠fd for 1≤k≤N1 \Sigma _n^1 = \left\{ {i \in {\Sigma _n}:{f_{{i_k}}} \ne {f_d}\;{\rm{for}}\;1 \le k \le {N_1}} \right\} . Note that ℙnΣn1=(1−pd)N1 {\mathbb{P}_n}\left( {\Sigma _n^1} \right) = {(1 - {p_d})^{{N_1}}} . Let Σn2=i∈Σn:i|N1∉ΣN11 \Sigma _n^2 = \left\{ {i \in {\Sigma _n}:{i_{|{N_1}}} \notin \Sigma _{{N_1}}^1} \right\} . For i∈Σn2 i \in \Sigma _n^2 , let x_i = f_i(0). Since 0 < x_i < 1, there exists a neighborhood J_i such that for almost all j ∈ Σ, we have fjkJi<qk \left| {f_j^k\left( {{J_i}} \right)} \right| < {q^k} . Let Σ3=j∈Σ:for every i∈Σn2,fjkJi<qk {\Sigma ^3} = \left\{ {j \in \Sigma :{\rm{for}}\;{\rm{every}}\;i \in \Sigma _n^2,\left| {f_j^k\left( {{J_i}} \right)} \right| < {q^k}} \right\} . Clearly, ℙ(Σ³) = 1. Choose δ small enough such that for every i∈Σn2 i \in \Sigma _n^2 , we have f_i([0, δ]) ⊂ J_i. Let N₂ > N₁ be sufficiently large such that q^N₂−N₁ < ε/3. Let Σn4=j*=ij|n:i∈Σn2 and j∈Σ3 \Sigma _n^4 = \left\{ {{j^*} = {{\left( {ij} \right)}_{|n}}:i \in \Sigma _n^2\;{\rm{and}}\;j \in {\Sigma ^3}} \right\} and Σn5=j*=(ij)|n:i∈Σn2 and j∉Σ3 \Sigma _n^5 = \left\{ {{j^*} = {{(ij)}_{|n}}:i \in \Sigma _n^2\;{\rm{and}}\;j \notin {\Sigma ^3}} \right\} . Let N₃ > N₂ be sufficiently large such that ℙN3Σn5<ε/3 {\mathbb{P}_{{N_3}}}\left( {\Sigma _n^5} \right) < \varepsilon /3 . For n > N₃, the following holds: ∑i∈Σnpifi0,h=∑i∈Σn1pifi0,h+∑i∈Σn4pifi0,h+∑i∈Σn5pifi0,h≤∑i∈Σn1pi+∑i∈Σn4piqn−N1+∑i∈Σn5pi≤(1−pd)N1+qN2−N1+∑i∈Σn5pi≤ε. \begin{array}{*{20}{l}}{\sum\limits_{i \in {\Sigma _n}} {{p_i}\left| {{f_i}\left( {\left[ {0,h} \right]} \right)} \right|} }&{ = \sum\limits_{i \in \Sigma _n^1} {{p_i}\left| {{f_i}\left( {\left[ {0,h} \right]} \right)} \right|} + \sum\limits_{i \in \Sigma _n^4} {{p_i}\left| {{f_i}\left( {\left[ {0,h} \right]} \right)} \right|} + \sum\limits_{i \in \Sigma _n^5} {{p_i}\left| {{f_i}\left( {\left[ {0,h} \right]} \right)} \right|} }\\{}&{ \le \sum\limits_{i \in \Sigma _n^1} {{p_i}} + \sum\limits_{i \in \Sigma _n^4} {{p_i}{q^{n - {N_1}}}} + \sum\limits_{i \in \Sigma _n^5} {{p_i}} }\\{}&{ \le {{(1 - {p_d})}^{{N_1}}} + {q^{{N_2} - {N_1}}} + \sum\limits_{i \in \Sigma _n^5} {{p_i} \le \varepsilon } .}\end{array} Consequently, P has the e-property at 0, so if μ and ν are two distinct ergodic measures, then 0 ∉ supp μ∩supp ν and on the other hand, 0 ∈ supp μ∩supp ν – a contradiction, which completes the proof.

Let μ^∗ be the unique invariant measure of the operator P. Then every probabilistic measure μ converges weakly to μ^∗. For continuous functions ϕ, we have: limn→∞Pnμ,ϕ=μ*,ϕ. \mathop {\lim }\limits_{n \to \infty } \left\langle {{P^n}\mu ,\phi } \right\rangle = \left\langle {{\mu _*},\phi } \right\rangle .

For ψ ∈ C([0, 1]), define the sequence of random variables on (Σ, ℝ) by ξnψi=μ*,ψ∘fin,in−1,…,i1. \xi _n^\psi \left( i \right) = \left\langle {{\mu _*},\psi \circ {f_{\left( {{i_n},{i_{n - 1}}, \ldots ,{i_1}} \right)}}} \right\rangle . We will show that ξnψ \left( {\xi _n^\psi } \right) is a bounded martingale. The boundedness is obvious, so it is sufficient to show that 𝔼(ξn+1ψ|ξ1ψ,…,ξnψ)=ξnψ. {\mathbb{E}}(\xi _{n + 1}^\psi |\xi _1^\psi , \ldots ,\xi _n^\psi ) = \xi _n^\psi . Notice that U∈σξ1ψ,…,ξnψ U \in \sigma \left( {\xi _1^\psi , \ldots ,\xi _n^\psi } \right) has the form U_n × Σ₁ × Σ for some U_n ∈ Σ_n. We have: ∫U𝔼(ξn+1ψ|ξ1ψ,…,ξnψ)dℙ=∫Uξn+1ψdℙn+1=∑i∈Un+1piμ*,ψ∘fi=∑i∈Σ1piμ*,∑j∈Unpjψ∘fjfix=μ*,U∑j∈Unpjψ∘fj=μ*,∑j∈Unpjψ∘fj=∫Unξnψdℙn=∫Uξnψdℙ. \begin{array}{*{20}{l}}{\int_U {{\mathbb{E}}(\xi _{n + 1}^\psi |\xi _1^\psi , \ldots ,\xi _n^\psi )d\mathbb{P}} }&{ = \int_U {\xi _{n + 1}^\psi d{\mathbb{P}_{n + 1}}} = \sum\limits_{i \in {U_{n + 1}}} {{p_i}\left\langle {{\mu _*},\psi \circ {f_i}} \right\rangle } }\\{}&{ = \sum\limits_{i \in {\Sigma _1}} {{p_i}\left\langle {{\mu _*},\sum\limits_{j \in {U_n}} {{p_j}\psi \circ {f_j}\left( {{f_i}\left( x \right)} \right)} } \right\rangle } }\\{}&{ = \left\langle {{\mu _*},U\left( {\sum\limits_{j \in {U_n}} {{p_j}\psi \circ {f_j}} } \right)} \right\rangle = \left\langle {{\mu _*},\sum\limits_{j \in {U_n}} {{p_j}\psi \circ {f_j}} } \right\rangle }\\{}&{ = \int_{{U_n}} {\xi _n^\psi d{\mathbb{P}_n}} = \int_U {\xi _n^\psi d\mathbb{P}} .}\end{array} This completes this part of the proof. By the Martingale Convergence Theorem, we know that ξnψ \xi _n^\psi converges for almost every i ∈ Σ. The space of continuous functions on the interval is central, so there exists a set Σ₀ ⊂ Σ of full measure such that for every i ∈ Σ₀, the sequence ξnψ \xi _n^\psi converges. This follows from the fact that we can specify such a set for the center. From the Riesz Representation Theorem, we know that for i ∈ Σ₀, there exists a probabilistic measure μ_i such that (3.1) limn→∞ξnψi=μi,ψ. \mathop {\lim }\limits_{n \to \infty } \xi _n^\psi \left( i \right) = \left\langle {{\mu _i},\psi } \right\rangle . We will show that for almost every i, the measure μ_i = δ_v(i) for some v(i). It is sufficient to show that for ε > 0, there exists a set Σ_ε ⊂ Σ of full measure such that for each i ∈ Σ_ε, there exists an interval I of length less than ε such that μiI≥1−ε. {\mu _i}\left( I \right) \ge 1 - \varepsilon . Then for i∈Σ1=∩n=1∞Σ1/n i \in {\Sigma ^1} = \bigcap\nolimits_{n = 1}^\infty {{\Sigma _{1/n}}} , we have μ_i = δ_v(i). The set Σ¹ is a set of full measure. For a fixed ε > 0, choose a natural number l such that 1/l < ε. Let the interval [a, b] satisfy μ*a,b>1−ε {\mu _*}\left[ {a,b} \right] > 1 - \varepsilon and contain f_d(f_g(0)) and f_d(f_g(1)). We can specify j ∈ Σ such that f_jn(b) → 0. Notice that there exists an n₁ such that f_jn1 (b) < a. Let i₁ = j_n1. In general, for k ≤ l, there exists n_k such that fjnkb<fjnk−1a. {f_{{j_{{n_k}}}}}\left( b \right) < {f_{{j_{{n_{k - 1}}}}}}\left( a \right). Let i_k = j_nk. Notice that the intervals J_n = f_in[a, b] are disjoint. It follows that for some n^∗, we have Jn*<1/l<ε/2. \left| {{J_{{n^*}}}} \right| < 1/l < \varepsilon /2. Notice that Σ1=i∈Σ:for infinitely many n,fina,b<ε/2. {\Sigma ^1} = \left\{ {i \in \Sigma :{\rm{for}}\;{\rm{infinitely}}\;{\rm{many}}\;n,\left| {{f_{{i_n}}}\left[ {a,b} \right]} \right| < \varepsilon /2} \right\}. is a set of full measure. This is true because if i ∉ Σ¹, there exists N such that for n > N |f_in[a, b]| ≥ ε/2. However, with probability 1, the sequence σ^N i contains the fragment (i_d, i_g)i_n^∗. So with probability 1, there exists n′ > N such that |f_in′ [a, b]| < ε/2. By the compactness of the interval, it follows that for infinitely many n, the image f_in′ [a, b] ∈ I, where I is an interval of length ε. Notice that Σ¹ ⊂ Σ_ε, which completes this part of the proof.

To show the asymptotic stability, it is sufficient to show that for a Lipschitz function ψ and any points x, y ∈ (0, 1), the following holds: limn→∞Pnδx,ψ−Pnδy,ψ=0. \mathop {\lim }\limits_{n \to \infty } \left| {\left\langle {{P^n}{\delta _x},\psi } \right\rangle - \left\langle {{P^n}{\delta _y},\psi } \right\rangle } \right| = 0. This is true because for any measure μ ∈ M₁(0, 1), we have Pnμ,ψ−μ*,ψ≤∫0,1∫0,1Pnδx,ψ−Pnδy,ψμdxμ*dy. \left| {\left\langle {{P^n}\mu ,\psi } \right\rangle - \left\langle {{\mu _*},\psi } \right\rangle } \right| \le \int_{\left( {0,1} \right)} {\int_{\left( {0,1} \right)} {\left| {\left\langle {{P^n}{\delta _x},\psi } \right\rangle - \left\langle {{P^n}{\delta _y},\psi } \right\rangle } \right|\mu \left( {dx} \right){\mu _*}\left( {dy} \right).} } Let us fix points x and y belonging to the interval (0, 1), with x < y. Choose any ε > 0. Since the measure μ^∗ is invariant, according to the proof of uniqueness from Theorem 4.4, its support contains the points 0 and 1, which means that μ^∗((0, x)) > 0 and μ^∗((y, 1)) > 0. We know that for almost every sequence i = (i₁, i₂, . . . ) ∈ Σ with respect to the measure ℙ, the sequence of measures μ*∘fi1,i2,…,in−1vi−ε2,vi+ε2∩0,1→1 {\mu ^*} \circ f_{\left( {{i_1},{i_2}, \ldots ,{i_n}} \right)}^{ - 1}\left( {\left( {v\left( i \right) - \frac{\varepsilon }{2},v\left( i \right) + \frac{\varepsilon }{2}} \right) \cap \left( {0,1} \right)} \right) \to 1 as n → ∞. Since μ^∗((0, x)) > 0 and μ^∗((y, 1)) > 0, we can find points u_n ∈ (0, x) and v_n ∈ (y, 1) such that for sufficiently large n, we have un,vn∈fi1,i2,…,in−1vi−ε2,vi+ε2∩0,1 {u_n},{v_n} \in f_{\left( {{i_1},{i_2}, \ldots ,{i_n}} \right)}^{ - 1}\left( {\left( {v\left( i \right) - \frac{\varepsilon }{2},v\left( i \right) + \frac{\varepsilon }{2}} \right) \cap \left( {0,1} \right)} \right) . Then it follows that f_(i1,...,_in) (u_n) and f_(i1,...,_in) (v_n) lie in the interval vi−ε2,vi+ε2 \left( {v\left( i \right) - \frac{\varepsilon }{2},v\left( i \right) + \frac{\varepsilon }{2}} \right) , and in particular, for sufficiently large n, f_(i1,...,in) (x) and f_(i1,...,in) (y) lie in this interval. Since ε > 0 was arbitrary, we conclude that for almost every i = (i₁, i₂, . . . ) ∈ Σ with respect to ℙ, the following convergence holds: limn→∞fi1,…,inx−fi1,…,iny=0. \mathop {\lim }\limits_{n \to \infty } \left| {{f_{\left( {{i_1}, \ldots ,{i_n}} \right)}}\left( x \right) - {f_{\left( {{i_1}, \ldots ,{i_n}} \right)}}\left( y \right)} \right| = 0. By equation (3.1) and the fact that ⟨Pⁿδ_z, ϕ⟩ = Uⁿϕ(z) for z ∈ [0, 1], we have: (3.2) Pnδx,ϕ−Pnδy,ϕ=Unϕx−Unϕy≤L∑i1,…,in∈Σnfi1,…,inx−fi1,…,inypi1⋯pin, \left| {\left\langle {{P^n}{\delta _x},\phi } \right\rangle - \left\langle {{P^n}{\delta _y},\phi } \right\rangle } \right| = \left| {{U^n}{\phi _x} - {U^n}{\phi _y}} \right| \le L\sum\limits_{\left( {{i_1}, \ldots ,{i_n}} \right) \in {\Sigma _n}} {\left| {{f_{\left( {{i_1}, \ldots ,{i_n}} \right)}}\left( x \right) - {f_{\left( {{i_1}, \ldots ,{i_n}} \right)}}\left( y \right)} \right|} {p_{{i_1}}} \cdots {p_{{i_n}}}, where L is the Lipschitz constant for the function ϕ. We will analyze why the right-hand side of the above inequality tends to zero as n → ∞. For i = (i₁, . . . , i_n, . . . ), define g_n(i) := |f_in (x) − f_in (y)|, where i_n = (i₁, . . . , i_n). Then, g_n(i) → 0 as n → ∞ for almost every i ∈ Σ with respect to ℙ. From the construction of the probability measures ℙ and ℙⁿ for n ∈ ℕ, it follows that the following relationship holds ℙBn×Σ1×Σ1×…=ℙnBn for Bn∈Σn. \mathbb{P}\left( {{B_n} \times {\Sigma _1} \times {\Sigma _1} \times \ldots } \right) = {\mathbb{P}_n}\left( {{B_n}} \right)\;\;\;{\rm{for}}\;{B_n} \in {\Sigma _n}. Since g_n(i) depends solely on the first n coordinates, it follows that ∫Σgnidℙi=∫Σngnidℙni=∑i1,…,in∈Σnfi1,…,inx−fi1,…,inypi1⋯⋅⋅pin. \begin{array}{*{20}{l}}{\int_\Sigma {{g_n}\left( i \right)d\mathbb{P}\left( i \right)} }&{ = \int_{{\Sigma _n}} {{g_n}\left( i \right)d{\mathbb{P}_n}\left( i \right)} }\\{}&{ = \sum\limits_{\left( {{i_1}, \ldots ,{i_n}} \right) \in {\Sigma _n}} {\left| {{f_{\left( {{i_1}, \ldots ,{i_n}} \right)}}\left( x \right) - {f_{\left( {{i_1}, \ldots ,{i_n}} \right)}}\left( y \right)} \right|{p_{{i_1}}} \cdots \cdot \cdot {p_{{i_n}}}.} }\end{array} As a result, according to Lebesgue’s theorem, we have limn→∞∑i1,…,in∈Σnfi1,…,inx−fi1,…,inypi1⋯⋅⋅pin=0, \mathop {\lim }\limits_{n \to \infty } \sum\limits_{\left( {{i_1}, \ldots ,{i_n}} \right) \in {\Sigma ^n}} {\left| {{f_{\left( {{i_1}, \ldots ,{i_n}} \right)}}\left( x \right) - {f_{\left( {{i_1}, \ldots ,{i_n}} \right)}}\left( y \right)} \right|{p_{{i_1}}} \cdots \cdot \cdot {p_{{i_n}}} = 0} , which proves inequality (3.2) and thus completes the proof.

Let the family (f₁, . . . , f_N; p₁, . . . , p_N) be a contracting iterated function system, and let a∈0,12 a \in \left( {0,\frac{1}{2}} \right) . Then there exists r ∈ ℕ and Ω ⊆ Σ with probability ℙ(Ω) > 0 such that J = [a, 1 − a] and we get ∑n=1∞finJ≤r+q1−q \sum\limits_{n = 1}^\infty {\left| {f_i^n\left( J \right)} \right| \le r} + \frac{q}{{1 - q}} for every i ∈ Ω, where q is a constant given by Theorem 3.2.

Let J = [a, 1 − a] be such that f_d(f_g(0)), f_d(f_g(1)) ∈ J. Let En=i∈Σ:fin1/40,1∈J {E_n} = \left\{ {i \in \Sigma :f_i^{\lfloor {{n^{1/4}}} \rfloor }\left[ {0,1} \right] \in J} \right\} . Then, for n ≥ 16, there exists β = p_dp_g > 0 such that ℙ(E_n) ≥ β.

Let 𝒜 ⊂ Σ be a set such that ℙ(𝒜) ≥ β for some β > 0 and let k, n ∈ ℕ with k < n. Then, there exists a set A ⊂ Σ_n such that ℙ_n(Σ_n\A) ≤ (1 − β)^k and for any i ∈ A there exist i₁, i₂, . . . , i_k ∈ Σ_∗ such that i = i₁i₂ . . . i_k and for j = 1, . . . , k at least one of the sequences i_j, σi_j , . . . , σ^k−1i_j is dominated by A.

Let X_n be a stationary Markov chain generated by a random walk with the initial distribution given by μ_∗. If ϕ: [0, 1] → ℝ is a Lipschitz function such that ∫_[0,1] ϕdμ_∗ = 0, then the process ϕ(X_n) satisfies the central limit theorem. That is, σ2=limn→∞𝔼ϕX0+⋯+ϕXnn2 {\sigma ^2} = \mathop {\lim }\limits_{n \to \infty } {\mathbb{E}}{\left( {\frac{{\phi \left( {{X_0}} \right) + \cdots + \phi \left( {{X_n}} \right)}}{{\sqrt n }}} \right)^2} exists, and ϕX0+⋯+ϕXnn⇒𝒩0,σ as n→∞. \frac{{\phi \left( {{X_0}} \right) + \cdots + \phi \left( {{X_n}} \right)}}{{\sqrt n }} \Rightarrow {{\cal N}}\left( {0,\sigma } \right)\;\;\;as\;\;\;n \to \infty .

From the uniqueness of the ergodic measure μ_∗, we know that the chain is ergodic. Therefore, by Theorem 1 from [5], it is sufficient to show that ∑n=1∞n−3/2∑j=1nUjϕL2<∞. \sum\limits_{n = 1}^\infty {{n^{ - 3/2}}} {\left\| {\sum\limits_{j = 1}^n {{U^j}\phi } } \right\|_{{L^2}}} < \infty . Let E_n be as in Lemma 4.2. Clearly, ℙ(E_n) ≥ β > 0. Let Ω be as in Lemma 4.1. Let A=ij|n:i∈Enn1/4,j∈Ω. \mathcal{A} = \left\{ {i{j_{|n}}:i \in E_n^{\lfloor {{n^{1/4}}} \rfloor },j \in \Omega } \right\}. Clearly, ℙ(𝒜) ≥ α > 0 for some α (independent of n). Then, by Lemma 4.3, for k = ⌊n^1/8⌋, we get a sequence A_n ∈ Σ_n satisfying ℙ(B_n = Σ_n/A_n) ≤ (1 − α)^⌊n1/8⌋. Moreover, if i ∈ A_n, then i = i₁ . . . i_k, where at least one of i_m, σi_m, . . . , σ^k−1i_m is dominated by 𝒜. Therefore, for any x, y, we have: ∑j=1imfijx−fijy≤n1/8+n1/4+r+q1−q≤2n1/4+c. \sum\limits_{j = 1}^{\left| {{i_m}} \right|} {\left| {f_i^j\left( x \right) - f_i^j\left( y \right)} \right|} \le \lfloor {{n^{1/8}}} \rfloor + \lfloor {{n^{1/4}}} \rfloor + r + \frac{q}{{1 - q}} \le 2\left( {\lfloor {{n^{1/4}}} \rfloor + c} \right). Notice that ∑j=1nfijx−fijy≤2kn1/4+c≤Cn3/4. \sum\limits_{j = 1}^n {\left| {f_i^j\left( x \right) - f_i^j\left( y \right)} \right|} \le 2k\left( {\lfloor {{n^{1/4}}} \rfloor + c} \right) \le C\lfloor {{n^{3/4}}} \rfloor . Let L be the Lipschitz constant of the function ϕ. Since ∫0,1ϕdμ*=∫0,1Ujϕdμ*=0, \int_{\left[ {0,1} \right]} {\phi d{\mu _*} = } \int_{\left[ {0,1} \right]} {{U^j}} \phi d{\mu _*} = 0, we have: ∫0,1∑j=1nUjϕx2dμ*x≤∫0,1∫0,1∑j=1nUjϕx−Ujϕy2dμ*xμ*y. {\int_{\left[ {0,1} \right]} {\left| {\sum\limits_{j = 1}^n {{U^j}\phi \left( x \right)} } \right|} ^2}d{\mu _*}\left( x \right) \le \int_{\left[ {0,1} \right]} {\int_{\left[ {0,1} \right]} {{{\left( {\sum\limits_{j = 1}^n {\left| {{U^j}\phi \left( x \right) - {U^j}\phi \left( y \right)} \right|} } \right)}^2}d{\mu _*}\left( x \right){\mu _*}\left( y \right)} } . We know that ∑j=1nUjϕx−Ujϕy≤∫An∑j=1nfijϕx−fijϕydℙi + ∫Bn∑j=1nfijϕx−fijϕydℙi≤LCn3/8+2nLℙBn≤C*n3/8. \begin{array}{*{20}{l}}{\sum\limits_{j = 1}^n {\left| {{U^j}\phi \left( x \right) - {U^j}\phi \left( y \right)} \right|} }&{ \le \int_{{A_n}} {\sum\limits_{j = 1}^n {\left| {f_i^j\phi \left( x \right) - f_i^j\phi \left( y \right)} \right|d\mathbb{P}\left( i \right)} } }\\{}&{\;\;\; + \;\int_{{B_n}} {\sum\limits_{j = 1}^n {\left| {f_i^j\phi \left( x \right) - f_i^j\phi \left( y \right)} \right|d\mathbb{P}\left( i \right)} } }\\{}&{ \le LC{n^{3/8}} + 2nL\mathbb{P}\left( {{B_n}} \right) \le {C_*}{n^{3/8}}.}\end{array} This implies that ∫0,1∫0,1∑j=1nUjϕx−Ujϕy2dμ*xμ*y≤C*2n3/4. \int_{\left[ {0,1} \right]} {\int_{\left[ {0,1} \right]} {{{\left( {\sum\limits_{j = 1}^n {\left| {{U^j}\phi \left( x \right) - {U^j}\phi \left( y \right)} \right|} } \right)}^2}d{\mu _*}\left( x \right){\mu _*}\left( y \right) \le C_*^2{n^{3/4}}} } . Therefore, ∑j=1nUjϕL2<C*n3/8 {\left\| {\sum\nolimits_{j = 1}^n {{U^j}\phi } } \right\|_{{L^2}}} < C^*{n^{3/8}} . By Theorem 1 from [5], we obtain the result.