Fast Simulation of Size-Constrained Multitype Bienaym\'e-Galton-Watson Forests and Applications

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\'e--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\"ive 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).