Hen e, by the above observation,

$${\bf E}\,Q=k{\bf E}\,Q_{1}\,\approx k\Phi\left(\frac{(c-1)n\,/k}{\sqrt{n\,/k(1-1/k)}}\right)\,.\tag{4}$$

We now use Approximation 4 to determine the probability that the whole de ision tree T will be pruned into a single leaf. Let P be a random variable that represent the number of those safe nodes in T that re eive at most 
n=k examples and at least one example. If we denote by R the number of empty safe nodes, we have P = QR. Hen
e, EP = E(QR) =
EQ  ER.

The following result (Kamath, Motwani, Palem, & Spirakis, 1994; Motwani & Raghavan, 1995) lets us approximate the number of empty safe nodes when n  k.

Theorem 7 Let Z be the number of empty bins when m bal ls are thrown randomly into h bins. Then

$$\mu\,=\,\mathbf{E}Z\,=\,h\left(1\,-\,{\frac{1}{h}}\right)^{m}\,\approx\,h e^{-m/h}$$

$$a n\,d\,\,f o\,r\,\,\lambda>0,$$

$$\mathbf{Pr}\left\{\left|Z-\mu\right|\geq\lambda\,\right\}\leq2\exp\left(-{\frac{\lambda^{2}(h-1/2)}{h^{2}-\mu^{2}}}\right)\,.$$

By this result the expe ted number of empty safe nodes is approximately ken=k; this number is small when k is relatively small ompared to n.

Substituting the above obtained approximation for EQ (Equation 4) and using the previous result, we get

$$\mathbf{E}P\,=\mathbf{E}Q\,-\mathbf{E}R\,\approx\,k\left(\Phi\left({\frac{(\,c-1)n\,/k\,}{\sqrt{n\,/k(1-\,1/k)}}}\right)\,-\,e^{-n\,/k}\right)\,.$$

Applying Slud's inequality we an, as before, bound from above the probability that the ma jority lass does not hange in a safe node that re eives 
n=k pruning examples.

Sin e there are P su h safe nodes and the lass distribution of examples within them is independent, the event ma jority lass does not hange in any safe node that re eives at least one and at most 
n=k examples has the upper bound

$$\left(\Phi\left({\frac{(p-.5)r}{\sqrt{r p(1-p)}}}\right)\right)^{P},$$

$$\left(\begin{array}{l}5\end{array}\right)$$ . 
where r = 
n=k. Repla
ing P with its expe
ted value in this equation we have an approximation for the pruning probability. This approximation is valid if P does not deviate a lot from its expe ted value. We onsider the deviation of P from its expe ted value below.

The above upper bound for the pruning probability is similar to the upper bound that was obtained without any assumptions about the distribution of the examples. However, the earlier onstant 2 has been repla ed by a new, ontrollable parameter 
, and empty subtrees are now expli itly taken into a ount. If is hosen suitably, this upper bound is more stri t than the one obtained in the general ase.

