Wasserman's AoS, Chapter 8, Question 5

We show here that the number of possible bootstrap samples \(X_1^*, \dotsc, X_n^*\) is

\[ {2n - 1 \choose n - 1}. \]

given a sample \(X_1, \dotsc, X_n\).

In fact, we prove the more general result that the number of ways of choosing a sample (with replacement) of size k from n objects is

\[ {n + k - 1 \choose n - 1}. \]

Wrong Solution

It is tempting to answer that there are \(n^n\) possibilities with the reasoning that there are n free choices for n balls. However, this overcounts the possibilities, which can be verified by hand in the simple case where \(n=k=2\).

Correct Solution

The proof actually counts the number of ways to write down a solution using a certain notation called stars and bars. Consider each of our observations, \(X_i\), as a bucket and each choice as a ball that we put into a bucket. By drawing the k balls in a row, we can show which bucket they fall into by separating the balls with a line. For example, for \(n=4\) and \(k=3\), the choice \(X_3, X_4, X_4\) would be written

||*|**

Similarly, we can write all solutions for \(n=2, k=3\) as

|***
*|**
**|*
***|

The crucial point to note is that we always use \(n + k - 1\) symbols for a solution: \(n-1\) bars and \(k\) balls. Any ordering of these symbols is a solution so we just need to figure out how many orderings there are. The positions of the bars completely determine the positions of the stars. There are \(n + k - 1\) positions in total and we choose \(n-1\) of these to be bars, so there are

\[ {n + k - 1 \choose n - 1} \]

possible solutions.

Example

Here are all 10 possibilities for \(n=k=3\).

||***
|*|**
|**|*
|***|
*||**
*|*|*
*|**|
**||*
**|*|
***||