This article includes a list ofgeneral references, butit lacks sufficient correspondinginline citations. Please help toimprove this article byintroducing more precise citations.(September 2011) (Learn how and when to remove this message)

Inprobability andstatistics, aBernoulli process (named afterJacob Bernoulli) is a finite or infinite sequence of binaryrandom variables, so it is adiscrete-time stochastic process that takes only two values, canonically 0 and 1. The componentBernoulli variablesX_i areidentically distributed and independent. Prosaically, a Bernoulli process is a repeatedcoin flipping, possibly with an unfair coin (but with consistent unfairness). Every variableX_i in the sequence is associated with aBernoulli trial or experiment. They all have the sameBernoulli 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 die); this generalization is known as theBernoulli scheme.

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

ABernoulli process is a finite or infinite sequence ofindependentrandom variablesX₁, X₂, X₃, ..., such that

• for eachi, the value ofX_i is either 0 or 1;
• for all values of$i$, the probabilityp thatX_i = 1 is the same.

In other words, a Bernoulli process is a sequence ofindependent identically distributedBernoulli trials.

Independence of the trials implies that the process ismemoryless, in which past event frequencies have no influence on about future event probability frequencies. In most instances the true value ofp is unknown, therefore we use past frequencies to assess/forecast/estimate future events & their probabilities indirectly via applying probabilistic inference upon 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.

The two possible values of eachX_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 theith "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 variablesX_i may be calledBernoulli trials with parameter p.

In many applications time passes between trials, as the index i increases. In effect, the trialsX₁, 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, anyX_i andX_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 aBernoulli distribution.^[1] Several random variables andprobability distributions beside the Bernoullis may be derived from the Bernoulli process:

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

The negative binomial variables may be interpreted as randomwaiting times.

The Bernoulli process can be formalized in the language ofprobability 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\}.}$

Consider thecountably infinitedirect product of copies of${\displaystyle 2=\{H,T\}}$. It is common to examine either the one-sided set${\displaystyle \mathrm{\Omega }=2^{\mathbb{N}}=\{H,T{\}}^{\mathbb{N}}}$ or the two-sided set${\displaystyle \mathrm{\Omega }=2^{\mathbb{Z}}}$. There is a naturaltopology on this space, called theproduct topology. The sets in this topology are finite sequences of coin flips, that is, finite-lengthstrings ofH andT (H stands for heads andT stands for tails), with the rest of (infinitely long) sequence taken as "don't care". These sets of finite sequences are referred to ascylinder sets in the product topology. The set of all such strings forms asigma algebra, specifically, aBorel algebra. This algebra is then commonly written as${\displaystyle (\mathrm{\Omega },\mathcal{B})}$ where the elements of${\displaystyle \mathcal{B}}$ 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 naturalmeasure 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 adiscrete random variableX has aBernoulli distribution with parameterp, where 0 ≤p ≤ 1, and itsprobability 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).^[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}}$

wherek is the number of times thatH appears in the sequence, andn−k is the number of times thatT 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-valuedrandom variable with${\displaystyle x_i=[{\omega }_i=H]}$ inIverson 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 theBernoulli measure.^[2]

Note that the probability of any specific, infinitely long sequence of coin flips is exactly zero; this is because${\displaystyle \underset{n\to \mathrm{\infty }}{lim}{p}^n=0}$, for any. A probability equal to 1 implies that any given infinite sequence hasmeasure 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 theasymptotic equipartition property.

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

Let us assume the canonical process with${\displaystyle H}$ represented by${\displaystyle 1}$ and${\displaystyle T}$ represented by${\displaystyle 0}$. Thelaw of large numbers states that the average of the sequence, i.e.,${\displaystyle {\overline{X}}_n:=\frac{1}{n}\sum _{i=1}^n{X}_i}$, will approach theexpected value almost certainly, that is, the events which do not satisfy this limit have zero probability. Theexpectation value of flippingheads, 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 ofBernoulli trials that compose the Bernoulli process.

One is often interested in knowing how often one will observeH in a sequence ofn coin flips. This is given by simply counting: Givenn successive coin flips, that is, given the set of all possiblestrings of lengthn, the numberN(k,n) of such strings that containk occurrences ofH is given by thebinomial coefficient

${\displaystyle N(k,n)=(\genfrac{}{}{0ex}{}{n}{k})=\frac{n!}{k!(n-k)!}}$

If the probability of flipping heads is given byp, then the total probability of seeing a string of lengthn withk heads is

${\displaystyle \mathbb{P}([S_n=k])=(\genfrac{}{}{0ex}{}{n}{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 theBinomial distribution.

As we can see from the above formula that, if n=1, theBinomial distribution will turn into aBernoulli distribution. So we can know that theBernoulli distribution is exactly a special case ofBinomial 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 \mathrm{\infty }}$. In this case, one may make use ofStirling'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 forP(k,n), one obtains theNormal distribution; this is the content of thecentral 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: theasymptotic equipartition property. Put informally, one notes that, yes, over many coin flips, one will observeH exactlyp 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 ofH andT 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 theKolmogorov 0-1 law.

The size of this set is interesting, also, and can be explicitly determined: the logarithm of it is exactly theentropy of the Bernoulli process. Once again, consider the set of all strings of lengthn. 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\le 1}$. By using Stirling's approximation, putting it into the expression forP(k,n), solving for the location and width of the peak, and finally taking${\displaystyle n\to \mathrm{\infty }}$ one finds that

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

This value is theBernoulli entropy of a Bernoulli process. Here,H stands for entropy; not to be confused with the same symbolH standing forheads.

John von Neumann posed a question about the Bernoulli process regarding the possibility of a given process beingisomorphic to another, in the sense of theisomorphism of dynamical systems. The question long defied analysis, but was finally and completely answered with theOrnstein isomorphism theorem. This breakthrough resulted in the understanding that the Bernoulli process is unique anduniversal; 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 aremixing 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).

