Bernoulli process

From Wikipedia, the free encyclopedia

Jump to navigation Jump to search

Random process of binary (boolean) random variables

This article includes a list of references, but its sources remain unclear because it has insufficient inline citations. Please help to improve this article by introducing more precise citations. (September 2011) (Learn how and when to remove this template message)

In probability and statistics, a Bernoulli process (named after Jacob Bernoulli) is a finite or infinite sequence of binary random variables, so it is a discrete-time stochastic process that takes only two values, canonically 0 and 1. The component Bernoulli variables X_i are identically distributed and independent. Prosaically, a Bernoulli process is a repeated coin flipping, possibly with an unfair coin (but with consistent unfairness). Every variable X_i in the sequence is associated with a Bernoulli trial or experiment. They all have the same Bernoulli distribution. Much of what can be said about the Bernoulli process can also be generalized to more than two outcomes (such as the process for a six-sided dice); this generalization is known as the Bernoulli scheme.

The problem of determining the process, given only a limited sample of Bernoulli trials, may be called the problem of checking whether a coin is fair.

Contents

• 1 Definition
  • 1.1 Interpretation
• 2 Formal definition
• 3 Law of large numbers, binomial distribution and central limit theorem
• 4 Dynamical system
• 5 Bernoulli sequence
• 6 Randomness extraction
  • 6.1 Basic von Neumann extractor
  • 6.2 Iterated von Neumann extractor
• 7 References
• 8 Further reading
• 9 External links

Definition[edit]

A Bernoulli process is a finite or infinite sequence of independent random variables X₁, X₂, X₃, ..., such that

• for each i, the value of X_i is either 0 or 1;
• for all values of i, the probability p that X_i = 1 is the same.

In other words, a Bernoulli process is a sequence of independent identically distributed Bernoulli trials.

Independence of the trials implies that the process is memoryless. Given that the probability p is known, past outcomes provide no information about future outcomes. (If p is unknown, however, the past informs about the future indirectly, through inferences about p.)

If the process is infinite, then from any point the future trials constitute a Bernoulli process identical to the whole process, the fresh-start property.

Interpretation[edit]

The two possible values of each X_i are often called "success" and "failure". Thus, when expressed as a number 0 or 1, the outcome may be called the number of successes on the ith "trial".

Two other common interpretations of the values are true or false and yes or no. Under any interpretation of the two values, the individual variables X_i may be called Bernoulli trials with parameter p.

In many applications time passes between trials, as the index i increases. In effect, the trials X₁, X₂, ... X_i, ... happen at "points in time" 1, 2, ..., i, .... That passage of time and the associated notions of "past" and "future" are not necessary, however. Most generally, any X_i and X_j in the process are simply two from a set of random variables indexed by {1, 2, ..., n}, the finite cases, or by {1, 2, 3, ...}, the infinite cases.

One experiment with only two possible outcomes, often referred to as "success" and "failure", usually encoded as 1 and 0, is used to be modeled as a Bernoulli distribution.^[1] Several random variables and probability distributions beside the Bernoullis may be derived from the Bernoulli process:

• The number of successes in the first n trials, which has a binomial distribution B(n, p)
• The number of failures needed to get r successes, which has a negative binomial distribution NB(r, p)
• The number of failures needed to get one success, which has a geometric distribution NB(1, p), a special case of the negative binomial distribution

The negative binomial variables may be interpreted as random waiting times.

Formal definition[edit]

The Bernoulli process can be formalized in the language of probability spaces as a random sequence of independent realisations of a random variable that can take values of heads or tails. The state space for an individual value is denoted by ${\displaystyle 2=\{H,T\}.}$

Specifically, one considers the countably infinite direct product of copies of ${\displaystyle 2=\{H,T\}}$. It is common to examine either the one-sided set ${\displaystyle \Omega =2^{\mathbb {N} }=\{H,T\}^{\mathbb {N} }}$ or the two-sided set ${\displaystyle \Omega =2^{\mathbb {Z} }}$. There is a natural topology on this space, called the product topology. The sets in this topology are finite sequences of coin flips, that is, finite-length strings of H and T (H stands for heads and T stands for tails), with the rest of (infinitely long) sequence taken as "don't care". These sets of finite sequences are referred to as cylinder sets in the product topology. The set of all such strings form a sigma algebra, specifically, a Borel algebra. This algebra is then commonly written as ${\displaystyle (\Omega ,{\mathcal {F}})}$ where the elements of ${\displaystyle {\mathcal {F}}}$ are the finite-length sequences of coin flips (the cylinder sets).

