Boostrap sample probability question

1. Dec 17, 2012

infk

If we have $x_1, \ldots , x_n$, all distinct values, and then sample from this with replacement and thus obtain a bootstrap sample $x^{\star}_1, \ldots , x^{\star}_n$, what is the probability that the bootstrap sample has only two unique values?

My attempt at a solution:

there are $\binom{n}{2}$ possible pairs in the original sample.
When sampling with replacement, there are $n^n$ possible bootstrap samples. The number of ways that two unique values can occur is $n-1$ so the sought-for probability is:
$\binom{n}{2} \frac{n-1}{n^n}$.

Last edited: Dec 17, 2012
2. Dec 17, 2012

awkward

You have $n^n$ possible samples, which we assume are all equally likely. In order to find the probability that a sample contains only two unique values, you need to count the number of cases which meet that critereon. So ask yourself...

1. How many ways can you choose the two unique values?

2. Given two unique values, how many samples of size n can you choose which contain only those values?

3. Dec 17, 2012

infk

1. There are $\binom{n}{2}$ ways to do that.

2. There should be in total $n$ recordings of the only two unique values. If the first one occurs once, the other one must occur $n-1$ times, or the first one occurs twice, then the other one occurs $n-2$ times, and so on and so forth, giving in total $n-1$ possible ways two distribute the two unique values in the bootstrap sample.

These two steps combined means that the probability is $\binom{n}{2} \frac{n-1}{n^n}$, but this is incorrect (why?)

Alternatively, the probability of choosing either of the two $n$ times is $\frac{2^n}{n^n}$. It is also true that for 2 given distinct values this can occur in $n-1$ ways. Thus the probability of choosing two given values $n$ times is $\frac{2^n}{n^n}(n-1)$. Moreover, this holds for excactly $\binom{n}{2}$ pairs of values.
So the probability is $\binom{n}{2}\frac{2^n}{n^n}(n-1) = \binom{n}{2}\left( \frac{2^n(n-1)}{n^n}\right)$. According to the solution, the correct answer should be:
$\binom{n}{2}\left( \frac{2^n}{n^n} - \frac{2}{n^n}\right)$

Last edited: Dec 17, 2012
4. Dec 17, 2012

awkward

You are off on your answer to 2. If you have coins numbered 1 through n, each of which can be heads or tails (and order counts), how many arrangements are possible?

(Two of those arrangements are special, because they are either all tails or all heads.)

Last edited: Dec 17, 2012