We present a new algorithm for computing the quasi-stationary distribution of subcritical Galton-Watson branching processes. This algorithm is based on a particular discretization of a well-known functional equation that characterizes the quasi-stationary distribution of these processes. We provide a theoretical analysis of the approximate low-rank structure that stems from this discretization, and we extend the procedure to multitype branching processes. We use numerical examples to demonstrate that our algorithm is both more accurate and more efficient than other approaches.
Bibliographical noteFunding Information:
∗Received by the editors January 30, 2019; accepted for publication (in revised form) October 18, 2019; published electronically January 9, 2020. https://doi.org/10.1137/19M1241647 Funding: The work of the first author was supported by the Australian Research Council through the Discovery Early Career Researcher Award DE150101044. The work of the second author was supported by the SNSF research project Fast algorithms from low-rank updates, grant 200020 178806. †The University of Melbourne, Australia and EPF Lausanne, Switzerland (sophiemh@unimelb. edu.au). ‡EPF Lausanne, Switzerland (email@example.com).
© 2020 Society for Industrial and Applied Mathematics
Copyright 2020 Elsevier B.V., All rights reserved.
- Galton-Watson processes
- Low-rank approximation
- Low-rank matrices
- Quasi-stationary distribution
- Yaglom limit