If the chances of flipping heads or tails are given by the probabilities ${\displaystyle \{p,1-p\}}$, then one can define a natural measure on the product space, given by ${\displaystyle P=\{p,1-p\}^{\mathbb {N} }}$ (or by ${\displaystyle P=\{p,1-p\}^{\mathbb {Z} }}$ for the two-sided process). In another word, if a discrete random variable X has a Bernoulli distribution with parameter p, where 0 ≤ p ≤ 1, and its probability mass function is given by

${\displaystyle pX(1)=P(X=1)=p}$ and ${\displaystyle pX(0)=P(X=0)=1-p}$.

We denote this distribution by Ber(p).^[2]

Given a cylinder set, that is, a specific sequence of coin flip results ${\displaystyle [\omega _{1},\omega _{2},\cdots \omega _{n}]}$ at times ${\displaystyle 1,2,\cdots ,n}$, the probability of observing this particular sequence is given by

${\displaystyle P([\omega _{1},\omega _{2},\cdots ,\omega _{n}])=p^{k}(1-p)^{n-k}}$

where k is the number of times that H appears in the sequence, and n−k is the number of times that T appears in the sequence. There are several different kinds of notations for the above; a common one is to write

${\displaystyle P(X_{1}=x_{1},X_{2}=x_{2},\cdots ,X_{n}=x_{n})=p^{k}(1-p)^{n-k}}$

where each ${\displaystyle X_{i}}$ is a binary-valued random variable with ${\displaystyle x_{i}=[\omega _{i}=H]}$ in Iverson bracket notation, meaning either ${\displaystyle 1}$ if ${\displaystyle \omega _{i}=H}$ or ${\displaystyle 0}$ if ${\displaystyle \omega _{i}=T}$. This probability ${\displaystyle P}$ is commonly called the Bernoulli measure.^[3]

Note that the probability of any specific, infinitely long sequence of coin flips is exactly zero; this is because ${\displaystyle \lim _{n\to \infty }p^{n}=0}$, for any ${\displaystyle 0\leq p<1}$. A probability equal to 1 implies that any given infinite sequence has measure zero. Nevertheless, one can still say that some classes of infinite sequences of coin flips are far more likely than others, this is given by the asymptotic equipartition property.

To conclude the formal definition, a Bernoulli process is then given by the probability triple ${\displaystyle (\Omega ,{\mathcal {F}},P)}$, as defined above.

Law of large numbers, binomial distribution and central limit theorem[edit]

Main articles: Law of large numbers, Central limit theorem, and Binomial distribution

Let us assume the canonical process with ${\displaystyle H}$ represented by ${\displaystyle 1}$ and ${\displaystyle T}$ represented by ${\displaystyle 0}$. The law of large numbers states that, on the average of the sequence, i.e., ${\displaystyle {\bar {X}}_{n}:={\frac {1}{n}}\sum _{i=1}^{n}X_{i}}$, will approach the expected value almost certainly, that is, the events which do not satisfy this limit have zero probability. The expectation value of flipping heads, assumed to be represented by 1, is given by ${\displaystyle p}$. In fact, one has

${\displaystyle \mathbb {E} [X_{i}]=\mathbb {P} ([X_{i}=1])=p,}$

for any given random variable ${\displaystyle X_{i}}$ out of the infinite sequence of Bernoulli trials that compose the Bernoulli process.

One is often interested in knowing how often one will observe H in a sequence of n coin flips. This is given by simply counting: Given n successive coin flips, that is, given the set of all possible strings of length n, the number N(k,n) of such strings that contain k occurrences of H is given by the binomial coefficient

${\displaystyle N(k,n)={n \choose k}={\frac {n!}{k!(n-k)!}}}$

If the probability of flipping heads is given by p, then the total probability of seeing a string of length n with k heads is

${\displaystyle \mathbb {P} ([S_{n}=k])={n \choose k}p^{k}(1-p)^{n-k},}$

