# An Approach of Randomness of a Sample Based on Its Weak Ergodic Limit

Authors: Jaime A. Londoño
Journal: Journal of Probability and Statistics
 (2017)

---

## Abstract

For a Polish Sample Space with a Borelσ-field with a surjective measurable transformation, we define an equivalence relation on sample points according to their ergodic limiting averages. We show that this equivalence relation partitions the subset of sample points on measurable invariant subsets, where each limiting distribution is the unique ergodic probability measure defined on each set. The results obtained suggest some natural objects for the model of a probabilistic time-invariant phenomenon are uniquely ergodic probability spaces. As a consequence of the results gained in this paper, we propose a notion of randomness that is weaker than recent approaches to Schnorr randomness.


---

## Body

## 1. Introduction

To understand the meaning of randomness several approaches have been undertaken. Some of them include Kolmogorov [1], Martin-Löf [2], Zvonkin and Levin [3], and Schnorr [4] among many others.On the initial attempts, researchers were trying to identify when a sequence of numbers was random. The sequence of digits ofπ or sequences of computer-generated numbers produced by an algorithm that seems to exhibit a “random behavior” motivated the original problem. In any case of interest, the sequences are elements of {0,1,…,9}N or RN and researchers would like to give a criterion that decides for a sequence to be “random.” In general, sample spaces that allow a Polish Space structure and a surjective transformation (the shifting transformation) embrace the interesting cases.In this paper, we show that a natural approach for a sample space is to consider all samples that describe the same physical time-invariant phenomenon. We would demonstrate that this method allows for a richer probability structure. The latter introduces a different view for randomness, in a way that two sample objects are equivalent if they describe the same probability phenomenon (in a way that we determine precisely later), and, as a consequence, we give an alternative answer to the problem of trying to define randomness.The Ergodic Theorem and the Ergodic Decomposition Theorem motivate our definition. Indeed, our approach goes hand in hand with Gray [5] and extends some results of Shields [6]. Some recent works which study the relation between Ergodic Theory and randomness are V’yugin [7], Gács et al. [8], and Galatolo et al. [9].The Birkhoff-Kinchin Ergodic Theorem (See Billingsley [10]) states that if θ is a measure preserving transformation defined on a probability space (Ω,F,P) and X:Ω,F→Rd,BRd is an integrable random vector, then (1)limn⁡1n∑k=1nX∘θk-1=EX∣Fθa.e.,where Fθ=F∈F∣θ-1(F)=F is the σ-field of invariant sets (under θ). For another interpretation of this fact, we define for each n(2)Pnθω,F=1n∑k=1n1F∘θk-1ωforF∈F.It follows that Pnθ:Ω×F→[0,1] defines a (finite) kernel, where Pnθ(ω,·) is an ergodic measure. Moreover for any measurable random vector X:Ω,F→Rd,BRd(3)∫ΩXdPnθω,·=1n∑k=1nX∘θk-1ω.The Birkhoff Ergodic Theorem implies that whenever θ is an ergodic measure preserving transformation and X is an integrable random vector there exists a set NX∈F with PNX=0 such that for ω∉NX(4)∫ΩXdPnθω,·⟶∫ΩXdP.Using the terminology of Gács et al. [8], if ω satisfies (4), ω is said to be θ typical with respect to the observable X. Moreover, if the last equation holds for any bounded continuous function X, then ω is said to be θ typical. The latter is equivalent to the weak convergence of Pnθ(ω,·)→P. For a review on weak convergence see Billingsley [11]. Moreover, if ω is θ typical for any effective ergodic surjective transformation, then it is said that ω is typical. For a definition of effective ergodic transformation see Gács et al. [8].For any computable measureP, defined on Ω={0,1}N, with Borel σ-field F, V’yugin [7] showed that any Martin-Löf random sequence ω∈Ω is typical. For a review on Martin-Löf randomness see Martin-Löf [2]. Galatolo et al. [9] generalize the last result to computable probability spaces and P-computable observables. For a discussion of the definition and consequences of computable probability, spaces see Gács et al. [8].Moreover Gács et al. [8] extend the concept of Schnorr randomness to computable probability spaces, and they show that the idea of Schnorr randomness is weaker than the notion of Martin-Löf randomness in this context. For a definition of Schnorr randomness see Schnorr [4]. Gács et al. [8] also showed that on an arbitrary computable probability space (Ω,F,P) space with no atoms ω∈Ω is Schnorr random if and only if ω is θ typical for every mixing endomorphism θ.In this paper, we obtain another approach to randomness. Assume that(Ω,d) is a Polish Space, with metric d, and assume the Borel σ-field F=Bd(Ω) on Ω. Moreover assume a measure preserving transformation θ defined on Ω. For most problems related to finding a reasonable definition for randomness it is sufficient to assume that Ω=RN is the sample space of real valued sequences with the metric d(ω,ω′)=∑n2-nmin⁡ωn-ω′n,1, the shifting transformation θ(ω)(n)=ω(n+1), and the sequence of processes Xn(ω)=ω(n) and with a probability that makes Xn independent with the same distribution PX1 defined as PX1(F)=PX1-1F for all F∈B(R) Borel set.With the help of the Ergodic Decomposition Theorem (see Proposition1) it is possible to show that there exists a set N∈F with P(N)=0 where, for any ω∉N, Pnθ(ω,·) are probability measures that convergeweakly, and the limiting distribution is an ergodic invariant probability measure Q(ω,·) on F.The latter suggests, in a manner to be precise by Theorem3, that only samples that describe a physical phenomenon (those whose ergodic limit is a “reasonable” probability) should be considered as samples for any physical “reasonable probability space.” It is also apparent, as shown by Theorem 3, that a stronger theory can be established if other samples are not considered.We propose to partition the sample space according to their weak ergodic limit: assume a measurable space(Ω,F), as above, and assume a surjective measurable function θ:(Ω,F)→(Ω,F). We define an equivalent relation on Ω, by ω≅ω′ iff for any bounded continuous function X:Ω→R(5)limn∫ΩXdPnθω,·-∫ΩXdPnθω′,·=0.If ω≅ω′ we say that ω has thesame stochastic type of ω′. Clearly ≅ is an equivalence relation on elements on Ω. Moreover if Pnθ(ω,·)→P weakly and ω≅ω′ then Pnθ(ω′,·)→P weakly, and if P is a θ null invariant probability (see Definition 2) then it is a θ invariant probability (see Theorem 3).We notice that the requirement of weak convergence ofPnθ(ω,·) as n→∞ to a probability measure is quite natural. The latter is because for any probability space defined on a Polish Space with a measure preserving transformation for almost all ω the mentioned weak convergence holds (see Proposition 1). In the case where Pnθ(ω,·)→P we say thatstochastic type ofωisP.The main contribution of this paper is Theorem3. Roughly speaking, Theorem 3 states that any reasonable space is divided into nonoverlapping subspaces, where on each subspace the statistics behavior of all the points is identical, and where these spaces have a simple statistical structure (they are uniquely ergodic). In fact Shields [6] [Section I.4.c] suggested in the case of finite alphabets (Ω={1,…,n}Z for some n) that, as a consequence of the Ergodic Decomposition Theorem, such decomposition is natural.As a result of Theorem3, for any physical “reasonable probability space” only the samples that describe a physical phenomenon (those whose ergodic limit is a “reasonable” probability) are sufficient as realizations of the sample space to study the physical phenomenon (the other realizations are unnecessary).In the current stay of affairs, for any sample realization of a probability space and any statistical application, only a finite set of valuesXn(ω) are observed, due to our technical limitations (the amount of time required to gather data is finite). Therefore, the assumption thatany  ω belongs to the sample space (for instance in the case that Ω=RN) is a technical assumption that it is motivated as long as it provides a rich and consistent theory. However we are showing in Theorem 3 that a richer theory is obtained if we restrict the sample space to those ω whose weak ergodic limit is a θ null invariant probability. The gain achieved in the modeling structure arises from the fact that the limiting probabilities describing the physical phenomenon are uniquely ergodic.Therefore, our conclusions suggest further studies could point out to consider the uniquely ergodic probability spaces as natural spaces for the modeling of any physical time-invariant phenomenon.Also, as a consequence of Theorem3, and results obtained by Gács et al. [8], a natural definition for a ω to be random is that Pnθ(ω,·) converges weakly to a θ null invariant ergodic measure (see Definition 2). In fact, it follows that our definition of randomness extends to noncomputable probability spaces, and by Gács et al. [8] on computable probability spaces our notion of randomness is weaker than Schnorr randomness (and therefore weaker than Martin-Löf randomness).In our approach, we do not consider any possible mixing endomorphism. Contrary to existing methods we fix a surjective transformationθ. Our approach works on any Polish Space, and it works for any probability measure (instead of computable probability spaces).Issues that remain open include studying the consequences of modeling probability spaces as uniquely ergodic spaces. On the side of randomness, it remains open to examining definitions of randomness for discrete sequences that model non-ergodic Dependent Processes and a definition of randomness for functions defined on an interval (in the ergodic and non-ergodic cases). Finally, it remains open to provide specific sequences that are random (or whose limiting distribution is a particular distribution) and to provide examples of sequences that are random in the sense we give in this paper and are not random in the Schnorr sense (and therefore not random in the Martin-Löf sense).


