Bernoulli scheme: Difference between revisions
m →Ornstein Isomorphism Theorem: HTTP → HTTPS for the American Mathematical Society, replaced: [http://www.ams.org/ → [https://www.ams.org/ |
TheMathCat (talk | contribs) References updated |
||
Line 1: | Line 1: | ||
{{Short description|generalization of the Bernoulli process to more than two possible outcomes}} |
{{Short description|generalization of the Bernoulli process to more than two possible outcomes}} |
||
{{Use American English|date = March 2019}} |
{{Use American English|date = March 2019}} |
||
In [[mathematics]], the '''Bernoulli scheme''' or '''Bernoulli shift''' is a generalization of the [[Bernoulli process]] to more than two possible outcomes.<ref>P. Shields, ''The theory of Bernoulli shifts'', Univ. Chicago Press (1973)</ref><ref>Michael S. Keane, "Ergodic theory and subshifts of finite type", (1991), appearing as Chapter 2 in ''Ergodic Theory, Symbolic Dynamics and Hyperbolic Spaces'', Tim Bedford, Michael Keane and Caroline Series, Eds. Oxford University Press, Oxford (1991). {{ISBN|0-19-853390-X}}</ref> Bernoulli schemes appear naturally in [[symbolic dynamics]], and are thus important in the study of [[dynamical system]]s. Many important dynamical systems (such as [[Axiom A system]]s) exhibit a [[repellor]] that is the product of the [[Cantor set]] and a [[smooth manifold]], and the dynamics on the Cantor set are isomorphic to that of the Bernoulli shift.<ref>Pierre Gaspard, ''Chaos, scattering and statistical mechanics''(1998), Cambridge University press</ref> This is essentially the [[Markov partition]]. The term ''shift'' is in reference to the [[shift operator]], which may be used to study Bernoulli schemes. The [[Ornstein isomorphism theorem]]<ref>{{ |
In [[mathematics]], the '''Bernoulli scheme''' or '''Bernoulli shift''' is a generalization of the [[Bernoulli process]] to more than two possible outcomes.<ref>P. Shields, ''The theory of Bernoulli shifts'', Univ. Chicago Press (1973)</ref><ref>Michael S. Keane, "Ergodic theory and subshifts of finite type", (1991), appearing as Chapter 2 in ''Ergodic Theory, Symbolic Dynamics and Hyperbolic Spaces'', Tim Bedford, Michael Keane and Caroline Series, Eds. Oxford University Press, Oxford (1991). {{ISBN|0-19-853390-X}}</ref> Bernoulli schemes appear naturally in [[symbolic dynamics]], and are thus important in the study of [[dynamical system]]s. Many important dynamical systems (such as [[Axiom A system]]s) exhibit a [[repellor]] that is the product of the [[Cantor set]] and a [[smooth manifold]], and the dynamics on the Cantor set are isomorphic to that of the Bernoulli shift.<ref>Pierre Gaspard, ''Chaos, scattering and statistical mechanics'' (1998), Cambridge University press</ref> This is essentially the [[Markov partition]]. The term ''shift'' is in reference to the [[shift operator]], which may be used to study Bernoulli schemes. The [[Ornstein isomorphism theorem]]<ref name="OIT">{{cite journal |
||
| first1=Donald | last1=Ornstein | authorlink1=Donald Ornstein |
|||
| title=Bernoulli shifts with the same entropy are isomorphic |
|||
| journal=[[Advances in Mathematics]] |
|||
| volume=4 |
|||
| year=1970 |
|||
| pages=337–352 |
|||
| doi=10.1016/0001-8708(70)90029-0 | doi-access=free}}</ref><ref>{{springer|author=D.S. Ornstein|title=Ornstein isomorphism theorem|id=Ornstein_isomorphism_theorem&oldid=17997}}</ref> shows that Bernoulli shifts are isomorphic when their [[Kolmogorov entropy|entropy]] is equal. |
|||
==Definition== |
==Definition== |
||
Line 49: | Line 56: | ||
==Matches and metrics== |
==Matches and metrics== |
||
The [[Hamming distance]] provides a natural metric on a Bernoulli scheme. Another important metric is the so-called <math>\overline f</math> metric, defined via a supremum over ''string matches''.<ref> |
The [[Hamming distance]] provides a natural metric on a Bernoulli scheme. Another important metric is the so-called <math>\overline f</math> metric, defined via a supremum over ''string matches''.<ref>{{cite journal |
||
| first1=Jacob | last1=Feldman |
|||
J. Feldman (1976) ''New K-automorphisms and a problem of Kakutani''. Israel Journal of Mathematics, '''24''' (1): 16 - 38. |
|||
| year=1976 |
|||
</ref> |
|||
| title=New <math>K</math>-automorphisms and a problem of Kakutani |
|||
| journal=[[Israel Journal of Mathematics]] |
|||
| volume=24 |
|||
| issue=1 |
|||
| pages=16–38 |
|||
| doi=10.1007/BF02761426 | doi-access=free}}</ref> |
|||
Let <math>A = a_1a_2\cdots a_m</math> and <math>B = b_1b_2\cdots b_n</math> be two strings of symbols. A '''match''' is a sequence ''M'' of pairs <math>(i_k, j_k)</math> of indexes into the string, i.e. pairs such that <math>a_{i_k}=b_{j_k},</math> understood to be totally ordered. That is, each individual subsequence <math>(i_k)</math> and <math>(j_k)</math> are ordered: <math>1\le i_1 < i_2<\cdots <i_r\le m</math> and likewise <math>1\le j_1 < j_2<\cdots <j_r\le n.</math> |
Let <math>A = a_1a_2\cdots a_m</math> and <math>B = b_1b_2\cdots b_n</math> be two strings of symbols. A '''match''' is a sequence ''M'' of pairs <math>(i_k, j_k)</math> of indexes into the string, i.e. pairs such that <math>a_{i_k}=b_{j_k},</math> understood to be totally ordered. That is, each individual subsequence <math>(i_k)</math> and <math>(j_k)</math> are ordered: <math>1\le i_1 < i_2<\cdots <i_r\le m</math> and likewise <math>1\le j_1 < j_2<\cdots <j_r\le n.</math> |
||
Line 86: | Line 99: | ||
== Ornstein Isomorphism Theorem == |
== Ornstein Isomorphism Theorem == |
||
The [[Ornstein isomorphism theorem]] states that two Bernoulli schemes with the same entropy are [[isomorphism of dynamical systems|isomorphic]].<ref |
The [[Ornstein isomorphism theorem]] states that two Bernoulli schemes with the same entropy are [[isomorphism of dynamical systems|isomorphic]].<ref name="OIT"/> The result is sharp,<ref>{{cite journal |
||
| first1=Christopher | last1=Hoffman |
|||
| title=A <math>K</math> Counterexample Machine |
|||
| journal=Transactions of the American Mathematical Society |
|||
| volume=351 |
|||
| year= 1999 |
|||
| pages=4263–4280 |
|||
| url=https://www.ams.org/journals/tran/1999-351-10/S0002-9947-99-02446-0/}}</ref> in that very similar, non-scheme systems, such as [[Kolmogorov automorphism]]s, do not have this property. |
|||
The Ornstein isomorphism theorem is in fact considerably deeper: it provides a simple criterion by which many different [[measure-preserving dynamical system]]s can be judged to be isomorphic to Bernoulli schemes. The result was surprising, as many systems previously believed to be unrelated proved to be isomorphic. These include all finite{{clarify|date=November 2010}} [[stationary stochastic process]]es, [[subshifts of finite type]], finite [[Markov chain]]s, [[Anosov flow]]s, and [[Sinai's billiards]]: these are all isomorphic to Bernoulli schemes. |
The Ornstein isomorphism theorem is in fact considerably deeper: it provides a simple criterion by which many different [[measure-preserving dynamical system]]s can be judged to be isomorphic to Bernoulli schemes. The result was surprising, as many systems previously believed to be unrelated proved to be isomorphic. These include all finite{{clarify|date=November 2010}} [[stationary stochastic process]]es, [[subshifts of finite type]], finite [[Markov chain]]s, [[Anosov flow]]s, and [[Sinai's billiards]]: these are all isomorphic to Bernoulli schemes. |
||
For the generalized case, the Ornstein isomorphism theorem still holds if the group ''G'' is a countably infinite [[amenable group]]. |
For the generalized case, the Ornstein isomorphism theorem still holds if the group ''G'' is a countably infinite [[amenable group]]. |
||
<ref>{{cite journal |
|||
<ref>D. Ornstein and B. Weiss. "Entropy and isomorphism theorems for actions of amenable groups." ''J. Analyse Math.'' '''48''' (1987), pp. 1–141.</ref><ref>Lewis Bowen (2011), "[https://arxiv.org/abs/1103.4424 Every countably infinite group is almost Ornstein]", ArXiv abs/1103.4424</ref> |
|||
| first1=Daniel | last1=Ornstein |
|||
| first2=Benjamin | last2=Weiss |
|||
| title=Entropy and isomorphism theorems for actions of amenable groups |
|||
| journal=Journal d'Analyse Mathématique |
|||
| volume=48 |
|||
| year=1987 |
|||
| pages=1–141 |
|||
| doi=10.1007/BF02790325 | doi-access=free}}</ref><ref>{{cite journal |
|||
| first1=Lewis | last1=Bowen |
|||
| year=2012 |
|||
| arxiv=1103.4424 |
|||
| title=Every countably infinite group is almost Ornstein |
|||
| journal=Contemporary Mathematics |
|||
| pages=67–78 |
|||
| volume=567}}</ref> |
|||
==Bernoulli automorphism== |
==Bernoulli automorphism== |
Revision as of 08:51, 4 May 2021
In mathematics, the Bernoulli scheme or Bernoulli shift is a generalization of the Bernoulli process to more than two possible outcomes.[1][2] Bernoulli schemes appear naturally in symbolic dynamics, and are thus important in the study of dynamical systems. Many important dynamical systems (such as Axiom A systems) exhibit a repellor that is the product of the Cantor set and a smooth manifold, and the dynamics on the Cantor set are isomorphic to that of the Bernoulli shift.[3] This is essentially the Markov partition. The term shift is in reference to the shift operator, which may be used to study Bernoulli schemes. The Ornstein isomorphism theorem[4][5] shows that Bernoulli shifts are isomorphic when their entropy is equal.
Definition
A Bernoulli scheme is a discrete-time stochastic process where each independent random variable may take on one of N distinct possible values, with the outcome i occurring with probability , with i = 1, ..., N, and
The sample space is usually denoted as
as a shorthand for
The associated measure is called the Bernoulli measure[6]
The σ-algebra on X is the product sigma algebra; that is, it is the (countable) direct product of the σ-algebras of the finite set {1, ..., N}. Thus, the triplet
is a measure space. A basis of is the cylinder sets. Given a cylinder set , its measure is
The equivalent expression, using the notation of probability theory, is
for the random variables
The Bernoulli scheme, as any stochastic process, may be viewed as a dynamical system by endowing it with the shift operator T where
Since the outcomes are independent, the shift preserves the measure, and thus T is a measure-preserving transformation. The quadruplet
is a measure-preserving dynamical system, and is called a Bernoulli scheme or a Bernoulli shift. It is often denoted by
The N = 2 Bernoulli scheme is called a Bernoulli process. The Bernoulli shift can be understood as a special case of the Markov shift, where all entries in the adjacency matrix are one, the corresponding graph thus being a clique.
Matches and metrics
The Hamming distance provides a natural metric on a Bernoulli scheme. Another important metric is the so-called metric, defined via a supremum over string matches.[7]
Let and be two strings of symbols. A match is a sequence M of pairs of indexes into the string, i.e. pairs such that understood to be totally ordered. That is, each individual subsequence and are ordered: and likewise
The -distance between and is
where the supremum is being taken over all matches between and . This satisfies the triangle inequality only when and so is not quite a true metric; despite this, it is commonly called a "distance" in the literature.
Generalizations
Most of the properties of the Bernoulli scheme follow from the countable direct product, rather than from the finite base space. Thus, one may take the base space to be any standard probability space , and define the Bernoulli scheme as
This works because the countable direct product of a standard probability space is again a standard probability space.
As a further generalization, one may replace the integers by a countable discrete group , so that
For this last case, the shift operator is replaced by the group action
for group elements and understood as a function (any direct product can be understood to be the set of functions , as this is the exponential object). The measure is taken as the Haar measure, which is invariant under the group action:
These generalizations are also commonly called Bernoulli schemes, as they still share most properties with the finite case.
Properties
Ya. Sinai demonstrated that the Kolmogorov entropy of a Bernoulli scheme is given by[8][9]
This may be seen as resulting from the general definition of the entropy of a Cartesian product of probability spaces, which follows from the asymptotic equipartition property. For the case of a general base space (i.e. a base space which is not countable), one typically considers the relative entropy. So, for example, if one has a countable partition of the base Y, such that , one may define the entropy as
In general, this entropy will depend on the partition; however, for many dynamical systems, it is the case that the symbolic dynamics is independent of the partition (or rather, there are isomorphisms connecting the symbolic dynamics of different partitions, leaving the measure invariant), and so such systems can have a well-defined entropy independent of the partition.
Ornstein Isomorphism Theorem
The Ornstein isomorphism theorem states that two Bernoulli schemes with the same entropy are isomorphic.[4] The result is sharp,[10] in that very similar, non-scheme systems, such as Kolmogorov automorphisms, do not have this property.
The Ornstein isomorphism theorem is in fact considerably deeper: it provides a simple criterion by which many different measure-preserving dynamical systems can be judged to be isomorphic to Bernoulli schemes. The result was surprising, as many systems previously believed to be unrelated proved to be isomorphic. These include all finite[clarification needed] stationary stochastic processes, subshifts of finite type, finite Markov chains, Anosov flows, and Sinai's billiards: these are all isomorphic to Bernoulli schemes.
For the generalized case, the Ornstein isomorphism theorem still holds if the group G is a countably infinite amenable group. [11][12]
Bernoulli automorphism
An invertible, measure-preserving transformation of a standard probability space (Lebesgue space) is called a Bernoulli automorphism if it isomorphic to a Bernoulli shift.[13]
Loosely Bernoulli
A system is termed "loosely Bernoulli" if it is Kakutani-equivalent to a Bernoulli shift; in the case of zero entropy, if it is Kakutani-equivalent to an irrational rotation of a circle.
See also
References
- ^ P. Shields, The theory of Bernoulli shifts, Univ. Chicago Press (1973)
- ^ Michael S. Keane, "Ergodic theory and subshifts of finite type", (1991), appearing as Chapter 2 in Ergodic Theory, Symbolic Dynamics and Hyperbolic Spaces, Tim Bedford, Michael Keane and Caroline Series, Eds. Oxford University Press, Oxford (1991). ISBN 0-19-853390-X
- ^ Pierre Gaspard, Chaos, scattering and statistical mechanics (1998), Cambridge University press
- ^ a b Ornstein, Donald (1970). "Bernoulli shifts with the same entropy are isomorphic". Advances in Mathematics. 4: 337–352. doi:10.1016/0001-8708(70)90029-0.
- ^ D.S. Ornstein (2001) [1994], "Ornstein isomorphism theorem", Encyclopedia of Mathematics, EMS Press
- ^ Klenke, Achim (2006). Probability Theory. Springer-Verlag. ISBN 978-1-84800-047-6.
- ^ Feldman, Jacob (1976). "New -automorphisms and a problem of Kakutani". Israel Journal of Mathematics. 24 (1): 16–38. doi:10.1007/BF02761426.
- ^ Ya.G. Sinai, (1959) "On the Notion of Entropy of a Dynamical System", Doklady of Russian Academy of Sciences 124, pp. 768–771.
- ^ Ya. G. Sinai, (2007) "Metric Entropy of Dynamical System"
- ^ Hoffman, Christopher (1999). "A Counterexample Machine". Transactions of the American Mathematical Society. 351: 4263–4280.
- ^ Ornstein, Daniel; Weiss, Benjamin (1987). "Entropy and isomorphism theorems for actions of amenable groups". Journal d'Analyse Mathématique. 48: 1–141. doi:10.1007/BF02790325.
- ^ Bowen, Lewis (2012). "Every countably infinite group is almost Ornstein". Contemporary Mathematics. 567: 67–78. arXiv:1103.4424.
- ^ Peter Walters (1982) An Introduction to Ergodic Theory, Springer-Verlag, ISBN 0-387-90599-5