In probability theory, a branching random walk is a

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 generalizes both the concept of a random walk and of a branching process. 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, such as the

real line In elementary mathematics, a number line is a picture of a graduated straight line (geometry), 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 ...

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

. This process is a spatial expansion of the Galton–Watson process. 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 In mathematics and particularly in dynamic systems, an initial condition, in some contexts called a seed value, is a value of an evolving variable at some point in time designated as the initial time (typically denoted ''t'' = 0). For ...

that ''X''_ϵ = 0, we suppose that ''X''₁ and ''X''₂ are the two children of ''X''_ϵ. Further, we suppose that they are independent (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