Bernoulli process on:  
[Wikipedia]  
[Google]  
[Amazon]
In
probability
Probability is the branch of mathematics concerning numerical descriptions of how likely an event is to occur, or how likely it is that a proposition is true. The probability of an event is a number between 0 and 1, where, roughly speakin ...
and
statistics, a Bernoulli process (named after
Jacob Bernoulli
Jacob Bernoulli (also known as James or Jacques; – 16 August 1705) was one of the many prominent mathematicians in the Bernoulli family. He was an early proponent of Leibnizian calculus and sided with Gottfried Wilhelm Leibniz during the Le ...
) is a finite or infinite sequence of binary
random variables, so it is a
discrete-time stochastic process
In probability theory and related fields, a stochastic () or random process is a mathematical object usually defined as a family of random variables. Stochastic processes are widely used as mathematical models of systems and phenomena that appea ...
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
Coin flipping, coin tossing, or heads or tails is the practice of throwing a coin in the air and checking which side is showing when it lands, in order to choose between two alternatives, heads or tails, sometimes used to resolve a dispute betwe ...
, possibly with an unfair coin (but with consistent unfairness). Every variable ''X''
''i'' in the sequence is associated with a
Bernoulli trial
In the theory of probability and statistics, a Bernoulli trial (or binomial trial) is a random experiment with exactly two possible outcomes, "success" and "failure", in which the probability of success is the same every time the experiment is ...
or experiment. They all have the same
Bernoulli distribution
In probability theory and statistics, the Bernoulli distribution, named after Swiss mathematician Jacob Bernoulli,James Victor Uspensky: ''Introduction to Mathematical Probability'', McGraw-Hill, New York 1937, page 45 is the discrete probabi ...
. 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 the
Bernoulli scheme
In mathematics, the Bernoulli scheme or Bernoulli shift is a generalization of the Bernoulli process to more than two possible outcomes. Bernoulli schemes appear naturally in symbolic dynamics, and are thus important in the study of dynamical sy ...
.
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
In statistics, the question of checking whether a coin is fair is one whose importance lies, firstly, in providing a simple problem on which to illustrate basic ideas of statistical inference and, secondly, in providing a simple problem that can be ...
.
Definition
A Bernoulli process is a finite or infinite sequence of
independent
Independent or Independents may refer to:
Arts, entertainment, and media Artist groups
* Independents (artist group), a group of modernist painters based in the New Hope, Pennsylvania, area of the United States during the early 1930s
* Independ ...
random variables ''X''
1, ''X''
2, ''X''
3, ..., 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
In probability theory and statistics, a collection of random variables is independent and identically distributed if each random variable has the same probability distribution as the others and all are mutually independent. This property is us ...
Bernoulli trial
In the theory of probability and statistics, a Bernoulli trial (or binomial trial) is a random experiment with exactly two possible outcomes, "success" and "failure", in which the probability of success is the same every time the experiment is ...
s.
Independence of the trials implies that the process is
memoryless
In probability and statistics, memorylessness is a property of certain probability distributions. It usually refers to the cases when the distribution of a "waiting time" until a certain event does not depend on how much time has elapsed already ...
. 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 ''i''th "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 trial
In the theory of probability and statistics, a Bernoulli trial (or binomial trial) is a random experiment with exactly two possible outcomes, "success" and "failure", in which the probability of success is the same every time the experiment is ...
s with parameter p.
In many applications time passes between trials, as the index i increases. In effect, the trials ''X''
1, ''X''
2, ... ''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 , the finite cases, or by , 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
In probability theory and statistics, the Bernoulli distribution, named after Swiss mathematician Jacob Bernoulli,James Victor Uspensky: ''Introduction to Mathematical Probability'', McGraw-Hill, New York 1937, page 45 is the discrete probabi ...
.
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
In probability theory and statistics, the geometric distribution is either one of two discrete probability distributions:
* The probability distribution of the number ''X'' of Bernoulli trials needed to get one success, supported on the set \;
* ...
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 space
In probability theory, a probability space or a probability triple (\Omega, \mathcal, P) is a mathematical construct that provides a formal model of a random process or "experiment". For example, one can define a probability space which models t ...
s 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
Borel algebra
Consider the
countably infinite direct product of copies of
. It is common to examine either the one-sided set
or the two-sided set
. There is a natural
topology
In mathematics, topology (from the Greek words , and ) is concerned with the properties of a geometric object that are preserved under continuous deformations, such as stretching, twisting, crumpling, and bending; that is, without closing ...
on this space, called the
product topology
In topology and related areas of mathematics, a product space is the Cartesian product of a family of topological spaces equipped with a natural topology called the product topology. This topology differs from another, perhaps more natural-s ...
. The sets in this topology are finite sequences of coin flips, that is, finite-length
strings
String or strings may refer to:
*String (structure), a long flexible structure made from threads twisted together, which is used to tie, bind, or hang other objects
Arts, entertainment, and media Films
* ''Strings'' (1991 film), a Canadian anim ...
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
In mathematics, a Borel set is any set in a topological space that can be formed from open sets (or, equivalently, from closed sets) through the operations of countable union, countable intersection, and relative complement. Borel sets are nam ...
. This algebra is then commonly written as
where the elements of
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
, then one can define a natural
measure
Measure may refer to:
* Measurement, the assignment of a number to a characteristic of an object or event
Law
* Ballot measure, proposed legislation in the United States
* Church of England Measure, legislation of the Church of England
* Mea ...
on the product space, given by
(or by
for the two-sided process). In another word, if a
discrete random variable
A random variable (also called random quantity, aleatory variable, or stochastic variable) is a mathematical formalization of a quantity or object which depends on random events. It is a mapping or a function from possible outcomes (e.g., the po ...
''X'' has a ''Bernoulli distribution'' with parameter ''p'', where 0 ≤ ''p'' ≤ 1, and its
probability mass function is given by
:
and
.
We denote this distribution by Ber(''p'').
Given a cylinder set, that is, a specific sequence of coin flip results
; for the doubly-infinite sequence of bits
\Omega=2^\mathbb, the induced homomorphism is the Baker's map.
Consider now the space of functions in
y. Given some
f(y) one can easily find that
:
\left[\mathcal_T f\right](y) = \fracf\left(\frac\right)+\fracf\left(\frac\right)
Restricting the action of the operator
\mathcal_T to functions that are on polynomials, one finds that it has a discrete spectrum given by
:
\mathcal_T B_n= 2^B_n
where the
B_n are the
Bernoulli polynomials. Indeed, the Bernoulli polynomials obey the identity
:
\fracB_n\left(\frac\right)+\fracB_n\left(\frac\right) = 2^B_n(y)
The Cantor set
Note that the sum
:
y=\sum_^\infty \frac
gives the
Cantor function
In mathematics, the Cantor function is an example of a function that is continuous, but not absolutely continuous. It is a notorious counterexample in analysis, because it challenges naive intuitions about continuity, derivative, and measure. ...
, as conventionally defined. This is one reason why the set
\^\mathbb is sometimes called the
Cantor set.
Odometer
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 bit
In computer processors the carry flag (usually indicated as the C flag) is a single bit in a system status register/flag register used to indicate when an arithmetic carry or borrow has been generated out of the most significant arithmetic logic ...
s 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)
In mathematics, a group is a set and an operation that combines any two elements of the set to produce a third element of the set, in such a way that the operation is associative, an identity element exists and every element has an inverse. ...
, and the Bernoulli process was already given a topology, above, this provides a simple example of a
topological group
In mathematics, topological groups are logically the combination of groups and topological spaces, i.e. they are groups and topological spaces at the same time, such that the continuity condition for the group operations connects these two st ...
.
In this case, the transformation
T is given by
:
T\left(1,\dots,1,0,X_,X_,\dots\right) = \left(0,\dots,0,1,X_,X_,\dots \right).
It leaves the Bernoulli measure invariant only for the special case of
p=1/2 (the "fair coin"); otherwise not. Thus,
T is a
measure preserving dynamical system in this case, otherwise, it is merely a
conservative system In mathematics, a conservative system is a dynamical system which stands in contrast to a dissipative system. Roughly speaking, such systems have no friction or other mechanism to dissipate the dynamics, and thus, their phase space does not shrink o ...
.
Bernoulli sequence
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
In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is calle ...
of integers
:
\mathbb^x = \ \,
called the Bernoulli sequence 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
\mathbb^x is also a random subset of the index set, the natural numbers
\mathbb.
Almost all Bernoulli sequences
\mathbb^x are
ergodic sequences.
Randomness extraction
From any Bernoulli process one may derive a Bernoulli process with ''p'' = 1/2 by the
von Neumann extractor, the earliest
randomness extractor A randomness extractor, often simply called an "extractor", is a function, which being applied to output from a weakly random entropy source, together with a short, uniformly random seed, generates a highly random output that appears independent fro ...
, which actually extracts uniform randomness.
Basic von Neumann extractor
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
In probability theory and statistics, two real-valued random variables, X, Y, are said to be uncorrelated if their covariance, \operatorname ,Y= \operatorname Y- \operatorname \operatorname /math>, is zero. If two variables are uncorrelated, ther ...
. 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''
2 + (1 − ''p'')
2 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)
Iterated von Neumann extractor
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".
The iterated version of the von Neumann algorithm, also known as Advanced Multi-Level Strategy (AMLS), was introduced by Yuval Peres in 1992.
[ 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:
(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) else
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.]
References
Further reading
* Carl W. Helstrom, ''Probability and Stochastic Processes for Engineers'', (1984) Macmillan Publishing Company, New York .
External links
Using a binary tree diagram for describing a Bernoulli process
{{Stochastic processes
Stochastic processes