Observe that Inequality 1 also holds when ni < r, be
ause the 
umulative distribution fun tion  is an in reasing fun tion. The argument ni(p1=2)=
p nip(1  p) 
an be rewritten as pni
p, where 
p is a positive 
onstant depending on the value of p. Sin
e (pni
p) grows as ni grows, 1  (pni
p) grows with de
reasing ni. Hen
e, the lower bound of Inequality 1 also applies for values 0 < ni < r.

Thus, the probability that the half of the safe nodes that re eive at most r examples have a positive ma jority is at most

$$\left(\Phi\left(\frac{(p-1/2)r}{\sqrt{r p(1-p)}}\right)\right)^{k/2}\;.$$
$$\left(2\right)$$

: (2)

This is an upper bound for the probability that the whole tree T will be pruned into a single leaf. The only distribution assumption that was made to rea h the result is that p > :5. In order to obtain tighter bounds, one has to make assumptions about the shape of the tree T

and the distribution of examples.

The bound of Equation 2 depends on the size of the de ision tree (ree ted by k), the number (n) and the lass distribution (p) of the pruning examples. Keeping other parameters onstant and letting k grow redu es the pruning probability exponentially. If the number of pruning examples grows in the same proportion so that r = 2n=k stays 
onstant, the pruning probability still falls exponentially. Class distribution of the pruning examples also ae ts the pruning probability whi h is the smaller, the loser p is to value .5.

## 5.3 Impli Ations Of The Analysis

It has been empiri ally observed that the size of the de ision tree grows linearly with the training set size, even when the trees are pruned (Catlett, 1991; Oates & Jensen, 1997, 1998). The above analysis gives us a possibility to explain this behavior. However, let us rst prove that when there is no orrelation between the attribute values and the lass label of an example, the size of the tree that perfe tly ts the training data depends linearly on the size of the sample.

Our setting is as simple as an be. We only have one real-valued attribute x and the lass attribute y, whose value is independent of that of x. As before, y has two possible values, 0 and 1. The tree is built using binary splits of a numeri al value range; i.e., propositions of type x < r are assigned to the internal leaves of the tree. In this analysis dupli ate instan es o ur with probability 0.

Theorem 6 Let the training examples (x; y) be drawn from a distribution, where x is uniformly distributed in the range [0; 1) and y obtains value 1, independent of x, with probability p, and value 0 with probability 1  p. Then the expe
ted size of the de
ision tree that ts the data is linear in the size of the sample.

Proof Let S = h(x1; y1); : : : ; (xt ; yt)i be a sample of the above des
ribed distribution. We may assume that xi 6= xj , when i 6= j, be
ause the probability of the 
omplement event is 0.

Let us, further, assume that the examples of S have been indexed so that x1 < x2 < : : : < xt .

Let Ai be the indi
ator variable for the event that instan
es i and i + 1 have dierent 
lass labels; i.e., yi 6= yi+1, 1  i  t1. Then EAi = Prf Ai = 1 g = p(1p)+(1p)p = 2p(1p),