Branching random walk
# 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

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_1$ and $X_2$ 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_1$ 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_1,$ $X_{1,2},$ $X_{1,2,2},$ ..., forms a conventional random walk.

