A low-rank technique for computing the quasi-stationary distribution of subcritical Galton-Watson processes

Sophie Hautphenne, Stefano Massei

Research output: Contribution to journalArticleAcademicpeer-review

Abstract

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.

Original languageEnglish
Pages (from-to)29-57
Number of pages29
JournalSIAM Journal on Matrix Analysis and Applications
Volume41
Issue number1
DOIs
Publication statusPublished - 2020

Bibliographical note

Funding 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 (stefano.massei@epfl.ch).

Publisher Copyright:
© 2020 Society for Industrial and Applied Mathematics

Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.

Keywords

  • Galton-Watson processes
  • Low-rank approximation
  • Low-rank matrices
  • Quasi-stationary distribution
  • Yaglom limit

Fingerprint Dive into the research topics of 'A low-rank technique for computing the quasi-stationary distribution of subcritical Galton-Watson processes'. Together they form a unique fingerprint.

Cite this