A Simple Branching Process
The model.
Consider a system of A-particles or individuals subject to the Poisson-distributed random events
$$\begin{align*}\text{Death} & :\text{ } \begin{array}[c]{ll} A\rightarrow0\ \ \... ...gin{array}[c]{ll} A\rightarrow2A & \text{rate }\beta \end{array} \end{align*}$$
The state of zero individuals is an absorbing state. If the system hits this state it stays there. The corresponding master equation is

$$\frac{\partial P_{n}\left( t\right) }{\partial t}=\beta\left(... ...t\right) -\left( \lambda+\beta\right) nP_{n}\left( t\right)$$ (1)

                         Suppose we start with one individual at $\ t=0$. We'd like to know something about the sizes and durations of the resulting cascades. Interesting quantities.
1. Survival probability.

$$P_{\text{S}}\left( t\right) =1-P_{0}\left( t\right) ,$$

or the number of cascades lasting longer than time t, and in particular, its asymptotic value

$$P_{\infty}=\lim_{t\rightarrow\infty}P_{\text{s}}\left( t\right)$$

2. Cumulative size distribution
$n\left( s\right)$, the number of cascades larger than size s, or the probability that a cascade involves at least s individuals.

One finds critical behaviour when $\Delta\equiv\beta-\lambda=0$, i.e. all of these quantities behave as power laws
$$\begin{align*}P_{\text{S}}\left( t\right) & \sim t^{-\delta}\\ P_{\infty} & \sim\Delta^{\theta}\\ n\left( s\right) & \sim s^{-\alpha} \end{align*}$$
Survival probability.
The survival probability can be found by using the generating function

$$G\left( z,t\right) =\sum_{n=0}^{\infty}P_{n}\left( t\right) z^{n}$$ (2)

From the generating function, we can find the moments by taking derivative w.r.t z and then setting z=1.
For example:

$$\left\langle n\right\rangle =\left. \frac{\partial G(z)}{dz}\right\vert _{z=1}$$

and

$$\left\langle n^{2}\right\rangle -\left\langle n\right\rangle =\left. \frac{\partial^{2}G(z)}{dz^{2}}\right\vert _{z=1}$$

often the moments

$$\phi_{m}=\left\langle n(n-1)(n-2)\cdot\cdot\cdot(n-m+1)\right\rangle =\left. \frac{d^{m}G(z)}{dz^{m}}\right\vert _{z=1}$$ (3)