where ${\displaystyle S_{n}=\sum _{i=1}^{n}X_{i}}$. The probability measure thus defined is known as the Binomial distribution.

As we can see from the above formula that, if n=1, the Binomial distribution will turn into a Bernoulli distribution. So we can know that the Bernoulli distribution is exactly a special case of Binomial distribution when n equals to 1.

Of particular interest is the question of the value of ${\displaystyle S_{n}}$ for a sufficiently long sequences of coin flips, that is, for the limit ${\displaystyle n\to \infty }$. In this case, one may make use of Stirling's approximation to the factorial, and write

${\displaystyle n!={\sqrt {2\pi n}}\;n^{n}e^{-n}\left(1+{\mathcal {O}}\left({\frac {1}{n}}\right)\right)}$

Inserting this into the expression for P(k,n), one obtains the Normal distribution; this is the content of the central limit theorem, and this is the simplest example thereof.

The combination of the law of large numbers, together with the central limit theorem, leads to an interesting and perhaps surprising result: the asymptotic equipartition property. Put informally, one notes that, yes, over many coin flips, one will observe H exactly p fraction of the time, and that this corresponds exactly with the peak of the Gaussian. The asymptotic equipartition property essentially states that this peak is infinitely sharp, with infinite fall-off on either side. That is, given the set of all possible infinitely long strings of H and T occurring in the Bernoulli process, this set is partitioned into two: those strings that occur with probability 1, and those that occur with probability 0. This partitioning is known as the Kolmogorov 0-1 law.

The size of this set is interesting, also, and can be explicitly determined: the logarithm of it is exactly the entropy of the Bernoulli process. Once again, consider the set of all strings of length n. The size of this set is ${\displaystyle 2^{n}}$. Of these, only a certain subset are likely; the size of this set is ${\displaystyle 2^{nH}}$ for ${\displaystyle H\leq 1}$. By using Stirling's approximation, putting it into the expression for P(k,n), solving for the location and width of the peak, and finally taking ${\displaystyle n\to \infty }$ one finds that

${\displaystyle H=-p\log _{2}p-(1-p)\log _{2}(1-p)}$

This value is the Bernoulli entropy of a Bernoulli process. Here, H stands for entropy; do not confuse it with the same symbol H standing for heads.

John von Neumann posed a curious question about the Bernoulli process: is it ever possible that a given process is isomorphic to another, in the sense of the isomorphism of dynamical systems? The question long defied analysis, but was finally and completely answered with the Ornstein isomorphism theorem. This breakthrough resulted in the understanding that the Bernoulli process is unique and universal; in a certain sense, it is the single most random process possible; nothing is 'more' random than the Bernoulli process (although one must be careful with this informal statement; certainly, systems that are mixing are, in a certain sense, 'stronger' than the Bernoulli process, which is merely ergodic but not mixing. However, such processes do not consist of independent random variables: indeed, many purely deterministic, non-random systems can be mixing).

Dynamical system[edit]

Main article: Bernoulli scheme

The Bernoulli process can also be understood to be a dynamical system, specifically, a measure-preserving dynamical system. This arises because there is a natural translation symmetry on the (two-sided) product space ${\displaystyle \Omega =2^{\mathbb {Z} }}$ given by the shift operator

${\displaystyle TX_{i}=X_{i+1}}$

The measure is translation-invariant; that is, given any cylinder set ${\displaystyle \omega \in \Omega }$, one has

${\displaystyle P(T\omega )=P(\omega )}$

and thus the Bernoulli measure is a Haar measure.

The shift operator should be understood to be an operator acting on the sigma algebra ${\displaystyle (\Omega ,{\mathcal {F}})}$, so that one has

${\displaystyle T:{\mathcal {F}}\to {\mathcal {F}}}$

In this guise, the shift operator is known as the transfer operator or the Ruelle-Frobenius-Perron operator. It is interesting to consider the eigenfunctions of this operator, and how they differ when restricted to different subspaces of ${\displaystyle (\Omega ,{\mathcal {F}})}$. When restricted to the standard topology of the real numbers, the eigenfunctions are curiously the Bernoulli polynomials!^[4][5] This coincidence of naming was presumably not known to Bernoulli.

