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] shows that Bernoulli shifts are isomorphic when their entropy is equal.
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
pi
N | |
\sum | |
i=1 |
pi=1.
The sample space is usually denoted as
X=\{1,\ldots,N\}Z
as a shorthand for
X=\{x=(\ldots,x-1,x0,x1,\ldots):xk\in\{1,\ldots,N\} \forallk\inZ\}.
The associated measure is called the Bernoulli measure[5]
\mu=\{p1,\ldots,p
Z | |
N\} |
l{A}
(X,l{A},\mu)
is a measure space. A basis of
l{A}
[x0,x1,\ldots,xn]
\mu\left([x0,x1,\ldots,xn]\right)= \prod
n | |
i=0 |
p | |
xi |
\mu\left([x0,x1,\ldots,xn]\right)= Pr(X0=x0,X1=x1,\ldots,Xn=xn)
\{Xk\}
The Bernoulli scheme, as any stochastic process, may be viewed as a dynamical system by endowing it with the shift operator T where
T(xk)=xk+1.
Since the outcomes are independent, the shift preserves the measure, and thus T is a measure-preserving transformation. The quadruplet
(X,l{A},\mu,T)
is a measure-preserving dynamical system, and is called a Bernoulli scheme or a Bernoulli shift. It is often denoted by
BS(p)=BS(p1,\ldots,pN).
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.
The Hamming distance provides a natural metric on a Bernoulli scheme. Another important metric is the so-called
\overlinef
Let
A=a1a2 … am
B=b1b2 … bn
(ik,jk)
a | |
ik |
=b | |
jk |
,
(ik)
(jk)
1\lei1<i2< … <ir\lem
1\lej1<j2< … <jr\len.
The
\overlinef
A
B
\overlinef(A,B)=1-
2\sup|M| | |
m+n |
where the supremum is being taken over all matches
M
A
B
m=n,
(Y,l{B},\nu)
(X,l{A},\mu)=(Y,l{B},\nu)Z
As a further generalization, one may replace the integers
Z
G
(X,l{A},\mu)=(Y,l{B},\nu)G
gx(f)=x(g-1f)
f,g\inG
x\inYG
x:G\toY
YG
[G\toY]
\mu
\mu(gx)=\mu(x).
Ya. Sinai demonstrated that the Kolmogorov entropy of a Bernoulli scheme is given by[7] [8]
H=
N | |
-\sum | |
i=1 |
pilogpi.
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,l{B},\nu)
Y'\subsetY
\nu(Y')=1
HY'=-\sumy'\in\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.[4] 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]
An invertible, measure-preserving transformation of a standard probability space (Lebesgue space) is called a Bernoulli automorphism if it is isomorphic to a Bernoulli shift.[12]
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.
K
K