
## 5.1 Probability Theoreti Al Preliminaries

Let us re all some basi probabilisti
 
on epts and results that are used subsequently. We denote the probability of an event E by PrfEg and its expe tation by EE. A dis rete

(integer-valued) random variable X is said to be binomial ly distributed with parameters n and p, denoted by X  B(n; p), if

$$\mathbf{Pr}\,\{\,X\,=k\,\}={\binom{n}{k}}p^{k}(1\,-p\,)^{n\,-k}\,,\quad\,k=0,1,\ldots,n\,.$$

:

If X  B(n; p), then its expe
ted value or mean is EX =  = np, varian
e varX = np(1p),
and standard deviation  =

p np(1  p).

An indi ator variable is is a dis rete random variable that takes on only the values 0 and 1. An indi ator variable I is used to denote the o urren e or non-o urren e of an event.

If A1; : : : ; An are independent events with PrfAig = p and IA1

; : : : ; IAn are the respe
tive indi ator variables, then X = Pn i=1 IAi is binomially distributed with parameters n and p.

IAi is alled a Bernoul li random variable with parameter p.

The density fun tion fX : IN ! [0; 1℄ for a dis
rete random variable X is dened as fX(x) = Prf X = x g. The 
umulative distribution fun
tion FX : IN ! [0; 1℄ for X is dened as FX (y) = Prf X  y g = Pxy fX(x).

Let X  B(n; p) be a random variable with mean  = np and standard deviation
 =

p np(1  p). The normalized random variable 
orresponding to X is

$$\widetilde{X}\,=\,\frac{X\,-\,\mu}{\sigma}.$$

:

By the entral limit theorem we an approximate the umulative distribution fun tion F

Xe of Xe by the normal or Gaussian distribution

$$F_{\widetilde{X}}(y)=\mathbf{Pr}\left\{{\widetilde{X}}\,\leq\,y\right\}\approx\Phi(y).$$

 is the umulative distribution fun tion of the bell urve density fun tion ex2=2=
p 2.

Respe tively, we an apply the normal approximation to the orresponding random variable X

$$F_{X}\left(y\right)=\mathbf{Pr}\left\{\,X\leq y\,\,\right\}=F_{\tilde{X}}\left({\frac{y-\mu}{\sigma}}\right)\approx\Phi\left({\frac{y-\mu}{\sigma}}\right)$$

## 5.2 Bounding The Pruning Probability Of A Tree

Now, the pruning set is onsidered to be a sample from a distribution in whi h the lass attribute is independent of the other attributes. We assume that the lass attribute is distributed a ording to Bernoulli(p) distribution; i.e., the 
lass is positive with probability p and negative with probability 1  p. We assume that p > 0:5.

In the following we will analyze the situation in whi h the subtrees rooted at safe nodes have already been pruned into leaves. We bound the pruning probability of the tree starting from this initial onguration. Sin e the bottom-up pruning may already have ome to a halt before that situation, the following results a tually give too high a probability for pruning. Hen e, the following upper bounds are not as tight as possible.

