VMSTA Modern Stochastics: Theory and Applications 2351-6054 2351-6046 2351-6046 VTeXMokslininkų g. 2A, 08412 Vilnius, Lithuania VMSTA86 10.15559/17-VMSTA86 Research Article Random iterations of homeomorphisms on the circle GelfertKatringelfert@im.ufrj.bra1 StenfloÖrjanstenflo@math.uu.seb1∗ Institute of Mathematics, Federal University of Rio de Janeiro, 22.453 Rio de Janeiro RJ, Brazil Department of Mathematics, Uppsala University, Box 480, 75106 Uppsala, Sweden Corresponding author.

KG has been supported, in part, by CNPq research grant 302880/2015-1 (Brazil). KG and ÖS thank ICERM (USA) for their hospitality and financial support.

 2017 510201743253271 2232017 2592017 2592017 © 2017 The Author(s). Published by VTeX2017 Open access article under the CC BY license.

We study random independent and identically distributed iterations of functions from an iterated function system of homeomorphisms on the circle which is minimal. We show how such systems can be analyzed in terms of iterated function systems with probabilities which are non-expansive on average.

 Markov chains stationary distributions minimal iterated function systems circle homeomorphisms synchronization random dynamical systems 37E10 37Hxx 60B10 60J05 60G57

Dedicated to Professor Dmitrii S. Silvestrov on the occasion of his 70th Birthday

 Introduction

We study iterations of a finite family of circle homeomorphisms. This topic has been studied already from a number of different points of view. One may, for example, take a purely deterministic approach and study the associated action of the group of circle homeomorphisms (the special case of the group of orientation preserving circle diffeomorphisms is treated in [12, 19, 13]). Or one may, as we will, take a probabilistic approach and investigate Markov chains generated by random independent and identically distributed (i.i.d.) iterations of functions from the family (such as in [16, 8, 21]).

We restrict our attention to families of functions which are forward minimal in the sense that for any two points on the circle, there are orbits from the first point arbitrary close to the second one using some concatenations of functions from the family. The set of distances which are preserved simultaneously by all maps allows us to distinguish between distinct types of ergodic behavior for such Markov chains.

By finding a topologically conjugate system which is non-expansive on average, under the additional assumption that the system of inverse maps is forward minimal, we prove limit theorems including almost sure synchronization of random trajectories (which is sometimes also referred to as Antonov’s theorem [1]) provided that the system is not topologically conjugate to a family containing only isometries, and uniqueness and fiberwise properties of stationary distributions.

In contrast to many previous authors we do not assume that all maps preserve orientation or, a priori, that the system of inverse maps is forward minimal (such as in [1, 12, 14, 19, 13, 21]) or contains at least one map which is minimal (as in [21]). Our setting is also studied in [17] (without any minimality condition), where a different approach is used and ideas of [3] are adapted which in turn are built on ideas of [15, 8]. See also [22]. One further precursor in a more specific setting is the work by Furstenberg [10] where the homeomorphisms are the projective actions of elements of SL2(R) .

 Random iterations

Let K be a compact topological space equipped with its Borel sets. We call a finite set F={f1,…,fN} of continuous functions fj:K→K , j=1,…,N , an iterated function system (IFS). If all maps fj are homeomorphisms, as we will in general assume here, then we also consider the associate IFS F−1:={f1−1,…,fN−1} of the inverse maps.

We will discuss different points of view on random and deterministic iterations of functions from an IFS and recall some standard notations and facts.

Given (In)n≥1 a stochastic sequence with values in {1,…,N} , for x∈K define Znx:=(fIn∘⋯∘fI1)(x),Z0x=x. We may consider without loss of generality the (a priori) unspecified common domain of the random variables In as Σ={1,…,N}N , equipped with a probability measure P defined on its Borel subsets, with In being defined as In(ω)=ωn for every ω=(ω1ω2…)∈Σ and n≥1 .

We will later also consider the shift map σ:Σ→Σ defined by σ(ω1ω2…):=(ω2ω3…) .

For any ω=(ω1ω2…)∈Σ , any n≥0 and any x∈K we thus define Znx(ω)=Zn(x,ω) , where Zn(x,ω):=(fωn∘⋯∘fω1)(x),Z0(x,ω)=x.

The sequence (Zn(x,ω))n≥0 is called the trajectory corresponding to the realization ω of the random process (Znx)n≥0 starting at x∈K . It is common to also consider iterates in the reversed order and to define Zˆn(x,ω):=(fω1∘⋯∘fωn)(x),Zˆ0(x,ω)=x. If F is an IFS of homeomorphisms, then we also consider the associate sequence (Zn−(x,ω))n≥0 defined by Zn−(x,ω):=(fωn−1∘⋯∘fω1−1)(x),Z0−(x,ω)=x, and the sequence (Zˆn−(x,ω))n≥1 defined by Zˆn−(x,ω):=(fω1−1∘⋯∘fωn−1)(x),Zˆ0−(x,ω)=x. Note that for every ω∈Σ and x∈K it holds Zˆn−(x,ω)=(fωn∘⋯∘fω1)−1(x)andZˆn(x,ω)=(fωn−1∘⋯∘fω1−1)−1(x).

Iterated function systems with probabilities and Markov chains

Let (In)n≥1 be i.i.d. variables. The probability measure P is then a Bernoulli measure determined by a probability vector p=(p1,…,pN) . It then follows that Znx=Zn(x,·) defined in (1) and Zˆnx=Zˆn(x,·) defined in (2) both have the same distribution for any fixed n≥1 , and (Znx)n≥0 is a (time-homogeneous) Markov chain with transfer operator T defined for bounded measurable functions h:K→R by Th(x):= ∑j=1Npjh(fj(x)).

If p is non-degenerate, that is, if pj>0 0$]]> for every j=1,…,N , then we call the pair (F,p) an IFS with probabilities. The Markov chain (Znx)n≥0 is obtained by independent random iterations where in each iteration step the functions fj are chosen with probability pj .

Markov chains generated by IFSs with probabilities is a particular class of Markov chains that has received a considerable attention in recent years. The IFS terminology was coined by Barnsley and Demko [4].2