Bernoulli sequence[edit]

The term Bernoulli sequence is often used informally to refer to a realization of a Bernoulli process. However, the term has an entirely different formal definition as given below.

Suppose a Bernoulli process formally defined as a single random variable (see preceding section). For every infinite sequence x of coin flips, there is a sequence of integers

${\displaystyle \mathbb {Z} ^{x}=\{n\in \mathbb {Z} :X_{n}(x)=1\}\,}$

called the Bernoulli sequence^{[verification needed]} associated with the Bernoulli process. For example, if x represents a sequence of coin flips, then the associated Bernoulli sequence is the list of natural numbers or time-points for which the coin toss outcome is heads.

So defined, a Bernoulli sequence ${\displaystyle \mathbb {Z} ^{x}}$ is also a random subset of the index set, the natural numbers ${\displaystyle \mathbb {N} }$.

Almost all Bernoulli sequences ${\displaystyle \mathbb {Z} ^{x}}$ are ergodic sequences.^{[verification needed]}

Randomness extraction[edit]

Main article: Randomness extractor

From any Bernoulli process one may derive a Bernoulli process with p = 1/2 by the von Neumann extractor, the earliest randomness extractor, which actually extracts uniform randomness.

Basic von Neumann extractor[edit]

Represent the observed process as a sequence of zeroes and ones, or bits, and group that input stream in non-overlapping pairs of successive bits, such as (11)(00)(10)... . Then for each pair,

• if the bits are equal, discard;
• if the bits are not equal, output the first bit.

This table summarizes the computation.

input	output
00	discard
01	0
10	1
11	discard

For example, an input stream of eight bits 10011011 would by grouped into pairs as (10)(01)(10)(11). Then, according to the table above, these pairs are translated into the output of the procedure: (1)(0)(1)() (=101).

In the output stream 0 and 1 are equally likely, as 10 and 01 are equally likely in the original, both having probability p(1−p) = (1−p)p. This extraction of uniform randomness does not require the input trials to be independent, only uncorrelated. More generally, it works for any exchangeable sequence of bits: all sequences that are finite rearrangements are equally likely.

The von Neumann extractor uses two input bits to produce either zero or one output bits, so the output is shorter than the input by a factor of at least 2. On average the computation discards proportion p² + (1 − p)² of the input pairs(00 and 11), which is near one when p is near zero or one, and is minimized at 1/4 when p = 1/2 for the original process (in which case the output stream is 1/4 the length of the input stream on average).

Von Neumann (classical) main operation pseudocode:

if (Bit1 ≠ Bit2) {     output(Bit1)  }  

Iterated von Neumann extractor[edit]

This section possibly contains inappropriate or misinterpreted citations that do not verify the text. Relevant discussion may be found on the talk page. Please help improve this article by checking for citation inaccuracies. (January 2014) (Learn how and when to remove this template message)

This decrease in efficiency, or waste of randomness present in the input stream, can be mitigated by iterating the algorithm over the input data. This way the output can be made to be "arbitrarily close to the entropy bound".^[6]

The iterated version of the von Neumann algorithm, also known as Advanced Multi-Level Strategy (AMLS)^[7], was introduced by Yuval Peres in 1992.^[6] It works recursively, recycling "wasted randomness" from two sources: the sequence of discard/non-discard, and the values of discarded pairs (0 for 00, and 1 for 11). Intuitively, it relies on the fact that, given the sequence already generated, both of those sources are still exchangeable sequences of bits, and thus eligible for another round of extraction. While such generation of additional sequences can be iterated infinitely to extract all available entropy, an infinite amount of computational resources is required, therefore the number of iterations is typically fixed to a low value – this value either fixed in advance, or calculated at runtime.

More concretely, on an input sequence, the algorithm consumes the input bits in pairs, generating output together with two new sequences:

input	output	new sequence 1	new sequence 2
00	none	0	0
01	0	1	none
10	1	1	none
11	none	0	1

(If the length of the input is odd, the last bit is completely discarded.) Then the algorithm is applied recursively to each of the two new sequences, until the input is empty.

Example: The input stream from above, 10011011, is processed this way:

