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$
  • $\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 '15 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 '15 at 13:32
  • $\begingroup$ Is it a binary tree? $\endgroup$ – Tianyu Zheng Jun 8 '15 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 '15 at 13:52
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$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.