Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Lets work with the following inductive definition of a decision tree:

1) $\bot$, $\top$ are decision trees.
2) If $x_i$ is a variable and $T_0$, $T_1$ are decision trees then $(\lnot x_i \land T_0) \lor (x_i \land T_1)$ is a decision tree.

Let's assume a truth table $f:\{0,1\}^n -> \{0,1\}$ over the variables $x_1$, ..., $x_n$. The truth table can be readily turned into a decision tree $T$. If $n=0$ then pick either $\bot$ or $\top$ depending of $f$. If $n>0$ then pick $(\lnot x_1 \land T_0) \lor (x_1 \land T_1)$ where $T_0$ is the decision tree for $\lambda x_2,...,x_n f(0,x_2,...,x_n)$ and where $T_1$is the decision tree for $\lambda x_2,...,x_n f(1,x_2,...,x_n)$.

The above algorithm yields balanced complete trees. Their depth distribution is simple, we have P(d=j|n=j) = 1. So they have all a depth that corresponds to the number of variables.

Now we perform a normalization. Given a tree $T$, if there is a subtree $(\lnot x_i \land T') \lor (x_i \land T')$ then replace it by $T'$. Repeat until no more subtrees are replaced. Basically we shorten nodes with equivalent left and right branches. It shouldn't matter in which order we do the shortening.

What is the distribution P(.|.) of these normalized decision trees?


share|cite|improve this question
up vote 2 down vote accepted

It's not difficult to write a recurrence relation. Denote by $f(n,d)$ the number of function of $n$ variables where the depth is $d$. We have $$ \begin{align*} f(0,d) &= \begin{cases} 2 & d = 0, \\ 0 & d \neq 0. \end{cases} \\ f(n+1,d+1) &= f(n,d+1) + 2\sum_{c \leq d} f(n,d) f(n,c) + f(n,d)(f(n,d)-1). \end{align*} $$ From that you can determine the probabilities, using the fact that there are $2^{2^n}$ functions on $n$ variables.

share|cite|improve this answer
You can try doing this yourself - please tell us what you get... – Yuval Filmus Aug 27 '11 at 7:31

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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