Ensemble of Classifiers Method (Bagging)

Question

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$?

Answer 1

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.)