6
$\begingroup$

Given a tree-structure with a root node, the node can either get zero, one or two children, all with the same probability of 1/3. The children also has the same probability of getting zero, one or two children, which is 1/3. Recursively the algorithm creates the tree. What is the probability that the tree has more than N nodes in total?

Came across this question after programming a random tree generator and got really curious, would be cool if someone knew the answer.

$\endgroup$
  • 1
    $\begingroup$ Have you done anything on this? Have you set up an equation that you can't solve, or what? $\endgroup$ – saulspatz Feb 19 '18 at 1:05
  • $\begingroup$ I believe that if $p(n)$ is the probability of having a tree with exactly $n$ nodes gives $p(1) = 1/3$ and $$p(n) = \frac{1}{3}f(n-1) + \frac{1}{3}\sum_{k=1}^{n-1}f(k)f(n-1-k)$$. Very hard recurrence to solve... You're obviously interested in $g(n) = \sum_{k\geq n}f(k)$. $\endgroup$ – orlp Feb 19 '18 at 1:38
  • $\begingroup$ Shouldn't the problem specify the number of branching events? What's the probability that the tree has more than N nodes after k steps etc? It could be that the number of nodes are unbounded as k goes to infinity? $\endgroup$ – AnlamK Feb 19 '18 at 11:47
  • $\begingroup$ Update: Sorry, extinction occurs with probability 1 in this case, as k goes to infinity - so the tree has to die at some point. And I just realized the number of steps doesn't matter for the probability in question. $\endgroup$ – AnlamK Feb 19 '18 at 12:01
  • $\begingroup$ Sorry, I misread the question as the parent node doesn't disappear in this case. I confused it with some other problem. $\endgroup$ – AnlamK Feb 19 '18 at 12:08
1
$\begingroup$

Interesting question! Not a full answer, but an interesting problem representation that could lead to solutions. Too long for a comment.


For this analysis the only thing that's really relevant is the number of 'live' ends where the tree can grow. We start with $1$ live end. At each step a live end is explored, replacing it with 0, 1, or 2 new live ends. View each number of live ends as a state $k$, at each step we have the chance of going to a state with $k-1, k$ or $k+1$ live ends. If we hit state $0$ we are stuck there.

Let's represent our possibilities as a polynomial $f_n(x)$, where $n$ is the number of steps, and the coefficient of $x^k$ tells us the probability of being in state $k$ after $n$ steps. Initially we have $f_0(x) = x$, we have a 100% chance of having $1$ live end. Note that $f_n(0)$ is neatly the probability of hitting state $0$ after $n$ steps.

Now the beauty of this representation is that $f_{n+1}(x) = \frac{1}{3}(x^{-1} + 1 + x) \cdot (f_{n}(x) - f_{n}(0)) + f_{n}(0)$, cancelling fractions such as $x^2 \cdot x^{-1} = x$ (so that we do not divide by zero later).

Since $f_n(0)$ is exactly the chance that after $n$ steps our tree is no longer growing, if we want to know the probability of our tree having at least $n$ nodes we simply look at $1 - f_{n-1}(0)$.


Let's be crazy, and instead of looking directly at the value of $f_n(0)$, let's look at the limit instead. We also reorder terms a bit:

$$\lim_{x\to 0}\quad f_{n+1}(x) = \frac{1}{3}(1 + x + x^2) \frac{f_{n}(x) - f_{n}(0)}{x} +f_{n}(0)$$

Doesn't that remind you of something?

$$\lim_{x\to 0}\quad f_{n+1}(x) = \frac{1}{3}(1 + x + x^2) f'_n(x) +f_{n}(0)$$ $$f_{n+1}(0) = \frac{1}{3} f'_n(0) +f_{n}(0)$$

This looked really exciting until I realized that $f'_n(0)$ is simply the coefficient of state $1$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ How can you say there are only three states? Suppose I get 2 new nodes the first 3 times. Then I have 4 lives ends, don't I? I don't follow this at all. $\endgroup$ – saulspatz Feb 19 '18 at 3:09
  • $\begingroup$ @saulspatz There are an infinite number of states. $\{-1, 0, +1\}$ referred to going from $n$ to $\{n-1, n, n+1\}$. I clarified that a bit. $\endgroup$ – orlp Feb 19 '18 at 3:11
1
$\begingroup$

Let $T_n$ be the number of ordered, rooted trees with $n$ nodes, where each node has degree $\le 3.$ These are exactly the $n$-node trees that can be generated by the random process. The probability that a given $n$-node tree is generated is $3^{-n},$ for each node is associated with a factor of $1/3,$ the probability that of having the number of children it has (or does not have, in the case of the leaves.) Therefore, the probability of generating a tree with exactly $n$ nodes is $$p_n=3^{-n}T_n.$$

$T_n$ satisfies the recurrence relation $$T_n = T_{n-1} + \sum_{k=1}^{n-2}{T_kT_{n-1-k}},\tag{1}$$ since the root may have either a single subtree with $n-1$ nodes, or two subtrees, one with $k$ nodes and one with $n-k-1$ nodes.

Notice that we distinguish the case where the first subtree has $k$ nodes from the case where the second subtree has $k$ nodes. This is what makes it an ordered tree. It's not the same thing as a binary tree, for when there is only one subtree we don't care if it the left or right subtree. It's clear from the description of the random process that this is the kind of tree we want.

Now $(1)$ is almost identical to the recurrence relation for the Motzkin numbers $$M_n = M_{n-1} + \sum_{k=0}^{n-2}{M_kM_{n-2-k}},$$ and $T_1=M_0=1, T_2=M_1=1,$ so that $T_n=M_{n-1},$ and $\boxed{p_n=3^{-n}M_{n-1}}.$

The Wikipedia article linked above gives a more convenient formula for calculating the Motzkin numbers a s a three-term recurrence, and a closed-form expression as a sum involving binomial coefficients and Catalan numbers.

Using this closed form expression, I was able to obtain a closed-form formula for the OP's question, for the OP's question, but I can't see how to simplify it into something more useful than computing the $p_n'$s individually and adding them up. For what it's worth,$$ Pr(X>M)= 1 - \sum_{n=1}^{M-1}\sum_{k=0}^{\lfloor (n-1)/2\rfloor}{\left[\binom{n-1}{k,k,n-1-2k}-\binom{n-1}{k+1,k-1,n-1-2k}\right]} $$

| 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.