step number	input	output	new sequence 1	new sequence 2
0	(10)(01)(10)(11)	(1)(0)(1)()	(1)(1)(1)(0)	()()()(1)
1	(11)(10)	()(1)	(0)(1)	(1)()
1.1	(01)	(0)	(1)	()
1.1.1	1	none	none	none
1.2	1	none	none	none
2	1	none	none	none

From the step of 1 on, the input becomes the new sequence1 of the last step to move on in this process. The output is therefore (101)(1)(0)()()() (=10110), so that from the eight bits of input five bits of output were generated, as opposed to three bits through the basic algorithm above. The constant output of exactly 2 bits per round (compared with a variable 0 to 1 bits in classical VN) also allows for constant-time implementations which are resistant to timing attacks.

Von Neumann–Peres (iterated) main operation pseudocode:

if (Bit1 ≠ Bit2) {     output(1, Sequence1)     output(Bit1)  } else {     output(0, Sequence1)     output(Bit1, Sequence2)  }  

Another tweak was presented in 2016, based on the observation that the Sequence2 channel doesn't provide much throughput, and a hardware implementation with a finite number of levels can benefit from discarding it earlier in exchange for processing more levels of Sequence1.^[8]

References[edit]

1. ^ A modern introduction to probability and statistics. pp. 45–46. ISBN 9781852338961.
2. ^ A modern introduction to probability and statistics. pp. 45–46. ISBN 9781852338961.
3. ^ Klenke, Achim (2006). Probability Theory. Springer-Verlag. ISBN 978-1-84800-047-6.
4. ^ Pierre Gaspard, "r-adic one-dimensional maps and the Euler summation formula", Journal of Physics A, 25 (letter) L483-L485 (1992).
5. ^ Dean J. Driebe, Fully Chaotic Maps and Broken Time Symmetry, (1999) Kluwer Academic Publishers, Dordrecht Netherlands ISBN 0-7923-5564-4
6. ^ ^{a b} Peres, Yuval (March 1992). "Iterating Von Neumann's Procedure for Extracting Random Bits" (PDF). The Annals of Statistics. 20 (1): 590–597. doi:10.1214/aos/1176348543. Retrieved 30 May 2013.
7. ^ "Tossing a Biased Coin" (PDF). eecs.harvard.edu. Retrieved 2018-07-28.
8. ^ Rožić, Vladimir; Yang, Bohan; Dehaene, Wim; Verbauwhede, Ingrid (3–5 May 2016). Iterating Von Neumann's post-processing under hardware constraints (PDF). 2016 IEEE International Symposium on Hardware Oriented Security and Trust (HOST). Maclean, VA, USA. doi:10.1109/HST.2016.7495553\.

Further reading[edit]

• Carl W. Helstrom, Probability and Stochastic Processes for Engineers, (1984) Macmillan Publishing Company, New York ISBN 0-02-353560-1.

External links[edit]

• Using a binary tree diagram for describing a Bernoulli process

