3
$\begingroup$

I start with a one-node tree. Then I repeatedly choose a node uniformly at random and add a child node to it, stopping when there are a certain number of nodes.

Treating all nodes as equivalent and ignoring the order of children of a node, I'd like to calculate the probabiity of producing a given shape of tree.

For example, there is only 1 way to produce the 1 or 2 node tree, so each of those are 100% likely if I stop at 1 or 2 nodes. If I'm producing a 3-node tree then I might get A->B->C or C<-A->B, each with 50% probability depending on which of A or B was chosen before adding C. From either of those trees, D could get inserted in one of three places (as a child of A, B, or C), but some of those results are equivalent:

1. A->B->C
   `->D

2. A->B->C
      `->D

3. A->B->C->D

4. A->B
   |->C
   `->D

5. A->B->D
   `->C

6. A->B
   `->C->D

1, 5, and 6 are all the same tree structure, so there's a 50% chance of producing that tree, and a 16.67% chance of producing each of the other three (2, 3, 4).

$\endgroup$
4
  • $\begingroup$ Does the order in which the node are added matter? I mean: are D<-B<-A->C and C<-B<-A->D the same shape? $\endgroup$
    – wece
    Jun 8, 2015 at 10:17
  • 1
    $\begingroup$ No. The nodes are indistinct once they are added. I've only lettered them for convenience of describing the process. $\endgroup$
    – Sparr
    Jun 8, 2015 at 13:32
  • $\begingroup$ Is it a binary tree? $\endgroup$ Jun 8, 2015 at 13:49
  • $\begingroup$ @TianyuZheng no. As described, the parent for each new child is chosen at random from all previous nodes. $\endgroup$
    – Sparr
    Jun 8, 2015 at 13:52

1 Answer 1

3
$\begingroup$

There are $(k-1)!$ possible trees with $k$ nodes generated by your algorithm. We now compute, given a shape $T=(N,E)$, the number of trees generated by your algorithm of shape $T$.

First some notations: given an edge $e=(n_1,n_2)\in E$ we denote $\#(e)$ the number of edges in the sub-tree with root $n_2$ plus one.

We define inductively $g(n)$ the number of way to generate the sub-tree of root $n$.

  • If $n$ is a leaf then $g(n)=1$.
  • If there is only one edge $e=(n,n_1)\in E$ out of $n$ then $g(n)=g(n_1)$
  • Otherwise let $e_1=(n,n_1);\dots;e_l=(n,n_l)$ be the set of all edges going out of $n$. $$g(n)=\prod_{i=1}^{l-1}{\sum_{j=1}^{i+1} \#(e_j)\choose \#e_{i+1}}.\prod_{i=1}^{l}g(n_i) $$ Intuitively, the second product correspond to the number of way to produce all the sub-trees independently. And the first product correspond to the number of interleaving in such productions.

The probability to generate a particular shape of size $k$ and root $n$ is thus: $$ \frac{g(n)}{(k-1)!} $$

On the first shape you gave

 A->B->C
  `->D

it would give:

$g(C)=g(D)=1$ since $C$ and $D$ are leaves. $g(B)=g(C)=1$. And finally $g(A)={3\choose 1}g(D).g(B)=3$.

Thus the probability is $g(A)/((4-1)!)=1/2$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .