Branching Process - Mathematical Formulation

Mathematical Formulation

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

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

with S0 = 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 Si represent the number of revealed but unvisited nodes in period i, and let Xi 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.

Read more about this topic:  Branching Process

Famous quotes containing the words mathematical and/or formulation:

    It is by a mathematical point only that we are wise, as the sailor or the fugitive slave keeps the polestar in his eye; but that is sufficient guidance for all our life. We may not arrive at our port within a calculable period, but we would preserve the true course.
    Henry David Thoreau (1817–1862)

    Art is an experience, not the formulation of a problem.
    Lindsay Anderson (b. 1923)