A common abuse of notation is to use the term “IFS” for the Markov chain (Znx)n≥0 obtained from an IFS with probabilities. We here stress the deterministic nature of an IFS and the fact that an IFS can be used to build other objects like e.g.  (Zˆn(x,ω))n≥0 . A common way to construct fractal sets is for example to regard them as sets of limit points for the latter sequence (assuming conditions such as, for example, contractivity ensuring the limit to exist).

A Borel probability measure μ on K is an invariant probability measure for the IFS with probabilities (F,p) if T∗μ=μ,whereT∗μ(·)=∑jpjμ(fj−1(·)). Such a measure μ is also called a stationary distribution for the corresponding Markov chain, since if X is a μ-distributed random variable, independent of (In)n≥0 then (ZnX)n≥0 will be a stationary stochastic sequence.

By continuity of all functions fj , j=1,…,N , it follows that (Znx)n≥0 has the weak Feller property, that is, T maps the space of real valued continuous functions on K to itself. It is well known that Markov chains with the weak Feller property have at least one stationary distribution, see for example [18]. Hence, any IFS with probabilities (F,p) has at least one invariant probability measure.

Another formalism (which will not be used here) for analyzing stochastic sequences related to an IFS with probabilities is the one of a (deterministic) step skew product map (ω,x)↦(σ(ω),fω1(x)) with the shift map σ:Σ→Σ in the base and locally constant fiber maps. The Bernoulli measure is a σ-invariant measure in the base. Invariant measures (and hence stationary distributions) are closely related to measures which are invariant for the step skew product (see, for example, [23, Chapter 5]).

Given a positive integer n, define by Tn=T∘⋯∘T and T∗n=T∗∘⋯∘T∗ (each n times) the concatenations of T and T∗ , respectively. We call a stationary distribution μ for (Znx)n≥0 attractive if for any x∈K we have T∗nδx→μ as n→∞ in the weak∗ topology, where δx denotes the Dirac measure concentrated in x∈K . In other words, for any continuous h:K→R and for any x∈K we have limn→∞Tnh(x)=∫hdμ. An attractive stationary distribution is uniquely stationary.

Let ρ be some metric on K. We say that an IFS with probabilities (F,p) is contractive on average with respect to ρ if for any x,y∈S1 we have ∑j=1Npjρ(fj(x),fj(y))≤cρ(x,y), for some constant c<1 and non-expansive on average if (6) holds for some constant c≤1 .

It is well known that a Markov chain (Znx)n≥0 generated by an IFS with probabilities (F,p) which is contractive on average has an attractive (and hence unique) stationary distribution. More generally the distribution of Znx then converges (in the weak∗ topology) to the stationary distribution with an exponential rate that can be quantified for example by the Wasserstein metric, see e.g. [20].

Far less is known for non-expansive systems. The theory for Markov chains generated by non-expansive systems can be regarded as belonging to the realm of Markov chains where {Tnh} is equicontinuous for any continuous h:K→R , or “stochastically stable” Markov chains (see [18] for a survey).

The Markov chain (Znx)n≥0 is topologically recurrent if for any open set O⊂K and any x∈K we have P(Znx∈O for some n)>0. 0.\]]]>

In the present paper we are going to study a special class of topologically recurrent Feller continuous Markov chains generated by IFSs with probabilities of homeomorphisms on the circle. The topology of the circle and the hence implied monotonicity of the maps play a crucial role for our results.

 IFSs with homeomorphisms on the circle

From now on we will always assume K=S1=R/Z to be the unit circle and consider an IFS F={fj}j=1N of homeomorphisms fj:S1→S1 . Let d(x,y):=min{|y−x|,1−|y−x|} be the standard metric on S1 .

Deterministic iterations and simultaneously preserved distances

An IFS F={fj}j=1N is forward minimal if for any open set O⊂K and any x∈K there exist some n≥0 and some ω∈Σ such that Zn(x,ω)∈O. In other words, for a forward minimal IFS it is possible to go from any point x arbitrarily close to any point y by applying some concatenations of functions in the IFS. We say that the IFS F={fj}j=1N of homeomorphisms fj is backward minimal if the IFS {fj−1}j=1N is forward minimal.

Note that F is forward (backward) minimal if and only if for every nonempty closed set A⊂S1 satisfying fj(A)⊂A ( fj−1(A)⊂A ) for every j we have A=S1 .

Note that not every forward minimal IFS is automatically backward minimal if N>1 1$]]> (see [5] for a discussion and counterexamples). By [5, Corollary E], an IFS is both forward and backward minimal if and only if there exists an ω∈Ω such that (Zn(x,ω))n≥0 is dense, for any x∈S1 . (By forward minimality this property trivially holds for some fixed x∈S1 , but the choice of ω might depend on x∈S1 .) A simple sufficient condition for an IFS of circle homeomorphisms to be both forward and backward minimal is that at least one of the maps has a dense orbit. A class of IFSs which are forward and backward minimal (so-called expanding-contracting blenders) but without a map with a dense orbit can be found in [9, Section 8.1].

The following is somehow related to the study of the well-known concept of rotation numbers of orientation-preserving circle homeomorphisms which was introduced by Poincaré and which provides an invariant to (almost completely) characterize topologically conjugacy.3

The rotation number r(f) of a circle homeomorfism f is rational if, and only if, f has a periodic orbit. If r(f) is irrational then f is semi-conjugate to a rotation by angle r(f) and, in particular, this semi-conjugacy is a conjugacy if f is minimal.

Rotation numbers are also important when studying an IFS (which can be considered as a special group action) of orientation-preserving circle homeomorphisms. The surveys [12, 19] review these facts, see also [13].

Here we deal with a more general class of IFSs in which not necessarily all maps preserve orientation.

Given F and a metric ρ on S1 , let L=L(F,ρ) defined by L:={s∈[0,1/2]:ρ(x,y)=simplies thatρ(fj(x),fj(y))=s for any j=1,…,N and (x,y)∈S1×S1} be the set of ρ-distances which simultaneously are preserved by all maps in F.

