# Depth distribution of normalized decision trees?

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?

Bye

-

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.