World Library  
Flag as Inappropriate
Email this Article

Bernoulli scheme

Article Id: WHEBN0002580555
Reproduction Date:

Title: Bernoulli scheme  
Author: World Heritage Encyclopedia
Language: English
Subject: Symbolic dynamics, Ergodic theory, Markov models, Donald Samuel Ornstein, Bernoulli process
Collection: Ergodic Theory, Markov Models, Stochastic Processes, Symbolic Dynamics
Publisher: World Heritage Encyclopedia

Bernoulli scheme

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 are important in the study of dynamical systems, as most such 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] shows that Bernoulli shifts are isomorphic when their entropy is equal.


  • Definition 1
  • Generalizations 2
  • Properties 3
  • Bernoulli automorphism 4
  • See also 5
  • References 6


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 p_i, with i = 1, ..., N, and

\sum_{i=1}^N p_i = 1.

The sample space is usually denoted as

X=\{1,\ldots,N \}^\mathbb{Z}

as a shorthand for

X=\{ x=(\ldots,x_{-1},x_0,x_1,\ldots) : x_k \in \{1,\ldots,N\} \; \forall k \in \mathbb{Z} \}.

The associated measure is called the Bernoulli measure[5]

\mu = \{p_1,\ldots,p_N\}^\mathbb{Z}

The σ-algebra \mathcal{A} 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 \mathcal{A} is the cylinder sets. Given a cylinder set [x_0, x_1,\ldots,x_n], its measure is

\mu\left([x_0, x_1,\ldots,x_n]\right)= \prod_{i=0}^n p_{x_i}

The equivalent expression, using the notation of probability theory, is

\mu\left([x_0, x_1,\ldots,x_n]\right)= \mathrm{Pr}(X_0=x_0, X_1=x_1, \ldots, X_n=x_n)

for the random variables \{X_k\}

The Bernoulli scheme, as any stochastic process, may be viewed as a dynamical system by endowing it with the shift operator T where

Tx_k = x_{k+1}.

Since the outcomes are independent, the shift preserves the measure, and thus T is a measure-preserving transformation. The quadruplet

(X,\mathcal{A},\mu, T)

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.


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 (Y,\mathcal{B},\nu), and define the Bernoulli scheme as

(X, \mathcal{A}, \mu)=(Y,\mathcal{B},\nu)^\mathbb{Z}

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 in integers \mathbb{Z} by a countable discrete group G, so that

(X, \mathcal{A}, \mu)=(Y,\mathcal{B},\nu)^G

For this last case, the shift operator is replaced by the group action


for group elements f,g\in G and x\in Y^G understood as a function x:G\to Y (any direct product Y^G can be understood to be the set of functions [G\to Y], as this is the exponential object). The measure \mu is taken as the Haar measure, which is invariant under the group action:

\mu(gx)=\mu(x). \,

These generalizations are also commonly called Bernoulli schemes, as they still share most properties with the finite case.


Ya. Sinai demonstrated that the Kolmogorov entropy of a Bernoulli scheme is given by[6][7]

H = -\sum_{i=1}^N p_i \log p_i .

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 (Y, \mathcal{B}, \nu) (i.e. a base space which is not countable), one typically considers the relative entropy. So, for example, if one has a countable partition Y'\subset Y of the base Y, such that \nu(Y')=1, one may define the entropy as

H_{Y'} = -\sum_{y'\in Y'} \nu(y') \log \nu(y') .

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.

The Ornstein isomorphism theorem states that two Bernoulli schemes with the same entropy are isomorphic.[8] The result is sharp,[9] 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 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. [10][11]

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.[12]

See also


  1. ^ P. Shields, The theory of Bernoulli shifts, Univ. Chicago Press (1973)
  2. ^ 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
  3. ^ Pierre Gaspard, Chaos, scattering and statistical mechanics(1998), Cambridge University press
  4. ^ D.S. Ornstein (2001), "Ornstein isomorphism theorem", in Hazewinkel, Michiel,  
  5. ^ Klenke, Achim (2006). Probability Theory. Springer-Verlag.  
  6. ^ Ya.G. Sinai, (1959) "On the Notion of Entropy of a Dynamical System", Doklady of Russian Academy of Sciences 124, pp. 768–771.
  7. ^ Ya. G. Sinai, (2007) "Metric Entropy of Dynamical System"
  8. ^ Donald Ornstein, "Bernoulli shifts with the same entropy are isomorphic", Advances in Math. 4 (1970), pp.337–352
  9. ^ Christopher Hoffman, "A K counterexample machine", Trans. Amer. Math. Soc. 351 (1999), pp 4263–4280
  10. ^ D. Ornstein and B. Weiss. "Entropy and isomorphism theorems for actions of amenable groups." J. Analyse Math. 48 (1987), pp. 1–141.
  11. ^ Lewis Bowen (2011), "Every countably infinite group is almost Ornstein", ArXiv abs/1103.4424
  12. ^ Peter Walters (1982) An Introduction to Ergodic Theory, Springer-Verlag, ISBN 0-387-90599-5
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.

Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.