Trees generated by multi-type branching processes in n steps

Question

I am trying to develop some algorithm to compute probabilities in multi-type branching trees, and I doubt I am doing this right...

Let us consider a multi-type branching process with two types, denoted by 0 and 1. The process starts in state 0 with probability 1, so that the root vertex of any tree generated by this process has state 0. A vertex in state 0 generates two vertices in state 1 with probability 1. A vertex in state 1 generates either two vertices in state 0 (with probability 0.5) or one vertex in state 0 and one vertex in state 1 (with probability 0.5). We denote those three possible transitions by:

• A: 0 -> 1 1 (1.)
• B: 1 -> 0 0 (0.5)
• C: 1 -> 0 1 (0.5)

(their probabilities are between brackets).

In the sequel, a "tree" will refer to an unordered tree, i.e. two isomorphic ordered trees such that the tree isomorphism preserves the labels will be considered as a same mathematical object (following the principle in Chi (2004), p. 1993, paragraph 3 - see link at the end of the post).

Now let us consider the particular labeled tree of height three, composed by one root vertex in state 0 with

• one first child in state 1 that itself has one child in state 0 and one child in state 1
• one second child in state 1 that itself has two children in state 0

This tree should be depicted in some file I am not allowed to post, so I should draw it in ascii mode with limited guarantee on the result:

           0  
           |  
     -------------  
     |           |  
     1           1
     |           |  
 ---------   ---------  
 |       |   |       |  
 0       1   0       0  

I would like to compute the probability that this tree was generated by the above multi-type branching process after 2 generation steps (the generation of the root vertex does not count as a step).

Using equation 2 p. 1994 in Chi (2004), this probability should be 0.25, since each transition A, B and C is applied once. However, each possible tree of height 3 among the three trees generated by this process has probability 0.25, and the sum of the probabilities is 0.75 instead of 1.

Another possibility is to consider that in this given tree, the set of children (0, 0) of vertex 1 may have been generated by any vertex in state 1 (and same principle for the set of children (0, 1)), so that the tree probability is in fact 0.25+0.25 = 0.5.

Finally, how to compute the probability that a given tree t of height n was generated by a multi-type branching process after n-1 generation steps ? Can equation 2 p. 1994 in Chi (2004) be used ? Or do we have to compute the number of trees that are isomorphic to t in some sense ? Or do we have to give up the idea that isomorphic trees are equivalent representations of same object ?

Thanks for your help ! JB

Ref.
Z. Chi. Limit laws of estimators for critical multi-type Galton–Watson processes. Ann. Appl. Probab. Volume 14, Number 4 (2004), 1992-2015.

---

As a beginning of answer to the suggestion of Aniko, I think the following equivalence relation could lead to equivalence classes of trees such that formula (2) could be applied. It consists in adding constraints to the usual notion of isomorphism (by "isomorphism", I mean "an isomorphism preserving labels"). I denote by $I(v)$ the label of vertex $v$, and $t_v$ the complete subtree rooted in $v$. A complete subtree rooted in $v$ is the subgraph induced by the descendants of $v$.

The property $P(t)$ is defined inductively by:

$P(t)$ is satisfied iif $t$ has a single vertex, or if for every pair ${v, v'}$ of children of the root of $t$ such that $I(v)$ = $I(v')$, $t_v$ and $t_{v'}$ are isomorphic and they satisfy $P(t_{v'})$ and $P(t_{v})$.

The two trees $t$ and $t'$ are in the same equivalence class iif [they are isomorphic, and property $P$ is satisfied for $t$ and $t'$] or [$t=t'$].

Answer 1

I think you explained well why the probability of the given tree is 0.5 if its topology does not count. Looking at the formula (2) superficially, I find it hard to imagine the definition of isomorphism under which it would work (only leaves can be rearranged?), though perhaps the trick is in finding the right definition of the counting function f.

For the general case I would try to write a recursive formula, and I think the binomial coefficient should pop uo in it.

Answer 2

Let $\tilde{\omega}$ be the equivalence class of a given tree $\omega$ (i.e. $\omega_1 \sim \omega_2$ iif $\omega_1 \in \tilde{\omega}_2$). In your question, you define a probability (say $\tilde{P}$) on the equivalence class and you want a formula to compute rapidly $\tilde{P}(\tilde{\omega}=\tilde{w})$.

Obviously the trivial formula you though of when you said "compute the number of trees that are isomorphic to t in some sense" is $$\tilde{P}(\tilde{\omega})=\sum_{\omega\in\tilde{\omega}}P(\omega)$$

where $P$ is the probability measure without considering the equivalent class (two isomorphic trees can be different). $P$ is easy to compute from the paper but if the trees are big the preceding formula is not really friendly.

There is a type of equivalence for which you can have a nice formula (such as the one in the paper): it is when your equivalence relation can be restated recursively (according to the tree).

Let $\mathcal{S}_k$ be the group of the bijections of $(1,\dots,k)$ on itself.

Definition 1. $w_1$ and $w_2$ are $\mathcal{S}_k$-equivalent if any node has not more than $k$ sons and if

1. they have the same root (say $s\in V$ )

2. the sons of s in $w_1$ and $w_2$ are equal say to $V_1V_2\dots,V_k$ and there exists $\sigma\in \mathcal{S}_k$ such that

   a. $V_{\sigma(1)}V_{\sigma(2)}\dots V_{\sigma(k)}=V_1V_2\dots V_k$

   b. $\forall i=1\dots,k$ the sub-tree of $w_1$ with root $V_{\sigma(i)}$ is equivalent with the sub-tree of $w_2$ with root $V_{i}$.

To this definition, you can associate another one

Definition 2. Let us define the weigth $q(s->V_1V_2\dots V_k )$ of an occurence of a rule $(s->V_1V_2\dots V_k)$ in a tree $w$ by the number of elements $\sigma$ in $\mathcal{S}$ such that

a. $V_{\sigma(1)}V_{\sigma(2)}\dots V_{\sigma(k)}=V_1V_2\dots V_k$ b. for any $i$ such that $\sigma(i)\neq i$, the subtree generated by $V_{\sigma(i)}$ (in $w$) is not equal to the subtree generated by $V_i$.

with this second definition, and in the case when the equivalent class is defined through $\mathcal{S}_k$ -equivalence, the equation 2 p. 1994 in Chi (2004) is still true if you replace $p(s->n)$ by $q(s->n)p(s->n)$ exept for the transitions giving leaves or when .

In your example

* A: 0 -> 1 1 (1.) has weight 2 (identity+permutation of (1,2)) except if the sons are equal

* B: 1 -> 0 0 (0.5) has weight 2 (identity+permutation of (1,2)) except if the sons are equal

* C: 1 -> 0 1 (0.5) has weigh 1 (only identiy)

Hence your tree has probability 0.5 since each transition is applyed once and only the first one does not give leaves. In the two other tree we are in the case of equal sons (this gives weight 1) and the probabilities are 0.25. These definitions are a bit complicated for a tree with 3 cases... I guess it can lead to fast calculation and can be interesting in the case of a very large tree ?