v t e Stochastic processes
Discrete time	Bernoulli process Branching process Chinese restaurant process Galton–Watson process Independent and identically distributed random variables Markov chain Moran process Random walk Loop-erased Self-avoiding Biased Maximal entropy
Continuous time	Bessel process Birth–death process Brownian motion Bridge Excursion Fractional Geometric Meander Cauchy process Contact process Continuous-time random walk Cox process Diffusion process Empirical process Feller process Fleming–Viot process Gamma process Geometric process Hunt process Interacting particle systems Itô diffusion Itô process Jump diffusion Jump process Lévy process Local time Markov additive process McKean–Vlasov process Ornstein–Uhlenbeck process Poisson process Compound Non-homogeneous Point process Schramm–Loewner evolution Semimartingale Sigma-martingale Stable process Superprocess Telegraph process Variance gamma process Wiener process Wiener sausage
Both	Branching process Galves–Löcherbach model Gaussian process Hidden Markov model (HMM) Markov process Martingale Differences Local Sub- Super- Random dynamical system Regenerative process Renewal process Stochastic chains with memory of variable length White noise
Fields and other	Dirichlet process Gaussian random field Gibbs measure Hopfield model Ising model Potts model Boolean network Markov random field Percolation Pitman–Yor process Point process Cox Poisson Random field Random graph
Time series models	Autoregressive conditional heteroskedasticity (ARCH) model Autoregressive integrated moving average (ARIMA) model Autoregressive (AR) model Autoregressive–moving-average (ARMA) model Generalized autoregressive conditional heteroskedasticity (GARCH) model Moving-average (MA) model
Financial models	Black–Derman–Toy Black–Karasinski Black–Scholes Chen Constant elasticity of variance (CEV) Cox–Ingersoll–Ross (CIR) Garman–Kohlhagen Heath–Jarrow–Morton (HJM) Heston Ho–Lee Hull–White LIBOR market Rendleman–Bartter SABR volatility Vašíček Wilkie
Actuarial models	Bühlmann Cramér–Lundberg Risk process Sparre–Anderson
Queueing models	Bulk Fluid Generalized queueing network M/G/1 M/M/1 M/M/c
Properties	Càdlàg paths Continuous Continuous paths Ergodic Exchangeable Feller-continuous Gauss–Markov Markov Mixing Piecewise deterministic Predictable Progressively measurable Self-similar Stationary Time-reversible
Limit theorems	Central limit theorem Donsker's theorem Doob's martingale convergence theorems Ergodic theorem Fisher–Tippett–Gnedenko theorem Large deviation principle Law of large numbers (weak/strong) Law of the iterated logarithm Maximal ergodic theorem Sanov's theorem
Inequalities	Burkholder–Davis–Gundy Doob's martingale Kunita–Watanabe
Tools	Cameron–Martin formula Convergence of random variables Doléans-Dade exponential Doob decomposition theorem Doob–Meyer decomposition theorem Doob's optional stopping theorem Dynkin's formula Feynman–Kac formula Filtration Girsanov theorem Infinitesimal generator Itô integral Itô's lemma Karhunen–Loève_theorem Kolmogorov continuity theorem Kolmogorov extension theorem Lévy–Prokhorov metric Malliavin calculus Martingale representation theorem Optional stopping theorem Prokhorov's theorem Quadratic variation Reflection principle Skorokhod integral Skorokhod's representation theorem Skorokhod space Snell envelope Stochastic differential equation Tanaka Stopping time Stratonovich integral Uniform integrability Usual hypotheses Wiener space Classical Abstract
Disciplines	Actuarial mathematics Econometrics Ergodic theory Extreme value theory (EVT) Large deviations theory Mathematical finance Mathematical statistics Probability theory Queueing theory Renewal theory Ruin theory Statistics System on Chip design Stochastic analysis Time series analysis Machine learning
List of topics Category

Retrieved from "https://en.wikipedia.org/w/index.php?title=Bernoulli_process&oldid=929565866"

Categories:

• Stochastic processes

Hidden categories:

• Use American English from February 2019
• All Wikipedia articles written in American English
• Articles with short description
• Articles lacking in-text citations from September 2011
• All articles lacking in-text citations
• All pages needing factual verification
• Wikipedia articles needing factual verification from March 2010
• Articles lacking reliable references from January 2014
• All articles lacking reliable references

Navigation menu

Personal tools

• Not logged in
• Talk
• Contributions
• Create account
• Log in

Namespaces

• Article
• Talk

Variants

Views

• Read
• Edit
• View history

More

Search

Navigation

• Main page
• Contents
• Featured content
• Current events
• Random article
• Donate to Wikipedia
• Wikipedia store

Interaction

• Help
• About Wikipedia
• Community portal
• Recent changes
• Contact page

Tools

• What links here
• Related changes
• Upload file
• Special pages
• Permanent link
• Page information
• Wikidata item
• Cite this page

Print/export

• Create a book
• Download as PDF
• Printable version

Languages

• Català
• Deutsch
• Español
• Euskara
• فارسی
• Français
• 한국어
• Italiano
• 日本語
• Polski
• Português
• Slovenščina
• 中文

Edit links

• This page was last edited on 6 December 2019, at 17:38 (UTC).
• Text is available under the Creative Commons Attribution-ShareAlike License; additional terms may apply. By using this site, you agree to the Terms of Use and Privacy Policy. Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc., a non-profit organization.

• Privacy policy
• About Wikipedia
• Disclaimers
• Contact Wikipedia
• Developers
• Statistics
• Cookie statement
• Mobile view

• 
•