Printer Friendly

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

1. Introduction

To understand the meaning of randomness several approaches have been undertaken. Some of them include Kolmogorov [1], Martin-Lof [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 [pi] 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}.sup.N] or [R.sup.N] 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], Gacs et al. [8], and Galatolo et al. [9].

The Birkhoff-Kinchin Ergodic Theorem (See Billingsley [10]) states that if [theta] is a measure preserving transformation defined on a probability space ([OMEGA], F, P) and X : ([OMEGA], F) [right arrow] ([R.sup.d], B([R.sup.d])) is an integrable random vector, then

[mathematical expression not reproducible] (1)

where [F.sup.[theta]] = {F [member of] F | [[theta].sup.-1]](F) = F} is the [sigma]-field of invariant sets (under [theta]). For another interpretation of this fact, we define for each n

[mathematical expression not reproducible] (2)

It follows that [P.sup.[theta].sub.n] : [OMEGA] x F [right arrow] [0, 1] defines a (finite) kernel, where [P.sup.[theta].sub.n] ([omega], x) is an ergodic measure. Moreover for any measurable random vector X : ([OMEGA], F) [right arrow] ([R.sup.d], B([R.sup.d]))

[mathematical expression not reproducible] (3)

The Birkhoff Ergodic Theorem implies that whenever [theta] is an ergodic measure preserving transformation and X is an integrable random vector there exists a set [N.sub.X] [member of] F with P([N.sub.X]) = 0 such that for [omega[ [not member of] [N.sub.X]

[mathematical expression not reproducible] (4)

Using the terminology of Gacs et al. [8], if [omega] satisfies (4), [omega] is said to be [theta] typical with respect to the observable X. Moreover, if the last equation holds for any bounded continuous function X, then [omega] is said to be [theta] typical. The latter is equivalent to the weak convergence of [P.sup.[theta].sub.n]([omega], x) [right arrow] P. For a review on weak convergence see Billingsley [11]. Moreover, if [omega] is [theta] typical for any effective ergodic surjective transformation, then it is said that [omega] is typical. For a definition of effective ergodic transformation see Gacs et al. [8].

For any computable measure P, defined on [OMEGA] = [{0, 1}.sup.N], with Borel [sigma]-field F, V'yugin [7] showed that any Martin-Lof random sequence [omega] [member of] [OMEGA] is typical. For a review on Martin-Lof randomness see Martin-Lof [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 Gacs et al. [8].

Moreover Gacs 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-Lof randomness in this context. For a definition of Schnorr randomness see Schnorr [4]. Gacs et al. [8] also showed that on an arbitrary computable probability space ([OMEGA], F, P) space with no atoms [omega] [member of] [OMEGA] is Schnorr random if and only if [omega] is [theta] typical for every mixing endomorphism [theta].

In this paper, we obtain another approach to randomness. Assume that ([OMEGA], d) is a Polish Space, with metric d, and assume the Borel [sigma]-field F = [B.sub.d]([OMEGA]) on [OMEGA]. Moreover assume a measure preserving transformation [theta] defined on [OMEGA]. For most problems related to finding a reasonable definition for randomness it is sufficient to assume that [OMEGA] = [R.sup.N] is the sample space of real valued sequences with the metric d([omega], [omega]') = [[SIGMA].sub.n] [2.sup.-n] min([absolute value of ([omega](n) - [omega]'(n))], 1), the shifting transformation [theta]([omega])(n) = [omega](n + 1), and the sequence of processes Xn(w) = w(n) and with a probability that makes [X.sub.n] independent with the same distribution [mathematical expression not reproducible] defined as [mathematical expression not reproducible] for all F [member of] B(R) Borel set.

With the help of the Ergodic Decomposition Theorem (see Proposition 1) it is possible to show that there exists a set N [member of] F with P(N) = 0 where, for any [omega] [not member of] N, [P.sup.[theta].sub.n]([omega], x) are probability measures that converge weakly, and the limiting distribution is an ergodic invariant probability measure Q([omega], x) on F.

