Bernoulli process

In probability and statistics, a Bernoulli process is a discrete-time stochastic process consisting of a sequence of independent random variables taking values over two symbols. Prosaically, a Bernoulli process is coin flipping several times, possibly with an unfair coin. A variable in such a sequence may be called a Bernoulli variable.

Definition

A Bernoulli process is a discrete-time stochastic process consisting of 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 that X_i = 1 is the same number p.

In other words, a Bernoulli process is a sequence of independent identically distributed Bernoulli trials – it is a discrete-time Lévy process. The two possible values of each X_i are often called "success" (or "arrival") and "failure", so that, when expressed as a number, 0 or 1, the value is said to be the number of successes on the ith "trial". The individual success/failure variables X_i are also called Bernoulli trials.

Independence of Bernoulli trials implies memorylessness property: past trials do not provide any information regarding future outcomes. From any given time, future trials is also a Bernoulli process independent of the past (fresh-start property).

Random variables associated with the Bernoulli process include

• The number of successes in the first n trials; this has a binomial distribution;
• The number of trials needed to get r successes; this has a negative binomial distribution.
• The number of trials needed to get one success; this has a geometric distribution, which is a special case of the negative binomial distribution.

The problem of determining the process, given only a limited sample of Bernoulli trials, is known as the problem of checking if a coin is fair.

Formal definition

The Bernoulli process can be formalized in the language of probability spaces. A Bernoulli process is then a probability space (Ω,Pr) together with a random variable X over the set {0,1}, so that for every , one has X_i(ω) = 1 with probability p and X_i(ω) = 0 with probability 1-p.

Bernoulli sequence

Given a Bernoulli process defined on a probability space (Ω,Pr), then associated with every is a sequence of integers

which is called the Bernoulli sequence. So, for example, if ω represents a sequence of coin flips, then the Bernoulli sequence is the list of integers for which the coin toss came out heads.

Almost all Bernoulli sequences are ergodic sequences.

Randomness extraction

Given a Bernoulli sequence for one may produce a Bernoulli sequence with p = 1 / 2 by the Von Neumann extractor, the earliest randomness extractor. Given a Bernoulli sequence, one produces the new sequence by grouping the input sequence into non-overlapping pairs of successive bits and outputting as follows:

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

Thus, the output table is as follows:

As this takes two input bits to produce one or no output bits, the output will be shorter than the input by a factor of at least 2. It will discard on average p² + (1 − p)² = p² + q² of the input – this is a minimum for p = 1 / 2, where it will discard half the input pairs, so the output will be on average 1/4 the length of the input.

The output stream will have equal amounts of 0 and 1, as 10 and 01 are equally likely (both having likelihood pq, as ), and does not require the input trials to be independent, only uncorrelated – more generally, it applies to any exchangeable sequence (meaning that sequences that are finite rearrangements are equally likely).

Bernoulli map

Because every trial has one of two possible outcomes, a sequence of trials may be represented by the binary digits of a real number. When the probability p = 1/2, all possible distributions are equally likely, and thus the measure of the σ-algebra of the Bernoulli process is equivalent to the uniform measure on the unit interval: in other words, the real numbers are distributed uniformly on the unit interval.

The shift operator T taking each random variable to the next,

TX_i = X_{i + 1}

is then given by the Bernoulli map or the 2x mod 1 map

where represents a given sequence of measurements, and is the floor function, the largest integer less than or equal to z. The Bernoulli map essentially lops off one digit of the binary expansion of z.

The Bernoulli map is an exactly solvable model of deterministic chaos. The transfer operator, or Frobenius-Perron operator, of the Bernoulli map is solvable; the eigenvalues are powers of 1/2, and the eigenfunctions are the Bernoulli polynomials.

Generalizations

The generalization of the Bernoulli process to more than two possible outcomes is called the Bernoulli scheme.

See also

• Lévy process

References

• Carl W. Helstrom, Probability and Stochastic Processes for Engineers, (1984) Macmillan Publishing Company, New York ISBN 0-02-353560-1.
• Dimitri P. Bertsekas and John N. Tsitsiklis, Introduction to Probability, (2002) Athena Scientific, Massachusetts ISBN 1-886529-40-X
• Pierre Gaspard, "r-adic one-dimensional maps and the Euler summation formula", Journal of Physics A, 25 (letter) L483-L485 (1992). (Describes the eigenfunctions of the transfer operator for the Bernoulli map)
• Dean J. Driebe, Fully Chaotic Maps and Broken Time Symmetry, (1999) Kluwer Academic Publishers, Dordrecht Netherlands ISBN 0-7923-5564-4 (Chapters 2, 3 and 4 review the Ruelle resonances and subdynamics formalism for solving the Bernoulli map).