Note that since all maps of the IFS are homeomorphisms it follows that for every x,y∈S1 with ρ(x,y)∈L(F,ρ) we have ρ(x,y)=ρ(fj(x),fj(y))=ρ(fj−1(x),fj−1(y))for allj=1,…,N, and thus L(F,ρ)=L(F−1,ρ) . Moreover, note that by continuity of the maps of the IFS, the set L is closed.

We have the following dichotomy.

If L=L(F,ρ) is finite, then L={0,1k,2k,…,⌊k/2⌋k}, for some k≥1 .

If L=L(F,ρ) is infinite, then L=[0,1/2] . All IFS maps are then isometries (with respect to ρ).

Consider the operation ⊕:L×L→S1 defined by s1⊕s2:=min{s1+s2,1−s1−s2}. Note that L is closed under this operation, that is, ⊕:(L×L)→L . Indeed, given s1,s2∈L , if x,z∈S1 are such that ρ(x,z)=s1⊕s2 , then there is a point y∈S1 such that ρ(x,y)=s1 and ρ(y,z)=s2 . Thus, we have ρ(fj(x),fj(y))=s1 and ρ(fj(y),fj(z))=s2 for every j=1,…,N . Since all maps fj are homeomorphisms, it follows that ρ(x,z)=ρ(fj(x),fj(z)) for all j=1,…,N and hence s1⊕s2∈L .

It follows that if L is finite (and nontrivial) then the smallest positive element of L must be a rational number of the form 1/k for some integer k>1 1$]]> and hence L must have the given form.

If L is infinite, then L=[0,1/2] , since L has then arbitrary small positive elements and must therefore be a dense, and by continuity of all maps in F, also a closed subset of [0,1/2] . All IFS maps are then isometries.  □

If L(F,d) is finite and 1/k is its smallest positive element, then the IFS F˜={f˜j} with maps f˜j(x)=k(fj(x/k)mod 1/k) , j=1,…,N , satisfies L(F˜,d)={0} . Thus, we can describe the dynamical properties of an IFS with the set of preserved distances L(F,d) being finite in terms of the dynamics of an IFS with no positive preserved distances. Observe that each of the maps fj is semiconjugate with f˜j by means of the map π:S1→S1 defined by π(x)=kxmod1 , that is, we have π∘fj=f˜j∘π .

Intuitively we may in all cases regard the infimum of all positive elements of L=L(F,d) as the “common prime period” of all maps, where the case when L is infinite corresponds to a degenerated case. As mentioned above, for orientation-preserving homeomorphisms this number can be compared with the rotation number functions in [12, 19, 13].

 Random iterations

First, recall the following well-known fact about forward minimal IFSs with probabilities on S1 (compare also [19, Lemma 2.3.14]). We say that a measure μ has full support if the support of μ is S1 .

Let (F,p) be an IFS with probabilities of homeomorphisms on S1 and μ+ be an invariant probability measure for (F,p) . If F is forward minimal then μ+ is nonatomic and has full support.

By contradiction, suppose that μ+ is atomic. Let x∈S1 be a point of maximal positive μ+ -mass. By invariance of μ+ , we obtain μ+({x})= ∑j=1Npjμ+({fj−1(x)}) and hence, since we assume that p is non-degenerate, we have μ+({fj−1(x)})=μ+({x}) for every j. Hence, we obtain that the (nonempty) set A:={y∈S1:μ+({y})=μ+({x})} satisfies fj−1(A)⊂A for every j. Since μ+ is finite, A is finite (and, in particular, closed). Hence, since every fj−1 is bijective, we in fact have fj−1(A)=A and fj(A)=A for every j. Assuming that F is either backward minimal or forward minimal, we hence obtain A=S1 , which is a contradiction. Hence μ+ is nonatomic.

An analogous argument shows that μ+ has full support. Indeed, let the (closed) set A=suppμ+ denote the support of μ+ . By invariance of μ+ , for every j we have μ+(fj−1(A))=μ+(A)=1 which implies A⊂fj−1(A) , i.e.  fj(A)⊂A for every j, so if (F,p) is forward minimal, then μ+ has full support.  □

We say that a probability measure μ on S1 is s-invariant for s∈[0,1] if (Rs)∗μ=μ , where Rs(x)=(x+s) mod 1 . Analogously, we say that an S1 -valued random variable X is s-invariant if its distribution is s-invariant, in which case X and Rs(X) have the same distribution.

Let (F,p) be an IFS with probabilities of homeomorphisms on S1 which is forward minimal. Then any invariant probability measure for (F,p) is s-invariant for any s∈L(F,d) .

Let μ be an invariant probability measure for (F,p) . Let s∈L(F,d) . Consider an arbitrary interval I of length s satisfying μ(I)≥μ(I′) for all other intervals I′ of length s. By invariance of μ we have μ(I)=∑jpjμ(fj−1(I)) . Hence, since p is non-degenerate, it follows that μ(I)=μ(fj−1(I)) for every j.

Since I is of length s∈L(F,d)=L(F−1,d) , the interval fj−1(I) is also of length s for any j. More generally, the μ-measure of the image of I under arbitrary finite concatenations of functions from F−1 is an interval of length s and of measure μ(I) . By forward minimality and continuity of the maps in F it therefore follows that all intervals of length s have the same μ-measure equal to μ(I) .