The latter suggests, in a manner to be precise by Theorem 3, 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 ([OMEGA], F), as above, and assume a surjective measurable function [theta] : ([OMEGA], F) [right arrow] ([OMEGA], F). We define an equivalent relation on [OMEGA], by [omega] [congruent to] [omega]' iff for any bounded continuous function X : [OMEGA] [right arrow] R

[mathematical expression not reproducible] (5)

If [omega] [congruent to] [omega]' we say that w has the same stochastic type of [omega]'. Clearly [congruent to] is an equivalence relation on elements on [OMEGA]. Moreover if [P.sup.[theta].sub.n]([omega], x) [right arrow] P weakly and [omega] [congruent to] [omega]' then [P.sup.[theta].sub.n]([omega]', x) [right arrow] P weakly, and if P is a [theta] null invariant probability (see Definition 2) then it is a [theta] invariant probability (see Theorem 3).

We notice that the requirement of weak convergence of [P.sup.[theta].sub.n]([omega], x) as n [right arrow] [infinity] 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 [omega] the mentioned weak convergence holds (see Proposition 1). In the case where [P.sup.[theta].sub.n]([omega], x) [right arrow] P we say that stochastic type of [omega] is P.

The main contribution of this paper is Theorem 3. 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 ([OMEGA] = [{1, ..., n}.sup.Z] for some n) that, as a consequence of the Ergodic Decomposition Theorem, such decomposition is natural.

As a result of Theorem 3, 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 values [X.sub.n]([omega]) are observed, due to our technical limitations (the amount of time required to gather data is finite). Therefore, the assumption that any [omega] belongs to the sample space (for instance in the case that [OMEGA] = [R.sup.N]) 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 [omega] whose weak ergodic limit is a [theta] 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 Theorem 3, and results obtained by Gacs et al. [8], a natural definition for a [omega] to be random is that [P.sup.[theta].sub.n]([omega], x) converges weakly to a [theta] null invariant ergodic measure (see Definition 2). In fact, it follows that our definition of randomness extends to noncomputable probability spaces, and by Gaocs et al. [8] on computable probability spaces our notion of randomness is weaker than Schnorr randomness (and therefore weaker than Martin-Lof randomness).

In our approach, we do not consider any possible mixing endomorphism. Contrary to existing methods we fix a surjective transformation 9. 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-Lof 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 [theta] defined on a probability space ([OMEGA], F, P), where ([OMEGA], d) is a Polish Space, and F = [B.sub.d]([OMEGA]) is the Borel [sigma]-field. Let [F.sup.[theta]] be the [sigma]-field of invariant sets (with respect to [theta]). Define [P.sup.[theta].sub.n]([omega], x) by (2).

There exist a set N [member of] F with P(N) = 0 where for any [omega] [not member of] N, [P.sup.[theta].sub.n]([omega], x) are probability measures that converge weakly to the ergodic invariant probability measure [mathematical expression not reproducible] where [mathematical expression not reproducible] is the regular conditional probability kernel with respect to [F.sup.[theta]] of the Ergodic Decomposition Theorem.

Proof. Assume that D is a countable dense subset of [OMEGA]. 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 [pi]-system with [sigma](A) = F. Let [F.sub.0] 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 [member of] [F.sub.0],

[mathematical expression not reproducible] (6)

where [mathematical expression not reproducible] is the ergodic invariant probability measure corresponding to the regular conditional probability kernel with respect to [F.sup.[theta]] of the Ergodic Decomposition Theorem.

Assume an open set U, then there exist [A.sub.i] [member of] A, with U = [U.sup.[infinity].sub.i=1] [A.sub.i] = [U.sup.[infinity].sub.i=1] [B.sub.i], where [B.sub.i] [member of] [F.sub.0] can be assumed disjoint sets with [U.sup.m.sub.i=1] [B.sub.i] = [U.sup.m.sub.i=1] [A.sub.i] for each m [greater than or equal to] 1. It follows that for [omega] [not member of] N

[mathematical expression not reproducible] (7)

