|
|
| (309 intermediate revisions by more than 100 users not shown) |
| Line 1: |
Line 1: |
| 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 are important in the study of [[dynamical system]]s, as most such 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>{{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. Finite [[stationary stochastic process]]es are isomorphic to the Bernoulli shift; in this sense, Bernoulli shifts are [[universal property|universal]].
| | This is a preview for the new '''MathML rendering mode''' (with SVG fallback), which is availble in production for registered users. |
|
| |
|
| ==Definition==
| | If you would like use the '''MathML''' rendering mode, you need a wikipedia user account that can be registered here [[https://en.wikipedia.org/wiki/Special:UserLogin/signup]] |
| A Bernoulli scheme is a [[discrete-time]] [[stochastic process]] where each [[statistical independence|independent]] [[random variable]] may take on one of ''N'' distinct possible values, with the outcome ''i'' occurring with probability <math>p_i</math>, with ''i'' = 1, ..., ''N'', and
| | * Only registered users will be able to execute this rendering mode. |
| | * Note: you need not enter a email address (nor any other private information). Please do not use a password that you use elsewhere. |
|
| |
|
| :<math>\sum_{i=1}^N p_i = 1. </math> | | Registered users will be able to choose between the following three rendering modes: |
|
| |
|
| The [[sample space]] is usually denoted as
| | '''MathML''' |
| | :<math forcemathmode="mathml">E=mc^2</math> |
|
| |
|
| :<math>X=\{1,\ldots,N \}^\mathbb{Z}</math> | | <!--'''PNG''' (currently default in production) |
| | :<math forcemathmode="png">E=mc^2</math> |
|
| |
|
| as a short-hand for
| | '''source''' |
| | :<math forcemathmode="source">E=mc^2</math> --> |
|
| |
|
| :<math>X=\{ x=(\ldots,x_{-1},x_0,x_1,\ldots) : | | <span style="color: red">Follow this [https://en.wikipedia.org/wiki/Special:Preferences#mw-prefsection-rendering link] to change your Math rendering settings.</span> You can also add a [https://en.wikipedia.org/wiki/Special:Preferences#mw-prefsection-rendering-skin Custom CSS] to force the MathML/SVG rendering or select different font families. See [https://www.mediawiki.org/wiki/Extension:Math#CSS_for_the_MathML_with_SVG_fallback_mode these examples]. |
| x_k \in \{1,\ldots,N\} \; \forall k \in \mathbb{Z} \}.</math>
| |
|
| |
|
| The associated [[measure (mathematics)|measure]] is called the '''Bernoulli measure'''<ref>Achim Klenke, ''Probability Theory'' (2006) Springer-Verlag, ISBN 978-1-848000-047-6 doi:10.1007/978-1-848000-048-3</ref>
| | ==Demos== |
|
| |
|
| :<math>\mu = \{p_1,\ldots,p_N\}^\mathbb{Z}</math> | | Here are some [https://commons.wikimedia.org/w/index.php?title=Special:ListFiles/Frederic.wang demos]: |
|
| |
|
| The [[sigma-algebra|σ-algebra]] <math>\mathcal{A}</math> 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
| |
|
| |
|
| :<math>(X,\mathcal{A},\mu)</math> | | * accessibility: |
| | ** Safari + VoiceOver: [https://commons.wikimedia.org/wiki/File:VoiceOver-Mac-Safari.ogv video only], [[File:Voiceover-mathml-example-1.wav|thumb|Voiceover-mathml-example-1]], [[File:Voiceover-mathml-example-2.wav|thumb|Voiceover-mathml-example-2]], [[File:Voiceover-mathml-example-3.wav|thumb|Voiceover-mathml-example-3]], [[File:Voiceover-mathml-example-4.wav|thumb|Voiceover-mathml-example-4]], [[File:Voiceover-mathml-example-5.wav|thumb|Voiceover-mathml-example-5]], [[File:Voiceover-mathml-example-6.wav|thumb|Voiceover-mathml-example-6]], [[File:Voiceover-mathml-example-7.wav|thumb|Voiceover-mathml-example-7]] |
| | ** [https://commons.wikimedia.org/wiki/File:MathPlayer-Audio-Windows7-InternetExplorer.ogg Internet Explorer + MathPlayer (audio)] |
| | ** [https://commons.wikimedia.org/wiki/File:MathPlayer-SynchronizedHighlighting-WIndows7-InternetExplorer.png Internet Explorer + MathPlayer (synchronized highlighting)] |
| | ** [https://commons.wikimedia.org/wiki/File:MathPlayer-Braille-Windows7-InternetExplorer.png Internet Explorer + MathPlayer (braille)] |
| | ** NVDA+MathPlayer: [[File:Nvda-mathml-example-1.wav|thumb|Nvda-mathml-example-1]], [[File:Nvda-mathml-example-2.wav|thumb|Nvda-mathml-example-2]], [[File:Nvda-mathml-example-3.wav|thumb|Nvda-mathml-example-3]], [[File:Nvda-mathml-example-4.wav|thumb|Nvda-mathml-example-4]], [[File:Nvda-mathml-example-5.wav|thumb|Nvda-mathml-example-5]], [[File:Nvda-mathml-example-6.wav|thumb|Nvda-mathml-example-6]], [[File:Nvda-mathml-example-7.wav|thumb|Nvda-mathml-example-7]]. |
| | ** Orca: There is ongoing work, but no support at all at the moment [[File:Orca-mathml-example-1.wav|thumb|Orca-mathml-example-1]], [[File:Orca-mathml-example-2.wav|thumb|Orca-mathml-example-2]], [[File:Orca-mathml-example-3.wav|thumb|Orca-mathml-example-3]], [[File:Orca-mathml-example-4.wav|thumb|Orca-mathml-example-4]], [[File:Orca-mathml-example-5.wav|thumb|Orca-mathml-example-5]], [[File:Orca-mathml-example-6.wav|thumb|Orca-mathml-example-6]], [[File:Orca-mathml-example-7.wav|thumb|Orca-mathml-example-7]]. |
| | ** From our testing, ChromeVox and JAWS are not able to read the formulas generated by the MathML mode. |
|
| |
|
| is a [[measure space]]. The elements of <math>\mathcal{A}</math> are commonly called [[cylinder set]]s. Given a cylinder set <math>[x_0, x_1,\ldots,x_n]</math>, its measure is
| | ==Test pages == |
|
| |
|
| :<math>\mu\left([x_0, x_1,\ldots,x_n]\right)=
| | To test the '''MathML''', '''PNG''', and '''source''' rendering modes, please go to one of the following test pages: |
| \prod_{i=0}^n p_{x_i}</math>
| | *[[Displaystyle]] |
| The equivalent expression, using the notation of probability theory, is
| | *[[MathAxisAlignment]] |
| :<math>\mu\left([x_0, x_1,\ldots,x_n]\right)=
| | *[[Styling]] |
| \mathrm{Pr}(X_0=x_0, X_1=x_1, \ldots, X_n=x_n)</math>
| | *[[Linebreaking]] |
| for the random variables <math>\{X_k\}</math>
| | *[[Unique Ids]] |
| | *[[Help:Formula]] |
|
| |
|
| The Bernoulli scheme, as any stochastic process, may be viewed as a [[dynamical system]] by endowing it with the [[shift operator]] ''T'' where
| | *[[Inputtypes|Inputtypes (private Wikis only)]] |
| | | *[[Url2Image|Url2Image (private Wikis only)]] |
| :<math>Tx_k = x_{k+1}.</math>
| | ==Bug reporting== |
| | | If you find any bugs, please report them at [https://bugzilla.wikimedia.org/enter_bug.cgi?product=MediaWiki%20extensions&component=Math&version=master&short_desc=Math-preview%20rendering%20problem Bugzilla], or write an email to math_bugs (at) ckurs (dot) de . |
| Since the outcomes are independent, the shift preserves the measure, and thus ''T'' is a [[measure-preserving transformation]]. The quadruplet
| |
| | |
| :<math>(X,\mathcal{A},\mu, T)</math>
| |
| | |
| is a [[measure-preserving dynamical system]], and is called a '''Bernoulli scheme''' or a '''Bernoulli shift'''. It is often denoted by
| |
| | |
| :<math>BS(p)=BS(p_1,\ldots,p_N).</math>
| |
| | |
| 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 (graph theory)|clique]].
| |
| | |
| ==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]] <math>(Y,\mathcal{B},\nu)</math>, and define the Bernoulli scheme as
| |
| :<math>(X, \mathcal{A}, \mu)=(Y,\mathcal{B},\nu)^\mathbb{Z}</math>
| |
| 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 <math>\mathbb{Z}</math> by a [[countable]] [[discrete group]] <math>G</math>, so that
| |
| :<math>(X, \mathcal{A}, \mu)=(Y,\mathcal{B},\nu)^G</math> | |
| For this last case, the shift operator is replaced by the [[group action]]
| |
| :<math>gx(f)=x(g^{-1}f)</math>
| |
| for group elements <math>f,g\in G</math> and <math>x\in Y^G</math> understood as a function <math>x:G\to Y</math> (any direct product <math>Y^G</math> can be understood to be the set of functions <math>[G\to Y]</math>, as this is the [[exponential object]]). The measure <math>\mu</math> is taken as the [[Haar measure]], which is invariant under the group action:
| |
| :<math>\mu(gx)=\mu(x). \, </math>
| |
| 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<ref>Ya.G. Sinai, (1959) "On the Notion of Entropy of a Dynamical System", ''Doklady of Russian Academy of Sciences'' '''124''', pp. 768–771.</ref><ref>Ya. G. Sinai, (2007) "[http://web.math.princeton.edu/facultypapers/Sinai/MetricEntropy2.pdf Metric Entropy of Dynamical System]"</ref>
| |
| | |
| :<math>H = -\sum_{i=1}^N p_i \log p_i .</math>
| |
| | |
| 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 <math>(Y, \mathcal{B}, \nu)</math> (''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 a set|partition]] <math>Y'\subset Y</math> of the base ''Y'', such that <math>\nu(Y')=1</math>, one may define the entropy as
| |
| | |
| :<math>H_{Y'} = -\sum_{y'\in Y'} \nu(y') \log \nu(y') .</math>
| |
| | |
| In general, this entropy will depend on the partition; however, for many [[dynamical system]]s, 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 [[isomorphism of dynamical systems|isomorphic]].<ref>Donald Ornstein, "Bernoulli shifts with the same entropy are isomorphic", ''Advances in Math.'' '''4''' (1970), pp.337–352</ref> The result is sharp<ref>Christopher Hoffman, "[http://www.ams.org/journals/tran/1999-351-10/S0002-9947-99-02446-0/ A K counterexample machine]", ''Trans. Amer. Math. Soc.'' '''351''' (1999), pp 4263–4280 </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.
| |
| | |
| For the generalized case, the Ornstein isomorpism theorem still holds if the group ''G'' is a countably infinite [[amenable group]].
| |
| <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), "[http://arxiv.org/abs/1103.4424 Every countably infinite group is almost Ornstein]", ArXiv abs/1103.4424</ref>
| |
| | |
| ==Bernoulli automorphism==
| |
| An invertible, [[measure-preserving transformation]] of a [[standard probability space]] (Lebesgue space) is called a '''Bernoulli automorphism''' if it [[isomorphism of dynamical systems|isomorphic]] to a Bernoulli shift.<ref>Peter Walters (1982) ''An Introduction to Ergodic Theory'', Springer-Verlag, ISBN 0-387-90599-5</ref>
| |
| | |
| ==See also==
| |
| * [[Shift of finite type]]
| |
| * [[Markov chain]]
| |
| * [[Hidden Bernoulli model]]
| |
| | |
| ==References==
| |
| <references/>
| |
| | |
| {{DEFAULTSORT:Bernoulli Scheme}}
| |
| [[Category:Markov models]]
| |
| [[Category:Ergodic theory]]
| |
| [[Category:Stochastic processes]]
| |
| [[Category:Symbolic dynamics]]
| |
| | |
| | |
| [[fr:Décalage de Bernoulli (langage formel)]]
| |
| [[ru:Символическая динамика]]
| |