The Bernoulli process can also be understood to be adynamical system, as an example of anergodic system and specifically, ameasure-preserving dynamical system, in one of several different ways. One way is as ashift space, and the other is as anodometer. These are reviewed below.

One way to create a dynamical system out of the Bernoulli process is as ashift space. There is a natural translation symmetry on the product space${\displaystyle \mathrm{\Omega }=2^{\mathbb{N}}}$ given by theshift 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 theBernoulli measure is aHaar measure; it is aninvariant measure on the product space.

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

${\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 alinear operator, as (obviously) one has${\displaystyle {\mathcal{L}}_T(f+g)={\mathcal{L}}_T(f)+{\mathcal{L}}_T(g)}$ and${\displaystyle {\mathcal{L}}_T(af)=a{\mathcal{L}}_T(f)}$ for functions${\displaystyle f,g}$ and constant${\displaystyle a}$. This linear operator is called thetransfer operator or theRuelle–Frobenius–Perron operator. This operator has aspectrum, that is, a collection ofeigenfunctions and corresponding eigenvalues. The largest eigenvalue is theFrobenius–Perron eigenvalue, and in this case, it is 1. The associated eigenvector is the invariant measure: in this case, it is the Bernoulli measure. That is,${\displaystyle {\mathcal{L}}_T(P)=P.}$

If one restricts${\displaystyle {\mathcal{L}}_T}$ to act on polynomials, then the eigenfunctions are (curiously) theBernoulli polynomials!^[3][4] This coincidence of naming was presumably not known to Bernoulli.

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}^{\mathrm{\infty }}\frac{b_n}{2^{n+1}}.}$

The resulting${\displaystyle y}$ is a real number in the unit interval${\displaystyle 0\le y\le 1.}$ The shift${\displaystyle T}$ induces ahomomorphism, 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)=2ymod1.}$ This map is called thedyadic transformation; for the doubly-infinite sequence of bits${\displaystyle \mathrm{\Omega }=2^{\mathbb{Z}},}$ the induced homomorphism is theBaker'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 adiscrete spectrum given by

${\displaystyle {\mathcal{L}}_T{B}_n=2^{-n}{B}_n}$

where the${\displaystyle B_n}$ are theBernoulli 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)}$

Note that the sum

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

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

Another way to create a dynamical system is to define anodometer. Informally, this is exactly what it sounds like: just "add one" to the first position, and let the odometer "roll over" by usingcarry bits as the odometer rolls over. This is nothing more than base-two addition on the set of infinite strings. Since addition forms agroup, and the Bernoulli process was already given a topology, above, this provides a simple example of atopological group.

In this case, the transformation${\displaystyle T}$ is given by

${\displaystyle T\left(1,\dots ,1,0,X_{k+1},X_{k+2},\dots \right)=\left(0,\dots ,0,1,X_{k+1},X_{k+2},\dots \right).}$

It leaves the Bernoulli measure invariant only for the special case of${\displaystyle p=1/2}$ (the "fair coin"); otherwise not. Thus,${\displaystyle T}$ is ameasure preserving dynamical system in this case, otherwise, it is merely aconservative system.

The termBernoulli sequence is often used informally to refer to arealization 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 sequencex of coin flips, there is asequence of integers

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

called theBernoulli sequence^{[verification needed]} associated with the Bernoulli process. For example, ifx 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 isheads.

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}$ areergodic sequences.^{[verification needed]}

From any Bernoulli process one may derive a Bernoulli process withp = 1/2 by thevon Neumann extractor, the earliestrandomness extractor, which actually extracts uniform randomness.

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.

For example, an input stream of eight bits10011011 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 probabilityp(1−p) = (1−p)p. This extraction of uniform randomness does not require the input trials to be independent, onlyuncorrelated. More generally, it works for anyexchangeable 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 proportionp² + (1 − p)² of the input pairs(00 and 11), which is near one whenp is near zero or one, and is minimized at 1/4 whenp = 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 operationpseudocode:

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

This sectioncontainscitations that may notverify the text. Please helpimprove it by checking for citation inaccuracies and resourcing or removing material failing verification.(January 2014) (Learn how and when to remove this 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, () gives AMLS paper notation:

(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 the AMLS paper,11001011101110 using 1 for H and 0 for T, is processed this way:

Starting from step 1, the input is a concatenation of sequence 2 and sequence 1 from the previous step (the order is arbitrary but should be fixed). The final output is()()(1)()(1)()(1)(1)()()(0)(0)()(0)(1)(1)()(1) (=1111000111), so from 14 bits of input 10 bits of output were generated, as opposed to 3 bits through the von Neumann algorithm alone. The constant output of exactly 2 bits per round per bit pair (compared with a variable none to 1 bit in classical VN) also allows for constant-time implementations which are resistant totiming 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]

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

• Using a binary tree diagram for describing a Bernoulli process

• Stochastic processes

• Use American English from February 2019
• All Wikipedia articles written in American English
• Articles with short description
• Short description matches Wikidata
• 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