This property implies that μ is s-invariant. Indeed, consider an arbitrary interval (c,d) in S1 , where d=Rα(c) , for some 0<α≤1/2 . If α is larger than s then μ((c,d))=μ((c,Rs(c)))+μ((Rs(c),d))=μ((d,Rs(d)))+μ((Rs(c),d))=μ((Rs(c),Rs(d))). Otherwise, if α is smaller than or equal to s, then μ((c,d))+μ((d,Rs(c)))=μ((c,Rs(c)))=μ(I)=μ((d,Rs(d)))=μ((d,Rs(c)))+μ((Rs(c),Rs(d))), which also implies μ((c,d))=μ((Rs(c),Rs(d)) .  □

Given a measurable transformation Φ:S1→S1 and a probability measure μ, we denote by Φ∗μ the pushforward of μ defined by Φ∗μ(E)=μ(Φ−1(E)) for each Borel set E of S1 .

Recall that if μ is nonatomic (i.e. continuous) and fully supported Borel measure on S1 then its distribution function defines a homeomorphism Φ:S1→S1 and Φ∗−1μ=μLeb .

We state a preliminary result.4

The main idea is well known (see, for example, [16, p. 118] and [13], where the authors also consider a measurable bijection analogous to the here defined conjugation map Φ− ).

Let (F,p) be an IFS with probabilities of homeomorphisms on S1 which is backward minimal. Let μ− be an invariant measure for (F−1,p) and let Φ−:S1→S1 be defined by Φ−(x):=μ−([0,x]) . Then ρ(x,y):=min{μ−([x,y]),μ−([y,x])} is a metric on S1 and (F,p) is non-expansive on average with respect to ρ.

The IFS G={gj}j=1N given by the maps gj:=Φ−∘fj∘Φ−−1 , j=1,…,N , with probabilities p is non-expansive on average with respect to d and we have L(G,d)=L(F,ρ) .

Let (F,p) be an IFS with probabilities of homeomorphisms on S1 which is backward minimal. Let Φ−(x)=μ−([0,x]) , where μ− is an invariant probability measure for (F−1,p) , and define ρ(x,y):=min{μ−([x,y]),μ−([y,x])}. Clearly, L(G,d)=L(F,ρ) . By Lemma 2 applied to (F−1,p) , μ− is nonatomic and has full support and hence we have ρ(x,y)≥0 and ρ(x,y)=0 if and only if x=y . Moreover, clearly ρ(x,y)=ρ(y,x) and ρ(x,y)≤ρ(x,z)+ρ(z,y) . Hence, ρ defines a metric on S1 . The definition of ρ and the invariance of μ− together imply ∑j=1Npjρ(fj(x),fj(y))= ∑j=1Npjmin{μ−([fj(x),fj(y)]),μ−([fj(y),fj(x)])}= ∑j=1Npjmin{μ−(fj([x,y])),μ−(fj([y,x]))}≤min{ ∑j=1Npjμ−(fj([x,y])), ∑j=1Npjμ−(fj([y,x]))}=min{μ−([x,y]),μ−([y,x)])}=ρ(x,y), which proves that (F,p) is non-expansive on average with respect to ρ.  □

The following result can be regarded as the heart of the paper.5

A similar statement (without proof and stated for systems where all homeomorphisms preserve orientation) can be found for example in [13].

Let (F,p) be an IFS with probabilities of homeomorphisms on S1 which is forward minimal and non-expansive on average with respect to some metric ρ. Then ρ(Znx,Zny) converges almost surely to an L-valued random variable for any x,y∈S1 , where L=L(F,ρ) .

As an immediate corollary of Proposition 1 and Theorem 1 we get the following result. This type of result is usually referred to as Antonov’s theorem (see [2], where all maps in the IFS are assumed to preserve orientation, see also [13, 14]). Also in our generality, the present corollary is not new and follows (although not explicitly stated) from results by Malicet [17] who studied an even more general setting ( without assuming minimality).

Let (F,p) be an IFS with probabilities of homeomorphisms on S1 which is forward and backward minimal. Then exactly one of the following cases occurs:

(synchronization) For any x,y∈S1 and almost every ω∈Σ we have d(Zn(x,ω),Zn(y,ω))→0 as n→∞ .

(factorization) There exists a positive integer k≥2 and a homeomorphism Ψ:S1→S1 of order k (that is, Ψk=id ) which commutes with all fj . Moreover, there is a naturally associated IFS Fˇ={fˇj} where each map fˇj is a topological factor6

We call a map g:S1→S1 a topological factor of f:S1→S1 if there exists a continuous surjective map π:S1→S1 such that π∘f=g∘π .

(with a common factoring map) of the corresponding map fj of F such that (Fˇ,p) has the synchronization property claimed in item 1).

(invariance) All maps fj are conjugate (with a common conjugation map) to an isometry (with respect to d). There exists a probability measure which is invariant for all maps fj , j=1,…,N , and hence also uniquely invariant for (F,p) .

Apply Proposition 1 to (F,p) and consider the homeomorphism Φ−:S1→S1 , and the metric ρ such that (F,p) is non-expansive on average with respect to ρ. Consider the IFS (G,p) , conjugate to (F,p) through the conjugating map Φ− , which is non-expansive on average with respect to d and recall L=L(F,ρ)=L(G,d) . We consider three cases:

Case L={0} . By Theorem 1, we have ρ(Znx,Zny)→0 a.s. and thus d(Znx,Zny)→0 a.s., proving item 1).

Case L finite and nontrivial. By Lemma 1, L(G,d)={0,1/k,…,⌊k/2⌋/k} for some k≥2 . By Remark 6 applied to (G,d) , with fˇj(x)=g˜j(x):=k(gj(x/k)mod1/k) we have fˇj∘Ψ=Ψ∘fj , where Ψ=π∘Φ−−1 with π(x)=kxmod1 , and the IFS (Fˇ,p) satisfies L(Fˇ,d)=L(G˜,d)={0} .

Since by Lemma 3 we have Φ−−1(R1/k(x))=(Φ−−1(x)+1/k)mod1 , it follows that Ψ(R1/k(x))=(π∘Φ−−1)(R1/k(x))=π((Φ−−1(x)+1/k)mod1)=(π∘Φ−−1)(x)=Ψ(x), and thus Ψ is an order k homeomorphism having the claimed properties, proving item 2).

Case L infinite. By Lemma 1, we have L(G,d)=[0,1/2] . All maps in G are thus isometries (with respect to d) and hence simultaneously preserve the Lebesgue measure. The measure μ+:=(Φ−−1)∗μLeb is invariant for all maps of F, and by Lemma 3 uniquely invariant for (F,p) , proving item 3).  □

IFSs with nontrivial L can be regarded as degenerated systems. For a typical system satisfying the conditions of Theorem 1 we thus have that ρ(Znx,Zny)→0 as n→∞ a.s. for any x,y∈S1 . Using techniques from [17, Theorem D] it seems plausible that it should be possible to prove that convergence is exponential (see also [16]), and that (F,p) is contractive on average with respect to some metric in this case.

