An algorithm for solving systems of quadratic equations in branching processes
The author considers Markovian binary trees that evolve according to the following set of rules:NEWLINENEWLINE\noindent (1) At each time instant, a finite number of individuals exists.NEWLINENEWLINE\noindent (2) Each individual has one of \(N\) types.NEWLINENEWLINE\noindent (3) Individuals evolve independently of each other. At every discrete time, an individual of type \(i\) has a fixed probability \(b_{ijk}\) of being replaced by two individuals of types \(j\) and \(k\), and a fixed probability \(a_i\) of dying without producing any offspring.NEWLINENEWLINEThe dynamics of the process is thus determined by \(a \in \mathbb{R}_+^N\) and \(b \in \mathbb{R}_+^{N \times N \times N}\). The author also writes \(b\) for the function NEWLINE\[NEWLINEb : \mathbb{R}_+^N \times \mathbb{R}_+^N \to \mathbb{R}_+^N,\, (u,v) \mapsto (\sum_{j,k=1}^N b_{ijk} u_j v_k)_{i=1,\dots,N}.NEWLINE\]NEWLINE Let \(x = (x_1,\dots,x_N)\), where \(x_i\) denotes the probability that such a process starting from a single individual of type \(i\) becomes eventually extinct. It is known that \(x\) is the minimal nonnegative solution to the quadratic equation \(x = a+b(x,x)\).NEWLINENEWLINEIn the present paper, the author briefly reviews several known algorithms for computing the extinction probability \(x\), and further proposes a Perron vector-based algorithm for the computation of \(x\). While the new algorithm may fail to converge for problems that are far from the critical case, it is constructed to be more efficient in the near-critical case than the previously known algorithms. The author reports numerical experiments supporting the claim that the algorithm is indeed faster in near-critical cases.
- On the solution of a quadratic vector equation arising in Markovian binary trees.
- Newton's iteration for the extinction probability of a Markovian binary tree
- Algorithmic approach to the extinction probability of branching processes
- A Perron Iteration for the Solution of a Quadratic Vector Equation Arising in Markovian Binary Trees
- The modified Newton-Shamanskii method for the solution of a quadratic vector equation arising in Markovian binary trees
- A modified Newton method for the quadratic vector equation arising in Markovian binary trees
- Perturbation analysis of the extinction probability of a Markovian binary tree
- A Perron Iteration for the Solution of a Quadratic Vector Equation Arising in Markovian Binary Trees
- A structured Markov chain approach to branching processes
- On the solution of a quadratic vector equation arising in Markovian binary trees.
- A low-rank technique for computing the quasi-stationary distribution of subcritical Galton-Watson processes
- Algorithmic approach to the extinction probability of branching processes
This page was built for publication: An algorithm for solving systems of quadratic equations in branching processes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2869433)
