Coding multitype forests: application to the law of the total population of branching forests (Q2787987)

The breadth-first search algorithm associates to each critical or subcritical branching forest its Lukasiewicz-Harris coding path which is a downward skip free random walk. This allows to express the total population of the first \(k\) trees of the forest as the first-passage time of this random walk at level \(-k\). Together with the ballot theorem this allows to compute the law of the total population of the first \(k\) trees in terms of the progeny distribution of the branching process. The paper under review extends the correspondence mentioned above to multitype branching forests. The authors show that such forests can be encoded by \(d\) independent, \(d\)-dimensional integer-valued random walks. Furthermore, they obtain a multivariate generalization of the ballot theorem. Combining both results, they obtain an explicit formula for the law of the total population, jointly with the number of subtrees of each type, in terms of the offspring distribution of the multitype branching process.