Branching random walk

In probability theory, a branching random walk is a stochastic process 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. 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.

This process is a spatial expansion of the Galton–Watson process. Its continuous equivalent is called branching Brownian motion.

Example of a branching random walk

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 N(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 N(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 N(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.

See also

• Discrete-time dynamical system