We onsider pruning a de ision tree by rep as a trial whose result is de ided by the set of pruning examples. By Theorem 4 we an approximate the probability that a tree will be pruned into a ma jority leaf by approximating the probability that al l safe nodes get a positive ma jority or a negative ma jority. The latter alternative is not very probable under the assumption p > :5. It is safe to assume that it never happens.

We an onsider sampling the pruning examples in two phases. First the attribute values are assigned. This de ides the leaf into whi h the example falls. In the se ond phase we independently assign the lass label for the example.

Let the safe nodes of tree T be Z(T ) = fz1; : : : ; zkg and let the number of examples in the pruning set S be jSj = n. The number of pruning examples falling to a safe node zi is denoted by ni; Pk i=1 ni = n. For the time being we assume that ni > 0 for all i. The number of positive examples falling to safe node zi is the sum of independent Bernoulli variables and, thus, it is binomially distributed with parameters ni and p. Respe
tively, the number of negative pruning examples in safe node zi is Xi  B(ni; 1p). The probability that there is a ma jority of negative examples in safe node zi is Prf Xi > ni=2 g. We 
an bound this probability from below by using the following inequality (Slud, 1977).

Lemma 5 (Slud's inequality) Let X  B(m; q) be a random variable with q  1=2. Then for m(1  q)  h  mq,

$$\mathbf{Pr}\,\{\,X\,\geq\,h\,\}\geq1\,-\,\Phi\left({\frac{h-\,m\,q}{\sqrt{\,m\,q(1\,-\,q)\,}}}\right)\,.$$

Sin e p > :5 and the random variable 
orresponding to the number of negative examples in safe node zi is Xi  B(ni; 1p), the rst 
ondition of Slud's inequality holds. Furthermore, to see that ondition m(1  q)  h  mq holds in safe node zi substitute h = ni=2, m = ni, and q = 1  p to obtain nip  ni=2  ni(1  p). Thus,

$$\mathbf{Pr}\left\{X_{i}>\frac{n_{i}}{2}\right\}\geq1-\,\Phi\left(\frac{n_{i}/2-n_{i}(1-p)}{\sqrt{n_{i}p(1-p)}}\right)=1-\,\Phi\left(\frac{(p-1/2)n_{i}}{\sqrt{n_{i}p(1-p)}}\right).\tag{1}$$

As ni, the number of pruning instan
es rea
hing safe node zi, grows, then the standard normal distribution term in the above bound also grows. Hen e, the bound on the probability that the ma jority of the pruning examples rea hing zi is negative is the smaller the more pruning examples rea h it. The probability of a negative ma jority also redu es through the growing probability of positive lass for an example, p. These both are also ree
ted in the pruning probabilities of the whole tree.

We an now roughly approximate the probability that T will be pruned into a single ma jority leaf as follows. By Theorem 4, T will be pruned into a leaf if and only if ea h safe node in T re eives a ma jority of positive examples. Be ause T has k safe nodes and there are n pruning examples, then a ording to the pigeon-hole prin iple at least half of the safe nodes re eive at most r = 2n=k examples. Ea
h safe node zi with ni  r examples has, by Inequality 1, a negative ma jority at least with probability

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