where the second equality follows by absolute convergence of [mathematical expression not reproducible], 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 ([omega] [not member of] N), the ergodic average [P.sub.n]([omega], x) converges weakly to an ergodic 9 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 ([OMEGA], F) and a surjective transformation [theta] : ([OMEGA], F) [right arrow] ([OMEGA], F), we say that a probability measure P defined on F is a [theta] null invariant probability if P(F) = 0 implies that P([[theta].sup.-1] (F)) = 0.

Under conditions of Proposition 1 we obtain a necessary requirement for the limit probabilities of [P.sup.[theta].sub.n] 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 [theta] : ([OMEGA], F) [right arrow] ([OMEGA], F) defined on a measurable space ([OMEGA], F), where ([OMEGA], d) is a Polish Space and F = [B.sub.d]([OMEGA]) is the Borel [sigma]-field, where d is a metric for which [OMEGA] is a complete separable space. Let [omega] [member of] [OMEGA] and assume that [P.sup.[theta].sub.n]([omega], x) [right arrow] P weakly, where P is a [theta] null invariant probability. Then P is a [theta] invariant probability measure defined on F. Moreover if

[[OMEGA].sub.P] = {[omega]' | [P.sup.[theta].sub.n] ([omega]', x) [right arrow] P} (8)

then [[OMEGA].sub.P] is a measurable invariant set with [theta]([[OMEGA].sub.P]) = [[OMEGA].sub.P] where either P([[OMEGA].sub.P]) = 0 or P([[OMEGA].sub.P]) = 1 and P is ergodic iff P([[OMEGA].sub.P]) = 1. Moreover, there exist a countable field [F.sub.0] where any open can be written as a countable union of elements of [F.sub.0], such that, for any A [member of] [F.sub.0], and [omega]' [member of] [[OMEGA].sub.P], [P.sup.[theta].sub.n]([omega]', A) [right arrow] P(A) (and in particular [sigma]([F.sub.0]) = F).

Moreover, if P is an ergodic probability measure there is only one ergodic [theta] invariant measure on ([[OMEGA].sub.P], F [intersection] [[OMEGA].sub.P] = {F [intersection] [[OMEGA].sub.P], F [member of] F}) (namely, P).

Proof. Let D be a countable dense subset of [OMEGA]. For each d [member of] D, define A(d) to be a countable set of balls with center at d, with radius r(d, n) [down arrow] 0 when n [right arrow] [infinity] such that P([partial derivative][B.sub.r(d,n)](d)) = 0, for n = 1,2, ..., where x [member of] D, [B.sub.r](x) = {y | d(y, x) < r}, and [partial derivative]F denotes the boundary of given set F. The set A(d) with the desired properties exists by a standard argument. Let [F.sub.0] be the field generated by [U.sub.d[member of]D] A(d). Clearly any open set can be written as a countable union of elements in [F.sub.0]. By the Portmanteau Theorem [P.sup.[theta].sub.n]([omega], A) [right arrow] P(A) for any A [member of] [F.sub.0].

For any set A [member of] [F.sub.0], it is clear that [lim.sub.n][P.sup.[theta].sub.n]([omega], A) = [lim.sub.n][P.sup.[theta].sub.n]([omega], [[theta].sup.-1] (A)), and since the class of sets where P(F) = P([[theta].sup.-1](F)) is a [lambda]-system that contains A since P is a null invariant probability, it follows by the Dynkin's [pi]-[lambda] theorem that P(F) = P([[theta].sup.-1](F)) for any F [member of] F, proving that P is [theta]-invariant.