Let (F,p) be a forward minimal IFS which is non-expansive on average with respect to ρ. Let Fn be the sigma field generated by I1,…,In . Fix x,y∈S1 . Note that Znx and Zny are both measurable with respect to Fn and E(ρ(Zn+1x,Zn+1y)|Fn)=E(ρ(fIn+1(Znx),fIn+1(Zny))|Fn)= ∑j=1Npjρ(fj(Znx),fj(Zny))≤ρ(Znx,Zny), so the stochastic sequence (ρ(Znx,Zny))n≥0 is a bounded super-martingale with respect to the filtration {Fn} . By the Martingale convergence theorem it follows that ρ(Znx,Zny)→a.s.ξ as n→∞ for some random variable ξ=ξx,y .

Let L=L(F,ρ) . We will now show that ξ is L-valued a.s., that is, we will show that the distance between any two points a,b∈S1 with ρ(a,b)=ξ(ω) is preserved by all the maps in F for P a.a. ω∈Σ .

We will show that any two points a,b∈S1 with ρ(a,b)=ξ(ω) can simultaneously be (almost) reached by {Zn(x,ω),Zn(y,ω)} followed by an application of an arbitrary map for infinitely many n and that this leads to a contradiction if the distance between some points with distance ξ(ω) is not preserved by all maps in F for a typical ω.

Let us first prove the following claim that for any z and any index j, any open set in S1 will be visited followed by an application of the map fj infinitely many times by trajectories (Zn(z,ω))n≥0 corresponding to typical realizations ω.

For any z∈S1 and any open set O⊂S1 and any j∈{1,…,N} we have P(Ω)=1,where Ω:= ⋂m=1∞ ⋃n=m∞{ω:Zn(z,ω)∈O,ωn+1=j}.

Let z∈S1 . Consider an open set O⊂S1 and an index j∈{1,…,N} . By forward minimality, for every q∈S1 there exists some positive integer nq and some cq>0 0$]]>, such that P(Znqq∈O,Inq+1=j)=P(Znqq∈O)P(Inq+1=j)>cq>0. c_{q}>0.\]]]> Considering the left hand side expression in (8) as a function of q, by continuity (recall the weak Feller property) one concludes that there exists an open set Oq containing q and some positive integer nq and some cq′>0 0$]]> P(Znqz∈O,Inq+1=j)>cq′>0 {c^{\prime }_{q}}>0\]]]> for any z∈Oq . Thus, by compactness, there exists a positive integer N such that infq∈S1P(Znq∈O,In+1=j for some n<N)=:s>0. 0.\]]]>

Let Am:={ω:Zn(z,ω)∈O,ωn+1=j, for some n∈{mN,…,(m+1)N−1}}={ω:Zn−mN(ZmN(z,ω),σmN(ω))∈O,ωn+1=j,={ω:Zn(z,ω)∈O,ωn+1=j, for some n∈{mN,…,(m+1)N−1}}. For any m≥1 we have P(Am)≥infq∈S1P({ω:Zn−mN(q,σmN(ω))∈O,ωn+1=j,={ω:Zn(z,ω)∈O,ωn+1=j, for some n∈{mN,…,(m+1)N−1}})=infq∈S1P(Znq∈O,In+1=j for some n<N)=s>0 0\end{array}\]]]> and hence P(Amc)≤1−s . More generally, we can similarly show that P( ⋂m=jkAmc)≤(1−s)k−j, for any j<k , which implies P( ⋂j=1∞ ⋃m=j∞Am)=1−P( ⋃j=1∞ ⋂m=j∞Amc)=1. This implies the assertion.  □

We can now choose Ω with P(Ω)=1 such that for any ω∈Ω , for any a priori fixed index j, the trajectory (Zn(x,ω))n≥0 visits infinitely many times any open interval followed by an application of fj . Indeed, let {ak}k be a dense set in S1 and for every index pair (k,ℓ)∈N2 let Ωk,ℓj be the set provided by the Claim for the point x, an index j, and the open set Ok,ℓ=(ak−1/ℓ,ak+1/ℓ) . Let Ω:= ⋂j=1N⋂k∈N⋂ℓ∈NΩk,ℓj and note that P(Ω)=1 .

By the above, without loss of generality, we can also assume that Ω is such that for every ω∈Ω we have ρ(Zn(x,ω),Zn(y,ω))→ξ(ω) as n→∞ .

Fix ω∈Ω . Let a,b,c be points in S1 , with ρ(a,b)=ρ(a,c)=ξ(ω) , where b is obtained from a by a clockwise rotation and c is obtained from a by a counter-clockwise rotation. Note that if 0<ξ(ω)<1/2 then the points a,b,c will be distinct, and otherwise b=c . By definition of Ω we know that if Oa is an open set containing a, Ob is an open set containing b, and Oc is an open set containing c then there are infinitely many n such that Zn(x,ω)∈Oa and either Zn(y,ω)∈Ob or Zn(y,ω)∈Oc . We say that a is clockwise nice if for arbitrarily small open sets Oa and Ob containing a and b, respectively either Zn(x,ω)∈Oa and Zn(y,ω)∈Ob simultaneously or Zn(y,ω)∈Oa and Zn(x,ω)∈Ob simultaneously for infinitely many n, and counterclockwise nice if for arbitrarily small open sets Oa and Ob containing a and b, respectively either Zn(x,ω)∈Oa and Zn(y,ω)∈Oc simultaneously or Zn(y,ω)∈Oa and Zn(x,ω)∈Oc simultaneously for infinitely many n. We call a nice if a is both clockwise nice and counterclockwise nice.

Any a∈S1 is nice.

We first prove that there exist both clockwise nice and counterclockwise nice points. Indeed, by definition of Ω, any a∈S1 is either clockwise nice, counterclockwise nice, or nice. By contradiction, suppose that all points a∈S1 are only clockwise nice (the case that all points are only counterclockwise nice is analogous). Then, in particular, a given point a and the point c obtained from a counterclockwise rotation of a would both be only clockwise nice. But c being clockwise nice would imply that a is counterclockwise nice, contradiction.

Thus, there exist points of either type which are arbitrarily close to each other. Hence, there exists at least one point in S1 which is nice.

By definition of Ω it follows that nice points are mapped to nice points by all maps, so by forward minimality it follows that every point in S1 is nice.  □