are refered to as `factorial' moments. From the factorial moments, one can alway get back the probabilities

$$P_{n}=\frac{1}{n!}\sum_{m=n}^{\infty}\frac{\left( -1\right) ^{k}}{m!} \phi_{m}$$

We can use eqn (1) to obtain an equation for the generating function for this birth-death process. By multiplying by zⁿ and summing over n, one finds

$$\frac{\partial G\left( z,t\right) }{\partial t}=\left( z-1\ri... ...mbda\right) \frac{\partial G\left( z,t\right) }{\partial z}$$ (4)

This can be solved using the method of characteristics.
The method of characteristics.
Let $\left[ z\left( \tau\right) ,t\left( \tau\right) \right]$ be some curve in the $\left( z,t\right)$ plane. The change in G along this curve is

$$\frac{dG}{d\tau}=\frac{\partial G}{\partial t}\frac{dt}{d\tau}+\frac{\partial }{\partial z}\frac{dz}{d\tau}$$ (5)

We want to choose a curve such that

$$\left( \frac{dz}{d\tau}\right) /\left( \frac{dt}{d\tau}\right) =-\left( z-1\right) \left( \beta z-\lambda\right)$$

Eqn. (4) implies $G\left( z,t\right)$ is constant along this characteristic. Integrating

$$\frac{dz}{dt}=-\left( z-1\right) \left( \beta z-\lambda\right)$$

we find

$$C=\frac{z-1}{\beta z-\lambda}e^{\left( \beta-\lambda\right) t}$$

where C is some constant of the curve $z\left( t\right)$. Then $G\left( z,t\right)$ must be some function of C.If we consider initial conditions such that at t=0, the number of individuals was exactly m, or $P_{n}\left( 0\right) =\delta_{n,m}$, we have

$$G\left( z,0\right) =z^{m}$$

One finds the solution

$$G\left( z,t\right) =\left[ \frac{e^{\left( \lambda-\beta\righ... ...\beta z-\lambda\right) +\beta\left( 1-z\right) }\right] ^{m}$$ (6)

This complicated looking expression tells us everything we need to know about this birth death process. Expanding in a power series, we can find $P_{n}\left( t\right)$. The survival probability is

$$P_{\text{S}}\left( t\right) =\frac{\lambda-\beta}{e^{\left( \lambda -\beta\right) t}\lambda-\beta}$$

For $\beta<\lambda$,

$$\text{\ }P_{\infty}=0$$

the population becomes extinct. For $\lambda<\beta$
$$\begin{align*}P_{\infty} & =1-\frac{\lambda}{\beta}\\ & =\frac{\Delta}{\beta} \end{align*}$$
For the critical case, $\lambda=\beta,$ one finds

$$P_{\text{S}}\left( t\right) =\frac{1}{1+\beta t}$$ (7)

Exercise. The result for the critical point can also be found by solving the (factorial) moment equations. Using eqn. (3) show that

$$\frac{d\phi_{m}(t)}{dt}=\frac{\beta k!}{(k-2)!}n_{m-1}$$

and that for 1-initial particle b.c , these equations can be recursively integrated to find

$$\phi_{m}\left(t) =m!(\beta t)^{m-1}$$

Digression:
An easier method
There's actually an easier way to get the duration results. For this method, we need conditional probabilities.
$$\begin{align*}P_{n/m}\left( t_{2},t_{1}\right) & \equiv\text{prob. of finding }n... ...at time }t_{2}\text{ }\\ & \text{given }m\text{ at time }t_{1}. \end{align*}$$
For Markov processes, one finds Kolmogorov's forward and backward equations.
Forward equation.

$$\frac{dP_{n/m}(t_2,t_1)}{dt_2}=\sum_{n'}w_{n,n'} P_{n'/m}(t_2,t_1) - w_{n',n}P_{n/m}\left(t_2,t_1)$$

or with t=t₂-t₁,

$$\frac{dP_{n/m}\left( t\right) }{dt}=\sum_{n^{\prime}}w_{n,n^{... ...me}/m}\left( t\right) -w_{n^{\prime},n}P_{n/m}\left( t\right)$$

Backward equation.

$$\frac{dP_{n/m}\left( t_{2},t_{1}\right) }{dt_{1}}=-\sum_{m^{\... ...1}\right) +w_{m^{\prime} ,m}P_{n/m}\left( t_{2},t_{1}\right)$$

or with t=t₂-t₁,

$$\frac{dP_{n/m}\left( t\right) }{dt}=\sum_{m^{\prime}}w_{m^{\p... ...ime}}\left( t\right) -w_{m^{\prime},m}P_{n/m}\left( t\right)$$

Note that we can obtain the master equation by multiplying the both sides of the forward equation by P_m and summing over m, so that one only need worry about state probabilities at time t₂ and not conditional probabilities. For this simple branching process, the backward equation for 1-initial individual boundary conditions is

$$\frac{dP_{n,1}\left( t\right) }{dt}=-\left( \lambda+\beta\right) P_{n/1}+\beta P_{n/2}+\lambda P_{n/0}$$

Using the generating functions
$$\begin{align*}G_{1}\left( z\right) & =\sum_{n=0}^{\infty}P_{n/1}\left( t\right) ... ...\left( z\right) & =\sum_{n=0}^{\infty}P_{n/2}\left( t\right) z^{n} \end{align*}$$
the backward equation becomes

$$\frac{\partial G_{1}( z,t) }{\partial t}=-(\lambda +\beta)G_{1}+\beta G_{2}(z,t)+\lambda,$$

but since

$$G_{m}\left( z,t\right) =\left[ G_{1}\left( z,t\right) \right] ^{m}$$

$$\frac{\partial G_{1}\left( z,t\right) }{\partial t}=-\left( \... ...\beta\right) G_{1}+\beta G_{1}^{2}\left( z,t\right) +\lambda,$$

subject to the initial condition

$$G_{1}\left( z,0\right) =z$$

hence

$$G_{1}\left( z,t\right) =\frac{e^{\left( \lambda-\beta\right) ... ...ht) t}\left( \beta z-\lambda\right) +\beta\left( 1-z\right) }$$

Size distribution. In order to find the size distribution, we look at a generic tree.

The probability of a tree with n leaves is
$$\begin{align*}P_{n} & =\left( \begin{array}[c]{c} \text{\char93 of trees}\\ ... ...ight) ^{2} }\right] ^{n}\left( \frac{\lambda+\beta}{\beta}\right) \end{align*}$$
Using Stirling's formula

$$P_{n}\simeq\frac{1}{2\sqrt{\pi}}n^{-3/2}\left[ \frac{4\lambda... ...^{2}}\right] ^{n}\left( \frac{\lambda+\beta}{2\beta }\right)$$

or

$$n\left( s\right) \simeq\frac{1}{2\sqrt{\pi}}s^{-3/2}e^{-s/a}$$

with the characteristic size

$$a=-\frac{1}{\ln\left( \frac{4\lambda\beta}{\left( \lambda+\beta\right) ^{2}}\right) }$$

So the cumulative size distribution

$$n\left( s\right) \sim s^{-1/2}$$

Exercise. Suppose you didn't know Cayley's formula. You can still calculate the size distribution by using a slightly modified model.

$$\begin{array}{lll} Death:&A\rightarrow R & rate\;\lambda\\ Birth:&A\rightarrow 2A &rate\; \beta\\ \end{array}$$

where R is a `removed' individual. Using a two species generating function

$$G(y,z)=\sum_{n,l}P_{n,l}y^{l}z^{n}$$

One can use either the backward or forward equation and the relevant method above to solve for the $t\rightarrow\infty,\;R$ probabilities.

$$P_{l}=\sum_{n}P_{n,l}$$

Click here for Return to title page
Click here for 7. Absorbing boundaries