Branching Process - Mathematical Formulation

Mathematical Formulation

The most common formulation of a branching process is that of the Galton–Watson process. Let Z_n denote the state in period n (often interpreted as the size of generation n), and let X_n,i be a random variable denoting the number of direct successors of member i in period n, where X_n,i are iid over all n ∈ {0,1,2,...} and i ∈ {1,...,Z_n}. Then the recurrence equation is

with Z₀ = 1. Alternatively, one can formulate a branching process as a random walk. Let S_i denote the state in period i, and let X_i be a random variable that is iid over all i. Then the recurrence equation is

with S₀ = 1. To gain some intuition for this formulation, one can imagine a walk where the goal is to visit every node, but every time a previously unvisited node is visited, additional nodes are revealed that must also be visited. Let S_i represent the number of revealed but unvisited nodes in period i, and let X_i represent the number of new nodes that are revealed when node i is visited. Then in each period, the number of revealed but unvisited nodes equals the number of such nodes in the previous period, plus the new nodes that are revealed when visiting a node, minus the node that is visited. The process ends once all revealed nodes have been visited.