Inprobability theory, abranching random walk is astochastic process that generalizes both the concept of arandom walk and of abranching process. At every generation (apoint of discrete time), a branching random walk's value is a set of elements that are located in somelinear space, such as thereal 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 arandom variable.
This process is a spatial expansion of theGalton–Watson process.[1] Its continuous equivalent is called branching Brownian motion.[2][3]
An example of branching random walk can be constructed where the branching process generates exactly two descendants for each element, abinarybranching random walk. Given theinitial condition thatXϵ = 0, we suppose thatX1 andX2 are the two children ofXϵ. Further, we suppose that they areindependentN(0, 1) random variables. Consequently, in generation 2, the random variablesX1,1 andX1,2 are each the sum ofX1 and aN(0, 1) random variable. In the next generation, the random variablesX1,2,1 andX1,2,2 are each the sum ofX1,2 and aN(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 sequenceXϵ,X1,X1,2,X1,2,2, ..., forms a conventional random walk.
 | Thisprobability-related article is astub. You can help Wikipedia byexpanding it. |