Let us now prove that the distance between any two points a,b∈S1 with ρ(a,b)=ξ(ω) is preserved by all the maps in F. Arguing by contradiction, suppose that ξ(ω)∉L , and consider an interval [a,b] with ρ(a,b)=ξ(ω) such that for some j∈{1,…,N} we have ρ(a,b)≠ρ(fj(a),fj(b)). By continuity of fj , there exist open intervals Oa and Ob containing a and b, respectively and some positive number ε such that for any a′∈Oa and any b′∈Ob we have |ρ(a′,b′)−ρ(fj(a′),fj(b′))|>ε. \varepsilon .\]]]>

By choice of Ω and the fact that a is nice, there exist arbitrary large integers n such that either Zn(x,ω)∈Oa , and Zn(y,ω)∈Ob simultaneously or Zn(y,ω)∈Oa , and Zn(x,ω)∈Ob simultaneously and In+1(ω)=ωn+1=j . Hence |ρ(Zn(x,ω),Zn(y,ω))−ρ(Zn+1(x,ω),Zn+1(y,ω))|>ε, \varepsilon ,\]]]> contradicting the assumption that ω∈Ω .

This completes the proof that for any x,y∈S1 , ρ(Znx,Zny) converges almost surely to an L-valued random variable.  □

The following result about uniqueness of invariant probability measures is not new and was, to the best of our knowledge, first proved in [17]. A simple direct proof based on equicontinuity was recently presented in [22]. Note that equicontinuity of {Tnh} , where Tnh(x)=∫h(Zn(x,ω))dP(ω) for any Lipschitz continuous function h:S1→R , follows trivially from Proposition 1. Indeed, if ρ is the metric of Proposition 1, then ∫ρ(Zn(x,ω),Zn(y,ω))dP(ω)≤ρ(x,y) . For completeness we will show that uniqueness of invariant probability measures is also a very simple consequence of Theorem 1.

Any IFS (F,p) with probabilities of homeomorphisms on S1 which is forward and backward minimal has a unique invariant probability measure μ+ .

Let μ− be an invariant probability measure for (F−1,p) and define the metric ρ by ρ(x,y):=min{μ−([x,y]),μ−([y,x])} . By Proposition 1, the IFS G={gj}j defined by gj:=Φ−∘fj∘Φ−−1 , where Φ−(x)=μ−([0,x]) , with probabilities p is non-expansive on average with respect to d and we have L:=L(G,d)=L(F,ρ) .

By Theorem 1, with Zn as in (1) and Wn:=Φ−∘Zn∘Φ−−1 , we have that d(Wnx,Wny) converges almost surely to an L-valued random variable as n→∞ , for any x,y∈S1 .

We are now going to show that there is a unique invariant probability measure ν+ for the IFS (G,p) . This will imply that μ+:=(Φ−−1)∗ν+ is the unique invariant probability measure for (F,p) .

Let us divide the proof into cases:

Case L={0} . Consider first the (generic) case L={0} . Thus, d(Wnx,Wny)→0 as n→∞ a.s. for any x,y∈S1 . Let ν+ be an invariant probability measure for (F,p) , that is, a stationary distribution for (Wnx)n≥0 (recall Remark 1). For any x,y∈S1 and for any continuous h:S1→R , by Lebesgue’s dominated convergence theorem Tnh(x)−Tnh(y)=∫Σh(Wn(x,ω))dP(ω)−∫Σh(Wn(y,ω))dP(ω)→0 as n→∞ , and thus by invariance of ν+ we have |Tnh(x)−∫hdν+|=|Tnh(x)−∫Tnhdν+|≤∫|Tnh(x)−Tnh(y)|dν+(y) and by Lebesgue’s dominated convergence theorem the latter tends to 0 as n→∞ . This implies that ν+ must be attractive and thus unique (recall Remark 3).

Case L={0,1/k,…,⌊k/2⌋/k} for some k≥2 . By Lemma 3 all invariant probability measures for (G,p) are 1/k -invariant. By contradiction, suppose that there are two distinct invariant probability measures ν+1 and ν+2 for (G,p) . Hence, if X and Y are two random variables with distribution ν+1 and ν+2 respectively, independent of {In} , then WnXmod1/k , and WnY mod 1/k will also have distinct distributions for any fixed n≥0 , by 1/k –invariance of ν+1 and ν+2 . The latter is however impossible since the IFS G˜={g˜j} defined by g˜j(x)=k(gj(x/k)mod1/k) , j=1,…,N , satisfies L(G˜,d)={0} (recall Remark 6) and therefore the distribution of WnXmod1/k converges to the same limit as the limiting distribution of WnYmod1/k , as n→∞ . The invariant probability measure, ν+ , is therefore unique.

Case L=[0,1/2] . In this case, by Lemma 1 all maps in G are isometries (with respect to d). By Lemma 3, any invariant probability measure is s-invariant for any s∈[0,1/2] , which implies that ν+ must be the Lebesgue measure.  □

By applying Breiman’s ergodic theorem for Feller chains with a unique stationary distribution starting at a point (see, for example, [6] or [18]), we get the following result. Let δx denote the Dirac measure concentrated in the point x∈S1 , and let μnx(ω)=1n ∑k=0n−1δZk(x,ω), denote the empirical distribution along the trajectory starting at x∈S1 determined by ω∈Σ at time n−1 .

Let (F,p) be an IFS with probabilities of homeomorphisms on S1 which is forward and backward minimal and let μ+ denote its unique invariant probability measure. Then μnx(ω) converges to μ+ (in the weak∗ sense) P a.s. for any x∈S1 .

Corollary 3 slightly generalizes [21, Proposition 16] where a direct proof is given and the additional hypotheses that all maps in the IFS preserve orientation and that one map is minimal are assumed.

Let →d denote convergence in distribution. We are now ready to state our first result about invariant measures/stationary distributions for the IFS with probabilities generated by the inverse maps.

