Bernoulli process

This article includes a list of general references, but it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (September 2011) (Learn how and when to remove this template message)

Part of a series on statistics
Probability theory
Probability Axioms Determinism System Indeterminism Randomness
Probability space Sample space Event Collectively exhaustive events Elementary event Mutual exclusivity Outcome Singleton Experiment Bernoulli trial Probability distribution Bernoulli distribution Binomial distribution Exponential distribution Normal distribution Pareto distribution Poisson distribution Probability measure Random variable Bernoulli process Continuous or discrete Expected value Variance Markov chain Observed value Random walk Stochastic process
Complementary event Joint probability Marginal probability Conditional probability
Independence Conditional independence Law of total probability Law of large numbers Bayes' theorem Boole's inequality
Venn diagram Tree diagram
v t e

In

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.

Definition

A Bernoulli process is a finite or infinite sequence of

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

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, can 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

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\}.}$

Borel algebra

Consider the

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

Borel algebra

. This algebra is then commonly written as ${\displaystyle (\Omega ,{\mathcal {B}})}$ where the elements of ${\displaystyle {\mathcal {B}}}$ are the finite-length sequences of coin flips (the cylinder sets).

Bernoulli measure

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

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

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

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 the average of the sequence, i.e., ${\displaystyle {\bar {X}}_{n}:={\frac {1}{n}}\sum _{i=1}^{n}X_{i}}$, will approach the

${\displaystyle p}$

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

The size of this set is interesting, also, and can be explicitly determined: the logarithm of it is exactly the

${\displaystyle 2^{n}}$

${\displaystyle 2^{nH}}$

${\displaystyle H\leq 1}$

${\displaystyle n\to \infty }$

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

This value is the

One way to create a dynamical system out of the Bernoulli process is as a shift space. There is a natural translation symmetry on the product space ${\displaystyle \Omega =2^{\mathbb {N} }}$ given by the shift operator

${\displaystyle T(X_{0},X_{1},X_{2},\cdots )=(X_{1},X_{2},\cdots )}$

The Bernoulli measure, defined above, is translation-invariant; that is, given any cylinder set ${\displaystyle \sigma \in {\mathcal {B}}}$, one has

${\displaystyle P(T^{-1}(\sigma ))=P(\sigma )}$

and thus the

Instead of the probability measure ${\displaystyle P:{\mathcal {B}}\to \mathbb {R} }$, consider instead some arbitrary function ${\displaystyle f:{\mathcal {B}}\to \mathbb {R} }$. The pushforward

${\displaystyle f\circ T^{-1}}$

defined by ${\displaystyle \left(f\circ T^{-1}\right)(\sigma )=f(T^{-1}(\sigma ))}$ is again some function ${\displaystyle {\mathcal {B}}\to \mathbb {R} .}$ Thus, the map ${\displaystyle T}$ induces another map ${\displaystyle {\mathcal {L}}_{T}}$ on the space of all functions ${\displaystyle {\mathcal {B}}\to \mathbb {R} .}$ That is, given some ${\displaystyle f:{\mathcal {B}}\to \mathbb {R} }$, one defines

${\displaystyle {\mathcal {L}}_{T}f=f\circ T^{-1}}$

The map ${\displaystyle {\mathcal {L}}_{T}}$ is a

${\displaystyle {\mathcal {L}}_{T}(f+g)={\mathcal {L}}_{T}(f)+{\mathcal {L}}_{T}(g)}$

${\displaystyle {\mathcal {L}}_{T}(af)=a{\mathcal {L}}_{T}(f)}$

${\displaystyle f,g}$

${\displaystyle a}$

${\displaystyle {\mathcal {L}}_{T}(P)=P.}$

If one restricts ${\displaystyle {\mathcal {L}}_{T}}$ to act on polynomials, then the eigenfunctions are (curiously) the

The above can be made more precise. Given an infinite string of binary digits ${\displaystyle b_{0},b_{1},\cdots }$ write

${\displaystyle y=\sum _{n=0}^{\infty }{\frac {b_{n}}{2^{n+1}}}.}$

The resulting ${\displaystyle y}$ is a real number in the unit interval ${\displaystyle 0\leq y\leq 1.}$ The shift ${\displaystyle T}$ induces a homomorphism, also called ${\displaystyle T}$, on the unit interval. Since ${\displaystyle T(b_{0},b_{1},b_{2},\cdots )=(b_{1},b_{2},\cdots ),}$ one can see that ${\displaystyle T(y)=2y{\bmod {1}}.}$ This map is called the dyadic transformation; for the doubly-infinite sequence of bits ${\displaystyle \Omega =2^{\mathbb {Z} },}$ the induced homomorphism is the Baker's map.

Consider now the space of functions in ${\displaystyle y}$. Given some ${\displaystyle f(y)}$ one can find that

${\displaystyle \left[{\mathcal {L}}_{T}f\right](y)={\frac {1}{2}}f\left({\frac {y}{2}}\right)+{\frac {1}{2}}f\left({\frac {y+1}{2}}\right)}$

Restricting the action of the operator ${\displaystyle {\mathcal {L}}_{T}}$ to functions that are on polynomials, one finds that it has a

${\displaystyle {\mathcal {L}}_{T}B_{n}=2^{-n}B_{n}}$

where the ${\displaystyle B_{n}}$ are the Bernoulli polynomials. Indeed, the Bernoulli polynomials obey the identity

${\displaystyle {\frac {1}{2}}B_{n}\left({\frac {y}{2}}\right)+{\frac {1}{2}}B_{n}\left({\frac {y+1}{2}}\right)=2^{-n}B_{n}(y)}$

The Cantor set

Note that the sum

${\displaystyle y=\sum _{n=0}^{\infty }{\frac {b_{n}}{3^{n+1}}}}$

gives the Cantor function, as conventionally defined. This is one reason why the set ${\displaystyle \{H,T\}^{\mathbb {N} }}$ is sometimes called the Cantor set.

Odometer

Another way to create a dynamical system is to define an

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

From any Bernoulli process one may derive a Bernoulli process with p = 1/2 by the

Von Neumann (classical) main operation pseudocode:

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

Iterated von Neumann extractor

This section may contain verify the text. Relevant discussion may be found on the talk page. Please check 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".^[5]

The iterated version of the von Neumann algorithm, also known as advanced multi-level strategy (AMLS),^[6] was introduced by Yuval Peres in 1992.^[5] 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). 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:

(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:

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

References