Branching process

Discrete time branching processes The most common formulation of a branching process is that of the Galton–Watson process, which is a discrete time 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 independent and identically distributed random variables over all n ∈{ 0, 1, 2, ...} and i ∈ {1, ..., Zn}. The value of the process in the next generation is given by :Z_{n+1} = \sum_{i=1}^{Z_n} X_{n,i} Alternatively, the branching process can be formulated 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 :S_{i+1} = S_i+X_{i+1}-1 = \sum_{j=1}^{i+1} X_j-i with S0 = 1. To gain some intuition for this formulation, 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. Continuous-time branching processes In continuous-time branching processes, each individual waits for a random time (which is a continuous random variable), and then divides according to the given distribution. The waiting time for different individuals are independent, and are independent with the number of children. In Markov processes, the waiting time is an exponential random variable. == Extinction problem for a branching process==

The ultimate extinction probability is given by :\lim_{n \to \infty} \Pr(Z_n=0). For any nontrivial cases (trivial cases are ones in which the probability of having no offspring is zero for every member of the population - in such cases the probability of ultimate extinction is 0), the probability of ultimate extinction equals one if μ ≤ 1 and strictly less than one if μ > 1. The process can be analyzed using the method of probability generating function. Let p0, p1, p2, ... be the probabilities of producing 0, 1, 2, ... offspring by each individual in each generation. Let dm be the extinction probability by the mth generation, starting with a single individual (i.e. Z_0=1). Obviously, d0 = 0 and d1 = p0. Since the probabilities for all paths that lead to 0 by the mth generation must be added up, the extinction probability is nondecreasing in generations. That is, :0=d_0 \leq d_1\leq d_2 \leq \cdots \leq 1. Therefore, dm converges to a limit d, and d is the ultimate extinction probability. If there are j offspring in the first generation, then to die out by the mth generation, each of these lines must die out in m − 1 generations. Since they proceed independently, the probability is (dm−1) j. Thus, :d_m=p_0+p_1d_{m-1}+p_2(d_{m-1})^2+p_3(d_{m-1})^3+\cdots. \, The right-hand side of the equation is a probability generating function. Let h(z) be the ordinary generating function for pi: :h(z)=p_0+p_1z+p_2z^2+\cdots. \, Using the generating function, the previous equation becomes :d_m=h(d_{m-1}). \, Since dm → d, d can be found by solving :d=h(d). \, This is also equivalent to finding the intersection point(s) of lines y = z and y = h(z) for z ≥ 0. y = z is a straight line. y = h(z) is an increasing (since h'(z) = p_1 + 2 p_2 z + 3 p_3 z^2 + \cdots \geq 0) and convex (since h''(z) = 2 p_2 + 6 p_3 z + 12 p_4 z^2 + \cdots \geq 0) function. There are at most two intersection points. Since (1,1) is always an intersect point for the two functions, there only exist three cases: • There is another intersection point at z 1.(See the black curve in the graph) In case 1, the ultimate extinction probability is strictly less than one. For case 2 and 3, the ultimate extinction probability equals to one. By observing that h′(1) = p1 + 2p2 + 3p3 + ... = μ is exactly the expected number of offspring a parent could produce, it can be concluded that for a branching process with generating function h(z) for the number of offspring of a given parent, if the mean number of offspring produced by a single parent is less than or equal to one, then the ultimate extinction probability is one. If the mean number of offspring produced by a single parent is greater than one, then the ultimate extinction probability is strictly less than one. == Example of extinction problem ==

Consider a parent can produce at most two offspring. The extinction probability in each generation is: :d_m=p_0+p_1d_{m-1}+p_2(d_{m-1})^2. \, with d0 = 0. For the ultimate extinction probability, we need to find d which satisfies d = p0 + p1d + p2d2. Taking as example probabilities for the numbers of offspring produced p0 = 0.1, p1 = 0.6, and p2 = 0.3, the extinction probability for the first 20 generations is as follows: In this example, we can solve algebraically that d = 1/3, and this is the value to which the extinction probability converges with increasing generations. == Multitype branching processes ==

In multitype branching processes, individuals are not identical, but can be classified into n types. After each time step, an individual of type i will produce individuals of different types, and \mathbf{X}_i, a random vector representing the numbers of children in different types, satisfies a probability distribution on \mathbb{N}^n. For example, consider the population of cancer stem cells (CSCs) and non-stem cancer cells (NSCCs). After each time interval, each CSC has probability p_1 to produce two CSCs (symmetric division), probability p_2 to produce one CSC and one NSCC (asymmetric division), probability p_3 to produce one CSC (stagnation), and probability 1-p_1-p_2-p_3 to produce nothing (death); each NSCC has probability p_4 to produce two NSCCs (symmetric division), probability p_5 to produce one NSCC (stagnation), and probability 1-p_4-p_5 to produce nothing (death). Law of large numbers for multitype branching processes For multitype branching processes that the populations of different types grow exponentially, the proportions of different types converge almost surely to a constant vector as long as the expectation-matrix satisfies the conditions of the Perron-Frobenius theorem (irreducibility and primitivity). This is the strong law of large numbers for multitype branching processes. For continuous-time cases, proportions of the population expectation satisfy an ODE system, which has a unique attracting fixed point. This fixed point is just the vector that the proportions converge to in the law of large numbers. The monograph by Athreya and Ney summarizes a common set of conditions under which this law of large numbers is valid. Later there are some improvements through discarding different conditions. ==See also==