Let (F,p) be an IFS with probabilities of homeomorphisms on S1 which is forward minimal and non-expansive on average with respect to d. Assume that some map fj is not an isometry (with respect to d). Then L(F,d)={0,1/k,…,⌊k/2⌋/k} for some k≥1 and for any 1/k -invariant nonatomic and fully supported random variable X on S1 , independent of (In)n≥0 we have Zˆn−(X,ω)→dZˆ−(ω) as n→∞ for P a.a. ω∈Σ , where Zˆ−(ω) is a random variable with distribution μω−=1k ∑i=0k−1δ1k(i+Zˆ−(ω)) for some random variable Zˆ−:Σ→S1 and μω−=(fω1−1)∗μσ(ω)− for P a.a. ω∈Σ .

Thus, the measure μ− given by μ−:=∫μω−dP(ω) is the unique invariant probability measure for (F−1,p) .

Let L=L(F,d) . By Lemma 1 together with our hypotheses, we have L={0,1/k,…,⌊k/2⌋/k} for some k≥1 . Hence, if d(x,y)=s∈L , then d(fj(x),fj(y))=s for all j=1,…,N and thus d(Zn(x,ω),Zn(y,ω))=s for any ω∈Σ and n≥0 .

Let us denote by Zn and Zˆn− the sequences defined in (1) and (3), respectively. By Theorem 1 we have that d(Znx,Zny) converges almost surely to an L-valued random variable as n→∞ .

Given ω∈Σ , let Zˆ−(ω):=ksup{y:|Zn([0,y],ω)|→0, as n→∞}, where |·| denotes the length of an interval and where we use the notation Zn([0,y],ω):={Zn(z,ω):z∈[0,y]}. Note that y↦|Zn([0,y],ω)| is an increasing function, for each fixed n and ω. Further, |Zn([0,y],ω)| converges to an element in {0,1/k,…,1} as n→∞ , for any y∈S1 for P a.a. ω∈Σ . Indeed, this follows from the fact that d(Znx,Zny) converges to an element of L and the fact that x↦Znx is a random homeomorphism. So Zˆ−:Σ→S1 is a well-defined random variable.

Let m be an arbitrary 1/k -invariant nonatomic probability measure fully supported on S1 . Note that if I is an interval of length i/k , then m(I)=i/k for any 0≤i≤k . If x∉{Zˆ−(ω)/k,(Zˆ−(ω)+1)/k,…,(Zˆ−(ω)+(k−1))/k} , then m({y∈S1:Zˆn−(y,ω)≤x})=m({y∈S1:Zˆn−(y,ω)∈[0,x]})=m({y∈S1:Zn(Zˆn−(y,ω),ω)∈Zn([0,x],ω)})=m({y∈S1:y∈Zn([0,x],ω)})→0 if x<Zˆ−(ω)k,ik if Zˆ−(ω)+(i−1)k<x<Zˆ−(ω)+ik,1≤i≤k−1,1 if x>Zˆ−(ω)+(k−1)k \displaystyle \frac{{\widehat{Z}}^{-}(\omega )+(k-1)}{k}\end{array}\right.\end{array}\]]]> as n→∞ for P a.a. ω∈Σ . Thus, if X is an m-distributed random variable on S1 , independent of (In)n≥0 and Zˆ−(ω) has distribution μω−=1k ∑i=0k−1δ(i+Zˆ−(ω))/k for P a.a. ω∈Σ then m(Zˆn−(X,ω)≤x)→m(Zˆ−(ω)≤x) as n→∞ if x is a continuity point of the cumulative distribution function of Zˆ−(ω) (for P a.a. ω∈Σ ). Thus, Zˆn−(X,ω) converges in distribution to Zˆ−(ω) as n→∞ for P a.a. ω∈Σ . By taking limits in the equality Zˆn−(X,ω)=fω1−1(Zˆn−1−(X,σ(ω))) , it therefore follows that Zˆ−(ω)=fω1−1(Zˆ−(σω)), for P a.a. ω. Thus if μω− denotes the distribution of Zˆ−(ω) , then μω−=(fω1−1)∗μσ(ω)−. for P a.a. ω.

By integrating both sides of this equality with respect to P (recall that P is a Bernoulli measure determined by a probability vector p=(p1,…,pN) ) we thus obtain that μ−:=∫μω−dP(ω)= ∑j=1N∫ω:ω1=j(fω1−1)∗μσ(ω)−dP(ω)= ∑j=1N∫ω:ω1=j(fj−1)∗μσ(ω)−dP(ω)= ∑j=1N∫ω:ω1=j(fj−1)∗μ−dP(ω)= ∑j=1Npj(fj−1)∗μ− and μ− is therefore invariant for (F−1,p) . Since by construction μω is independent of X, it follows that μ− is indeed uniquely invariant.  □

Using Propositions 1 and 2 we get the following corollary.

Let (F,p) be an IFS with probabilities of homeomorphisms on S1 which is forward and backward minimal. Assume that not all maps in F are conjugate (with a common conjugation map) to an isometry (with respect to d). Let μ− be an invariant probability measure for (F−1,p) , and let k be the largest integer such that μ− is 1/k -invariant. Conclusion: if X is a μ− -distributed random variable, independent of (In)n≥0 , then Zˆn−(X,ω)→dZˆ−(ω), as n→∞ for P a.a. ω∈Σ , where Zˆ−(ω) is a random variable with distribution μω , uniformly distributed on k distinct points, and satisfying μω−=(fω1−1)∗μσ(ω)− for P a.a. ω∈Σ . It therefore follows that μ− is unique and given by μ−=∫μω−dP(ω) .

Convergence in (9) also follows from Furstenbergs martingale argument [11], but here we say more about the limit: The limit is 1/k -invariant and independent of X (this implies that μ− is uniquely invariant) and the limiting fiber measures μω are uniform and supported on sets of size k.

Let μ− be an invariant probability measure for (F−1,p) . By Proposition 1, the IFS G={gj}j defined by gj:=Φ−∘fj∘Φ−−1 , where Φ−(x)=μ−([0,x]) , with probabilities p satisfies the hypotheses of Proposition 2. Note that F is forward minimal if, and only if, G is. Let L(G,d) be the corresponding set of simultaneously preserved distances. By Lemma 1, we have L(G,d)={0,1/k,…,⌊k/2⌋/k} for some k≥1 .