## 2. Randomness

The first proposition says that on “reasonable spaces,” for any reasonable physical realization,always the ergodic averages converge weakly to ergodic invariant measures.Proposition 1.
Assume a measure preserving transformationθ defined on a probability space (Ω,F,P), where (Ω,d) is a Polish Space, and F=Bd(Ω) is the Borel σ-field. Let Fθ be the σ-field of invariant sets (with respect to θ). Define Pnθ(ω,·) by (2).
There exist a setN∈F with P(N)=0 where for any ω∉N, Pnθ(ω,·) are probability measures that convergeweakly to the ergodic invariant probability measure PF∣Fθ(ω,·) where PF∣Fθ(·,·) is the regular conditional probability kernel with respect to Fθ of the Ergodic Decomposition Theorem.Proof.
Assume thatD is a countable dense subset of Ω. We notice that the class of sets A that are finite intersections of balls with a rational radius centered at points in D is a countable π-system with σ(A)=F. Let F0 be the countable field generated by A. By the Ergodic Decomposition Theorem there exists a set N, with P(N)=0 such that, for F∈F0,(6)limn⁡1n∑k=1n1F∘θk-1ω=PF∣Fθω,Fforω∉N,where PF∣Fθ(ω,·) is the ergodic invariant probability measure corresponding to the regular conditional probability kernel with respect to Fθ of the Ergodic Decomposition Theorem.
Assume an open setU, then there exist Ai∈A, with U=⋃i=1∞Ai=⋃i=1∞Bi, where Bi∈F0 can be assumed disjoint sets with ⋃i=1mBi=⋃i=1mAi for each m≥1. It follows that for ω∉N(7)liminfn⁡Pnω,U=liminfn⁡1n∑k=1n1U∘θk-1ω=liminfn⁡∑k=1n∑i=1∞1n1Bi∘θk-1ω=liminfn⁡∑i=1∞∑k=1n1n1Bi∘θk-1ω≥∑i=1∞limn⁡∑k=1n1n1Bi∘θk-1ω=∑i=1∞PF∣Fθω,Bi=PF∣Fθω,U,where the second equality follows by absolute convergence of ∑k=1n∑i=1∞1/n1Bi∘θk-1(ω), and the third equality follows Fatou’s Lemma. Finally the result follows by the Portmanteau Theorem (see Billingsley [11]).The latter proposition suggests that, for any reasonable physical realization (ω∉N), the ergodic average Pnω,· converges weakly to an ergodic θ invariant probability measure. It turns out that a weaker concept for invariability is sufficient to describe the limiting ergodic behavior of any reasonable “physical realization.”Definition 2.
Given a measurable space(Ω,F) and a surjective transformation θ:(Ω,F)→(Ω,F), we say that a probability measure P defined on F is a θnull invariant probability if P(F)=0 implies that Pθ-1F=0.Under conditions of Proposition1 we obtain a necessary requirement for the limit probabilities of Pnθ to be null invariant. In Theorem 3 we prove that the latter condition is sufficient demand for the limiting probabilities to converge weakly to an invariant probability measure.In the next theorem, we prove that for any physical “reasonable probability space” only the realizations (or samples) that describe a physical phenomenon (those whose ergodic limit is a “reasonable.” probability) are sufficient as realizations of the sample space to study the physical phenomenon (the other samples are unnecessary) and that those realizations (or samples) partition the whole space according to the physical phenomenon that they describe. Moreover, we show that when we restrict ourselves to those samples that describe the same physical phenomenon (those whose limiting ergodic behavior is the same), the mathematical structure of the space defined is richer (in the sense that the probability spaces are uniquely invariant). The above conclusions make a strong point to consider the unique invariant probability spaces as natural spaces for the modeling of a physical time-invariant phenomenon.Theorem 3.
Assume a measurable surjective functionθ:(Ω,F)→(Ω,F) defined on a measurable space (Ω,F), where (Ω,d) is a Polish Space and F=Bd(Ω) is the Borel σ-field, where d is a metric for which Ω is a complete separable space. Let ω∈Ω and assume that Pnθ(ω,·)→P weakly, where P is a θ null invariant probability. Then P is a θ invariant probability measure defined on F. Moreover if(8)ΩP=ω′∣Pnθω′,·⟶Pthen ΩP is a measurable invariant set with θ(ΩP)=ΩP where either P(ΩP)=0 or P(ΩP)=1 and P is ergodic iff P(ΩP)=1. Moreover, there exist a countable field F0 where any open can be written as a countable union of elements of F0, such that, for any A∈F0, and ω′∈ΩP, Pnθ(ω′,A)→P(A) (and in particular σ(F0)=F).
Moreover, ifP is an ergodic probability measure there is only one ergodic θ invariant measure on (ΩP,F∩ΩP=F∩ΩP,F∈F) (namely, P).Proof.
LetD be a countable dense subset of Ω. For each d∈D, define A(d) to be a countable set of balls with center at d, with radius rd,n↓0 when n→∞ such that P∂Brd,nd=0, for n=1,2,…, where x∈D, Br(x)=y∣dy,x<r, and ∂F denotes the boundary of given set F. The set A(d) with the desired properties exists by a standard argument. Let F0 be the field generated by ⋃d∈DAd. Clearly any open set can be written as a countable union of elements in F0. By the Portmanteau Theorem Pnθ(ω,A)→P(A) for any A∈F0.
For any setA∈F0, it is clear that limnPnθ(ω,A)=limnPnθω,θ-1A, and since the class of sets where P(F)=Pθ-1F is a λ-system that contains A since P is a null invariant probability, it follows by the Dynkin’s π-λ theorem that P(F)=Pθ-1F for any F∈F, proving that P is θ-invariant.
Clearlylimn⁡Pnθω,A=limn⁡Pnθθω,A, for any A∈F0, and therefore using the Dinkyn π-λ theorem the limiting measure associated with ω and θ(ω) is the same, proving that θ(ΩP)⊂ΩP. We also notice that, for ω∈ΩP, if ω′∈Ω is an element such that θ(ω′)=ω, then limn⁡Pnθω′,A=limn⁡Pnθω,A, for any A∈F0, and then by the Dynkin’s π-λ theorem ω′≅ω proving that θ(ΩP)=ΩP. Next we prove that ΩP is a measurable set. For the latter, let ψ:N→F0 be an enumeration of F0. Define φ_,φ¯:Ω,F→RN,BRN by(9)φ¯ωm=limsupn⁡Pnθω,ψm,φ_ωm=liminfn⁡Pnθω,ψm.Then by the Portmanteau Theorem ΩP=ω∣φ¯(ω)=φ_(ω)=ωP, where ωP∈RN is defined by ωP(m)=limnPnθ(ω,ψ(m)), and therefore ΩP is measurable.
By the Ergodic Decomposition Theorem, there exist a kernelPF∣Fθ:Ω×F→[0,1] and set N, with P(N)=0 with the property that for all ω∉N  limnPnθω,A→PF∣Fθω,A for all A∈F0, PF∣Fθω,· is an ergodic measure, and(10)PG∩F=∫GPF∣Fθω,FdPFθF∈F,G∈Fθ,where PFθ is the restriction to Fθ of P and Fθ is the σ-field of invariant sets (under θ). It follows that for A∈F0(11)PΩP∩A=∫ΩPPF∣Fθω,AdPFθ=∫ΩPPAdPFθ=PAPΩP.Since the class of sets F∈F where P(ΩP∩F)=P(F)P(ΩP) is a λ system, by the Dynkin’s π-λ theorem it follows that for all F∈F, P(ΩP∩F)=P(F)P(ΩP). In particular P(ΩP)=P2(ΩP), proving that P(ΩP)=0 or P(ΩP)=1.
Assume thatP(ΩP)=1, then by the Ergodic Decomposition Theorem, there exist a set N where P(N)=0 and ω∉N, Pnθ(ω,F)→PF∣Fθ(ω,F)=P(F), for F∈F0 where PF∣Fθ(ω,·) is ergodic. It follows that P is ergodic.
Finally assume thatP(ΩP)=1, and assume an ergodic probability measure Q on ΩP. It is clear that Q can be extended to (Ω,F), in a natural way as Q(F)=Q(F∩ΩP). We also denote the extension as Q. Moreover the extension to F is also ergodic. By the Ergodic Decomposition Theorem, it follows that(12)QA=QΩP∩A=∫ΩPPAdQFθ=PAQΩPforA∈A.It follows that, on F0, Q=P and by the Dinkyn’s π-λ Theorem Q=P on F, and therefore Q=P on F∩ΩP.Probably the most interesting consequence of the previous theorem is the uniform convergence of ergodic averages for all sample points. IfΩP is a compact set then, for any continuous bounded function X defined on ΩP (for the induced topology),for allω∈ΩP(13)1n∑k=1nX∘θk-1ω⟶∫ΩPXdPuniformly on ΩP. The latter is the content of the Oxtoby Theorem [12] [Theorem  6.19].The consequence of Theorem3 that, for any ω∈ΩP, P is ergodic iff P(ΩP)=1 has been observed in the case of finite alphabets by Shields [6] [Section I.9.b]. In fact Shields [6] [Sections I.4.c and I.9.b] suggests a similar approach in the case of finite alphabets, although uniquely ergodicity is not obtained.Finally we observe some elementary facts of our definition.Proposition 4.
Assume a measurable space(Ω,F) and a surjective transformation θ:(Ω,F)→(Ω,F); then: (i)
Ifθ is periodic on ω in the sense that there exist n with θn(ω)=ω, with period k (namely, k=min⁡n∣θn(ω)=ω, then Pnθω,·→P), where P is a probability measure supported on a finite set.(ii)
If there existn,m such that θn(ω)=θmω′, then ω≅ω′. In particular it is impossible to tell from a finite set of values of ω any information about the distribution of ω.(iii)
For anyn, ω≅θn(ω).



---

*Source: 9139645-2017-11-05.xml*