Fast Simulation of Size-Constrained Multitype Bienaymé-Galton-Watson Forests and Applications
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2020
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911638997696512 |
|---|---|
| author | Hernández, Osvaldo Angtuncio |
| author_facet | Hernández, Osvaldo Angtuncio |
| contents | The degree sequence $(n_{i,j}(k), 1\leq i,j\leq d, k\geq 0)$ of a multitype forest with $d$ types encodes the number of individuals of type $i$ with $k$ children of type $j$. In this paper, we introduce a simple algorithm to sample a multitype forest uniformly from the set of all forests with a given degree sequence (MFGDS). This generalizes the single-type construction of Broutin and Marckert (2014). To achieve this, we extend the Vervaat transform (1979) to multidimensional discrete exchangeable increment processes.
We demonstrate that MFGDS extend multitype Bienaymé--Galton--Watson (MBGW) forests. Specifically, mixing MFGDS laws recovers MBGW forests conditioned on a fixed size for each type (CMBGW). Under general assumptions, we derive the law of the total population by types in an MBGW forest and relate it to a multidimensional first-hitting time. This result, which is of independent interest, generalizes the Otter--Dwass (1949,1969) and Kemperman (1950) formulas.
By combining this relation with our MFGDS construction, we provide an efficient algorithm to simulate CMBGW forests, generalizing the work of Devroye (2012). When the variance is finite, the expected simulation time outperforms standard naïve methods. For the proof we derive a generalized local limit theorem for multidimensional first-hitting times. Finally, we apply our results to enumerate plane, labeled, and binary multitype forests with fixed sizes, generalizing results of Pitman (1998). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2003_03036 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | Fast Simulation of Size-Constrained Multitype Bienaymé-Galton-Watson Forests and Applications Hernández, Osvaldo Angtuncio Probability Combinatorics 60C05, 60F99, 60G09, 60G50, 05C05, 60-08 The degree sequence $(n_{i,j}(k), 1\leq i,j\leq d, k\geq 0)$ of a multitype forest with $d$ types encodes the number of individuals of type $i$ with $k$ children of type $j$. In this paper, we introduce a simple algorithm to sample a multitype forest uniformly from the set of all forests with a given degree sequence (MFGDS). This generalizes the single-type construction of Broutin and Marckert (2014). To achieve this, we extend the Vervaat transform (1979) to multidimensional discrete exchangeable increment processes. We demonstrate that MFGDS extend multitype Bienaymé--Galton--Watson (MBGW) forests. Specifically, mixing MFGDS laws recovers MBGW forests conditioned on a fixed size for each type (CMBGW). Under general assumptions, we derive the law of the total population by types in an MBGW forest and relate it to a multidimensional first-hitting time. This result, which is of independent interest, generalizes the Otter--Dwass (1949,1969) and Kemperman (1950) formulas. By combining this relation with our MFGDS construction, we provide an efficient algorithm to simulate CMBGW forests, generalizing the work of Devroye (2012). When the variance is finite, the expected simulation time outperforms standard naïve methods. For the proof we derive a generalized local limit theorem for multidimensional first-hitting times. Finally, we apply our results to enumerate plane, labeled, and binary multitype forests with fixed sizes, generalizing results of Pitman (1998). |
| title | Fast Simulation of Size-Constrained Multitype Bienaymé-Galton-Watson Forests and Applications |
| topic | Probability Combinatorics 60C05, 60F99, 60G09, 60G50, 05C05, 60-08 |
| url | https://arxiv.org/abs/2003.03036 |