Bernoulli process

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.

Consider 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 {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 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).[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 Bernoulli measure.[2]

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 {B}},P)}$, as defined above.

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 Bernoulli measure is a Haar measure; it is an invariant 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} }$. 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 linear 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 the transfer operator or the Ruelle–Frobenius–Perron operator. This operator has a spectrum, that is, a collection of eigenfunctions and corresponding eigenvalues. The largest eigenvalue is the Frobenius–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) the Bernoulli polynomials![3][4] This coincidence of naming was presumably not known to Bernoulli.

The map T : [0,1) → [0,1), ${\displaystyle x\mapsto 2x{\bmod {1}}}$ preserves the Lebesgue measure.

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 discrete spectrum given by

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

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.

Another way to create a dynamical system is to define an odometer. Informally, this is exactly what it sounds like: just "add one" to the first position, and let the odometer "roll over" by using carry bits as the odometer rolls over. This is nothing more than base-two addition on the set of infinite strings. Since addition forms a group (mathematics), and the Bernoulli process was already given a topology, above, this provides a simple example of a topological 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 a measure preserving dynamical system in this case, otherwise, it is merely a conservative system.

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 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)
}

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]