Bernoulli scheme

In

is equal.

Definition

A Bernoulli scheme is a

may take on one of N distinct possible values, with the outcome i occurring with probability ${\displaystyle p_{i}}$, with i = 1, ..., N, and

${\displaystyle \sum _{i=1}^{N}p_{i}=1.}$

The sample space is usually denoted as

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

as a shorthand for

${\displaystyle 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^[6]

${\displaystyle \mu =\{p_{1},\ldots ,p_{N}\}^{\mathbb {Z} }}$

The

${\displaystyle {\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

${\displaystyle (X,{\mathcal {A}},\mu )}$

is a measure space. A basis of ${\displaystyle {\mathcal {A}}}$ is the cylinder sets. Given a cylinder set ${\displaystyle [x_{0},x_{1},\ldots ,x_{n}]}$, its measure is

${\displaystyle \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

${\displaystyle \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 ${\displaystyle \{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

${\displaystyle T(x_{k})=x_{k+1}.}$

Since the outcomes are independent, the shift preserves the measure, and thus T is a

. The quadruplet

${\displaystyle (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

${\displaystyle BS(p)=BS(p_{1},\ldots ,p_{N}).}$

The N = 2 Bernoulli scheme is called a

.

Matches and metrics

The Hamming distance provides a natural metric on a Bernoulli scheme. Another important metric is the so-called ${\displaystyle {\overline {f}}}$ metric, defined via a supremum over string matches.^[7]

Let ${\displaystyle A=a_{1}a_{2}\cdots a_{m}}$ and ${\displaystyle B=b_{1}b_{2}\cdots b_{n}}$ be two strings of symbols. A match is a sequence M of pairs ${\displaystyle (i_{k},j_{k})}$ of indexes into the string, i.e. pairs such that ${\displaystyle a_{i_{k}}=b_{j_{k}},}$ understood to be totally ordered. That is, each individual subsequence ${\displaystyle (i_{k})}$ and ${\displaystyle (j_{k})}$ are ordered: ${\displaystyle 1\leq i_{1}<i_{2}<\cdots <i_{r}\leq m}$ and likewise ${\displaystyle 1\leq j_{1}<j_{2}<\cdots <j_{r}\leq n.}$

The ${\displaystyle {\overline {f}}}$-distance between ${\displaystyle A}$ and ${\displaystyle B}$ is

${\displaystyle {\overline {f}}(A,B)=1-{\frac {2\sup |M|}{m+n}}}$

where the supremum is being taken over all matches ${\displaystyle M}$ between ${\displaystyle A}$ and ${\displaystyle B}$. This satisfies the triangle inequality only when ${\displaystyle m=n,}$ 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 ${\displaystyle (Y,{\mathcal {B}},\nu )}$, and define the Bernoulli scheme as

${\displaystyle (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 integers ${\displaystyle \mathbb {Z} }$ by a

${\displaystyle G}$, so that

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

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

group action

${\displaystyle gx(f)=x(g^{-1}f)}$

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

${\displaystyle \mu (gx)=\mu (x).\,}$

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

Properties

${\displaystyle 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 ${\displaystyle (Y,{\mathcal {B}},\nu )}$ (i.e. a base space which is not countable), one typically considers the

${\displaystyle Y'\subset Y}$ of the base Y, such that ${\displaystyle \nu (Y')=1}$, one may define the entropy as

${\displaystyle 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.

Ornstein isomorphism theorem

The

, do not have this property.

The Ornstein isomorphism theorem is in fact considerably deeper: it provides a simple criterion by which many different

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,

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

• Shift of finite type
• Markov chain
• Hidden Bernoulli model

References