Clearly [lim.sub.n][P.sup.[theta].sub.n]([omega], A) = [lim.sub.n][P.sup.[theta].sub.n]([theta]([omega]), A), for any A [member of] [F.sub.0], and therefore using the Dinkyn [pi]-[lambda] theorem the limiting measure associated with [omega] and [theta]([omega]) is the same, proving that [theta]([[OMEGA].sub.P]) [subset] [[OMEGA].sub.P]. We also notice that, for [omega] [member of] [[OMEGA].sub.P], if [omega]' [member of] [OMEGA] is an element such that [theta]([omega]') = [omega], then [lim.sub.n][P.sup.[theta].sub.n]([omega]', A) = [lim.sub.n][P.sup.[theta].sub.n]([omega], A), for any A [member of] [F.sub.0], and then by the Dynkin's [pi]-[lambda] theorem [omega]' [congruent to] [omega] proving that [theta]([[OMEGA].sub.P]) = [[OMEGA].sub.P]. Next we prove that [[OMEGA].sub.P] is a measurable set. For the latter, let [psi] : N [right arrow] [F.sub.0] be an enumeration of [F.sub.0]. Define [[phi].bar]([bar.[phi]] : ([OMEGA], F) [right arrow] ([R.sup.N], B([R.sup.N])) by

[mathematical expression not reproducible] (9)

Then by the Portmanteau Theorem [[OMEGA].sub.P] = {[omega] | [bar.[phi]]([omega]) = [[phi].bar]([omega]) = [[omega].sub.P]}, where [[omega].sub.P] [member of] [R.sup.N] is defined by [[omega].sub.P](m) = [lim.sub.n][P.sup.[theta].sub.n]([omega], [psi](m)), and therefore [[OMEGA].sub.P] is measurable.

By the Ergodic Decomposition Theorem, there exist a kernel [mathematical expression not reproducible] and set N, with P(N) = 0 with the property that for all [mathematical expression not reproducible] for all [mathematical expression not reproducible] is an ergodic measure, and

[mathematical expression not reproducible] (10)

where [mathematical expression not reproducible] is the restriction to [F.sup.[theta]] of P and [F.sup.[theta]] is the [sigma]-field of invariant sets (under [theta]). It follows that for A [member of] [F.sub.0]

[mathematical expression not reproducible] (11)

Since the class of sets F [member of] F where P([[OMEGA].sub.P] [intersection] F) = P(F)P([[OMEGA].sub.P]) is a [lambda] system, by the Dynkin's [pi]-[lambda] theorem it follows that for all F [member of] F, P([[OMEGA].sub.P] [intersection] F) = P(F)P([[OMEGA].sub.P]). In particular P([[OMEGA].sub.P]) = [P.sup.2]([[OMEGA].sub.P]), proving that P([[OMEGA].sub.P]) = 0 or P([[OMEGA].sub.P]) = 1.

Assume that P([[OMEGA].sub.P]) = 1, then by the Ergodic Decomposition Theorem, there exist a set N where P(N) = 0 and [mathematical expression not reproducible], for F [member of] [F.sub.0] where [mathematical expression not reproducible] is ergodic. It follows that P is ergodic.

Finally assume that P([[OMEGA].sub.P]) = 1, and assume an ergodic probability measure Q on [[OMEGA].sub.P]. It is clear that Q can be extended to ([OMEGA], F), in a natural way as Q(F) = Q(F [intersection] [[OMEGA].sub.P]). We also denote the extension as Q. Moreover the extension to F is also ergodic. By the Ergodic Decomposition Theorem, it follows that

[mathematical expression not reproducible] (12)

It follows that, on [F.sub.0], Q = P and by the Dinkyn's [pi]-[lambda] Theorem Q = P on F, and therefore Q = P on F [intersection] [[OMEGA].sub.P].

Probably the most interesting consequence of the previous theorem is the uniform convergence of ergodic averages for all sample points. If [[OMEGA].sub.P] is a compact set then, for any continuous bounded function X defined on [[OMEGA].sub.P] (for the induced topology), for all [omega] [member of] [[OMEGA].sub.P]

[mathematical expression not reproducible] (13)

uniformly on [[OMEGA].sub.P]. The latter is the content of the Oxtoby Theorem [12] [Theorem 6.19].

The consequence of Theorem 3 that, for any [omega] [member of] [[OMEGA].sub.P], P is ergodic iff P([[OMEGA].sub.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 ([OMEGA], F) and a surjective transformation [theta] : ([OMEGA], F) [right arrow] ([OMEGA], F); then:

(i) If [theta] is periodic on co in the sense that there exist n with [[theta].sup.n]([omega]) = [omega], with period k (namely, k = min{n | [[theta].sup.n]([omega]) = [omega]}, then [P.sup.[theta].sub.n]([omega], x) [right arrow] P), where P is a probability measure supported on a finite set.

(ii) If there exist n, m such that [[theta].sup.n]([omega]) = [[theta].sup.m]([omega]'), then [omega] [congruent to] [omega]'. In particular it is impossible to tell from a finite set of values of [omega] any information about the distribution of [omega].

(iii) For any n, [omega] [congruent to] [[theta].sup.n]([omega]).

Conflicts of Interest

The author declares that there are no conflicts of interest regarding the publication of this paper.


[1] A. N. Kolmogorov, "Three approaches to the quantitative definition of information," International Journal of Computer Mathematics, vol. 2, no. 1-4, pp. 157-168, 1968.

[2] P. Martin-Lof, "The definition of random sequences," Information and Control, vol. 9, pp. 602-619, 1966.

[3] A. K. Zvonkin and L. A. Levin, "The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms," Russian Mathematical Surveys, vol. 25, no. 6, pp. 83-124, 1970.

[4] C.-P. Schnorr, Zufalligkeit und Wahrscheinlichkeit. Eine algorithmische Begrandung der Wahrscheinlichkeitstheorie, vol. 218 of Lecture Notes in Mathematics, Springer-Verlag, Cham, Switzerland, 1971.

[5] R. M. Gray, Probability, Random Processes, and Ergodic Properties, Springer, Dordrecht, Netherlands, 2nd edition, 2009.

[6] P. C. Shields, The Ergodic Theory of Discrete Sample Paths, vol. 13 of Graduate Studies in Mathematics, American Mathematical Society, Providence, RI, USA, 1996.

[7] V. V. V'yugin, "Effective convergence in probability and an ergodic theorem for individual random sequences," Theory of Probability & its Applications, vol. 420, no. 1, Article ID S0040585, pp. 39-50, 1998.

[8] P. Gocs, M. Hoyrup, and C. Rojas, "Randomness on computable probability spaces-a dynamical point of view," Theory of Computing Systems, vol. 48, no. 3, pp. 465-485, 2011.

[9] S. Galatolo, M. Hoyrup, and C. Rojas, "Effective symbolic dynamics, random points, statistical behavior, complexity and entropy," Information and Computation, vol. 208, no. 1, pp. 23-41, 2010.

[10] P. Billingsley, Probability and Measure, John Wiley & Sons, Inc., Hoboken, NJ, USA, 3rd edition, 1995.

[11] P. Billingsley, Convergence of Probability Measures, John Wiley & Sons, New York, NY, USA, 2nd edition, 1999.

[12] P. Walters, An Introduction to Ergodic Theory, vol. 79, Springer, New York, NY, USA, 1st edition, 2000.

Jaime A. Londono

Departamento de Matematicas y Estadistica, Universidad Nacional de Colombia,

Manizales, Colombia

Correspondence should be addressed to Jaime A. Londono;

Received 7 May 2017; Revised 19 September 2017; Accepted 24 October 2017; Published 5 November 2017

Academic Editor: Ramon M. Rodriguez-Dagnino
COPYRIGHT 2017 Hindawi Limited
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2017 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Title Annotation:Research Article
Author:Londono, Jaime A.
Publication:Journal of Probability and Statistics
Article Type:Report
Geographic Code:1USA
Date:Jan 1, 2017
Previous Article:Stochastic Models for the Infectivity Function in an Infinite Population of Susceptible Individuals.
Next Article:Corrigendum to "Portfolio Theory for [alpha]-Symmetric and Pseudoisotropic Distributions: k-Fund Separation and the CAPM".

Terms of use | Privacy policy | Copyright © 2020 Farlex, Inc. | Feedback | For webmasters