# Ensemble of Classifiers Method (Bagging)

I am reading a book about classification systems. They tell me that Bagging is a technique where "we perform sampling with replacement, building the classifier on each bootstrap sample. Each sample has probability $1-(1/N)^N$ of being selected."

What could they mean by this? Probably this is quite easy but somehow I do not get it. N is the number of classifier combinations (=samples), right? Why is the formula given above right? Why isn't the probability of a sample being selected simply $1/N$?

• My notes said the chance for a sample to be selected at least once is $1-\left(1-\frac1N\right)^N$. – peterwhy Nov 15 '13 at 17:30

1. The probability of being selected in some particular trial is $1/N$.
2. The probability of not being selected in some particular trial is $1-1/N$.
3. The probability of not being selected in any of $M$ trials is $(1-1/N)^M$, since the events are independent.
4. The probability of being selected at least once in $M$ trials is $1-(1-1/N)^M$, since this event is complementary to 3.
If the number of trial is equal to the size $N$, you get $1-(1-1/N)^N$, as in peterwhy's comment. The formula $1-(1/N)^N$ gives the probability of not being selected at least once in $N$ trials. (Because $(1/N)^N$ is the probability of being selected in every trial.)