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

Sophie Hautphenne; Stefano Massei

doi:10.1137/19M1241647

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

Sophie Hautphenne, Stefano Massei

Research output: Contribution to journal › Article › Academic › peer-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 language	English
Pages (from-to)	29-57
Number of pages	29
Journal	SIAM Journal on Matrix Analysis and Applications
Volume	41
Issue number	1
DOIs	https://doi.org/10.1137/19M1241647
Publication status	Published - 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 ([email protected]).

Publisher Copyright:
© 2020 Society for Industrial and Applied Mathematics

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

Funding

∗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 protected]).

Keywords

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

Access to Document

10.1137/19M1241647

Cite this

@article{19b3a4612396475d81b77e2867e238f7,

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

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.",

keywords = "Galton-Watson processes, Low-rank approximation, Low-rank matrices, Quasi-stationary distribution, Yaglom limit",

author = "Sophie Hautphenne and Stefano Massei",

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 ([email protected]). Publisher Copyright: {\textcopyright} 2020 Society for Industrial and Applied Mathematics Copyright: Copyright 2020 Elsevier B.V., All rights reserved.",

year = "2020",

doi = "10.1137/19M1241647",

language = "English",

volume = "41",

pages = "29--57",

journal = "SIAM Journal on Matrix Analysis and Applications",

issn = "0895-4798",

publisher = "Society for Industrial and Applied Mathematics (SIAM)",

number = "1",

}

TY - JOUR

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

AU - Hautphenne, Sophie

AU - Massei, Stefano

N1 - 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 ([email protected]). Publisher Copyright: © 2020 Society for Industrial and Applied Mathematics Copyright: Copyright 2020 Elsevier B.V., All rights reserved.

PY - 2020

Y1 - 2020

N2 - 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.

AB - 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.

KW - Galton-Watson processes

KW - Low-rank approximation

KW - Low-rank matrices

KW - Quasi-stationary distribution

KW - Yaglom limit

UR - https://www.scopus.com/pages/publications/85084938813

U2 - 10.1137/19M1241647

DO - 10.1137/19M1241647

M3 - Article

AN - SCOPUS:85084938813

SN - 0895-4798

VL - 41

SP - 29

EP - 57

JO - SIAM Journal on Matrix Analysis and Applications

JF - SIAM Journal on Matrix Analysis and Applications

IS - 1

ER -

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

Abstract

Bibliographical note

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this