Research in Scientific Computing in Undergraduate Education

Multi-type branching processes with dependent offspring

The general theory of branching processes has been generalized to branching processes in which the population comprises multiple types (Mode, 1971). Multi-type branching processes have recently been considered in which offspring are potentially dependent (Gonzalez, Martinez & Mota, 2006).

Such processes arise already in relation to percolation on the integer lattice \mathbb{Z}\times \mathbb{Z}. To see how this occurs, consider a situation in which each bond in \mathbb{Z}\times \mathbb{Z} is open with probability p. We regard the site (0,0) as a base-point and look at geodesics (= shortest-length paths) of bonds from the base-point to another site. The length of a geodesic is the number of bonds comprising the geodesic:

Geodesic of length 4

If you prefer the language of graphs to that of percolation theory, replace “bond” with “edge” and “site” with “vertex”.

The geodesics come in three types:

Type 0

The unique geodesic of type 0 is the empty geodesic of length 0.

Type 1

Geodesic of type 1 - terminating at a site $latex (m,0) \textrm{ or }or (0,n)$

Type 2

Geodesic of type 2 - terminating at a site $latex (m,n) \textrm{ with }m\neq 0\neq n$

There is an obvious notion of offspring of a geodesic – a geodesic \gamma_1 of length n  has as offspring those geodesics \gamma_2 of length n+1 that contain \gamma_1 as sub-paths. Following the model of percolation, we regard the bonds as open with probability p, and correspondingly, regard the geodesics as giving birth to offspring with probability p. The unique geodesic of length 0 gives birth to 4 geodesics of type 1, each geodesic of type1 gives birth to 1 geodesic of type 1 and 2 geodesics of type 2, and each geodesic of type 2 gives birth to 2 geodesics of type 2, all with probability p. The birth of offspring geodesics is not independent:

Dependent geodesics of length 3
Dependent geodesics of length 3

The blue and red geodesics shown are not independent when 0<p<1: \mathbb{P}(\textrm{red}\vert \textrm{blue})=p^2\neq p^3 =\mathbb{P}(\textrm{red}).

The first aim of this project is to establish computational evidence for, and determine general conditions under which, there is a phase transition from extinction with probability 1 to extinction with probability 0 in multi-type branching processes with dependent offspring. We know that this will happen at p = \frac{1}{2} for the integer lattice, because that is the percolation threshold. Can we ascertain this from general facts about multi-type branching processes with dependent offspring?

References & readings


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: