probability theory Probability theory is the branch of mathematics concerned with probability. Although there are several different probability interpretations, probability theory treats the concept in a rigorous mathematical manner by expressing it through a set o ...

, a branching random walk is a stochastic process that generalizes both the concept of a

random walk In mathematics, a random walk is a random process that describes a path that consists of a succession of random steps on some mathematical space. An elementary example of a random walk is the random walk on the integer number line \mathbb ...

and of a

branching process In probability theory, a branching process is a type of mathematical object known as a stochastic process, which consists of collections of random variables. The random variables of a stochastic process are indexed by the natural numbers. The ori ...

. At every generation (a point of discrete time), a branching random walk's value is a set of elements that are located in some

linear space In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called ''vectors'', may be added together and multiplied ("scaled") by numbers called '' scalars''. Scalars are often real numbers, but c ...

, such as the

real line In elementary mathematics, a number line is a picture of a graduated straight line that serves as visual representation of the real numbers. Every point of a number line is assumed to correspond to a real number, and every real number to a po ...

. Each element of a given generation can have several descendants in the next generation. The location of any descendant is the sum of its parent's location and a

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 p ...

. This process is a spatial expansion of the

Galton–Watson process The Galton–Watson process is a branching stochastic process arising from Francis Galton's statistical investigation of the extinction of family names. The process models family names as patrilineal (passed from father to son), while offspri ...

. Its continuous equivalent is called branching Brownian motion. Branching random walk example

Example

An example of branching random walk can be constructed where the branching process generates exactly two descendants for each element, a ''binary ''branching random walk. Given the initial condition that ''X''_ϵ = 0, we suppose that ''X''₁ and ''X''₂ are the two children of ''X''_ϵ. Further, we suppose that they are

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 * Independe ...

(0, 1) random variables. Consequently, in generation 2, the random variables ''X''_1,1 and ''X''_1,2 are each the sum of ''X''₁ and a (0, 1) random variable. In the next generation, the random variables ''X''_1,2,1 and ''X''_1,2,2 are each the sum of ''X''_1,2 and a (0, 1) random variable. The same construction produces the values at successive times. Each lineage in the infinite "genealogical tree" produced by this process, such as the sequence ''X''_ϵ, ''X''₁, ''X''_1,2, ''X''_1,2,2, ..., forms a conventional random walk.

References

Variants of random walks {{probability-stub

Example

See also

References