Let us denote by (Wˆn−)n≥0 the sequence for the IFS G which is analogously defined as in (3) for the IFS F. Since F and G are conjugate by means of Φ− , it is easy to check that Zˆn−=Φ−−1∘Wˆn−∘Φ−.

Note that if X is a μ− -distributed random variable, independent of (In)n≥0 , then Y:=Φ−(X) is distributed according to the Lebesgue measure on S1 . Hence, in particular, it follows that Y is a 1/k -invariant, nonatomic, and fully supported random variable on S1 .

By Proposition 2, it therefore follows that Wˆn−(Φ−(X),ω)=Φ−(Zˆn−(X,ω))→dWˆ−(ω) as n→∞ for P a.a. ω∈Σ , where Wˆ−(ω) is a random variable with distribution νω−=1k ∑i=0k−1δ1k(i+Wˆ−(ω)) for some random variable Wˆ−:Σ→S1 , that is, we have Zˆn−(X,ω)→dΦ−−1(Wˆ−(ω)) as n→∞ for P a.a. ω∈Σ . Thus, if we define Zˆ−(ω):=Φ−−1(Wˆ−(ω)) , then this random variable has distibution μω(·)=νω(Φ−(·)) . Moreover, the measure μ− given by μ−:=∫μω−dP(ω) is the unique invariant probability measure for (F−1,p) .  □

If (F,p) is both forward and backward minimal, then by applying the above Corollary to (F−1,p) we obtain an alternative proof of uniqueness for μ+ under these assumptions.

 Acknowledgement

We are grateful to the referees whose comments on an earlier draft of the paper led to a substantially improved revised paper. KG also thanks Anton Gorodetski and Victor Kleptsyn for inspiring discussions.

 References Antonov, V.A.: Modeling of processes of cyclic evolution type. Synchronization by a random signal. Vestnik Leningrad. Univ. Mat. Mekh. Astronom. 2, 67–76 (1984). (in Russian). MR0756386 Arnold, L.: Random Dynamical Systems. Springer Monographs in Mathematics. Springer, Berlin (1998). MR1723992. doi:10.1007/978-3-662-12878-7 Ávila, A., Viana, M.: Extremal Lyapunov exponents: an invariance principle and applications. Inventiones Mathematicae 181, 115–178 (2010). MR2651382. doi:10.1007/s00222-010-0243-1 Barnsley, M.F., Demko, S.: Iterated function systems and the global construction of fractals. Proc. Roy. Soc. London. Ser. A 399, 243–275 (1985). MR0799111. doi:10.1098/rspa.1985.0057 Barrientos, P.G., Ghane, F.H., Malicet, D., Sarizadeh, A.: On the chaos game of iterated function systems. Topol. Methods Nonlinear Anal. 49, 105–132 (2017). MR3635639 Breiman, L.: The strong law of large numbers for a class of Markov chains. Ann. Math. Statist. 31, 801–803 (1960). MR0117786. doi:10.1214/aoms/1177705810 Chung, K.L.: A Course in Probability Theory, 3rd edn. Academic Press, Inc., San Diego, CA (2001). MR1796326 Crauel, H.: Extremal exponents of random dynamical systems do not vanish. J. Dyn. Diff. Equations 2, 245–291 (1990). MR1066618. doi:10.1007/BF01048947 Díaz, L.J., Gelfert, K., Rams, M.: Nonhyperbolic step skew-products: Ergodic approximation. To appear in: Annales de l’Institut Henri Poincare / Analyse non lineaire Furstenberg, H.: Noncommuting random products. Trans. Amer. Math. Soc. 108, 377–428 (1963). MR0163345. doi:10.2307/1993589 Furstenberg, H.: Boundary theory and stochastic processes on homogeneous spaces. Proc. Sympos. Pure Math. 26, 193–229 (1973). MR0352328. doi:10.1090/pspum/026/0352328 Ghys, E.: Groups acting on the circle. Enseign. Math. (2) 47, 329–407 (2001). MR1876932 Golenishcheva-Kutuzova, T., Gorodetski, A., Kleptsyn, V., Volk, D.: Translation numbers define generators of Fk+→Homeo+(S1) . Mosc. Math. J. 14, 291–308 (2014). MR3236495 Kleptsyn, V.A., Nal’skiĭ, M.B.: Convergence of orbits in random dynamical systems on a circle. Funct. Anal. Appl. 38, 267–282 (2004). MR2117507. doi:10.1007/s10688-005-0005-9 Ledrappier, F.: Positivity of the exponent for stationary sequences of matrices. In: Lyapunov Exponents, pp. 56–73. Springer, (1986). MR0850070. doi:10.1007/BFb0076833 Le Jan, Y.: Équilibre statistique pour les produits de difféomorphismes aléatoires indépendants. Ann. Inst. H. Poincaré Probab. Statist. 23, 111–120 (1987). MR0877387 Malicet, D.: Random walks on Homeo (S1) . Comm. Math. Phys. Preprint, To appear in arXiv:1412.8618 Meyn, S.P., Tweedie, R.L.: Markov Chains and Stochastic Stability. With a prologue by Glynn, P.W. (ed.): 2nd edn. Cambridge University Press, Cambridge (2009). MR2509253. doi:10.1017/CBO9780511626630 Navas, A.: Groups of Circle Diffeomorphisms, Translation of the 2007 Spanish edition. Chicago Lectures in Mathematics. University of Chicago Press, Chicago, IL (2011). MR2809110. doi:10.7208/chicago/9780226569505.001.0001 Stenflo, Ö.: A survey of average contractive iterated function systems. J. Difference Equ. Appl. 18, 1355–1380 (2012). MR2956050. doi:10.1080/10236198.2011.610793 Szarek, T., Zdunik, A.: Stability of iterated function systems on the circle. Bull. Lond. Math. Soc. 48, 365–378 (2016). MR3483074. doi:10.1112/blms/bdw013 Szarek, T., Zdunik, A.: The Central Limit Theorem for function systems on the circle. Preprint arXiv:1703.10465 Viana, M.: Lectures on Lyapunov exponents. Cambridge Studies in Advanced Mathematics, vol. 145. Cambridge University Press, Cambridge (2014). MR3289050. doi:10.1017/CBO9781139976602