This question is question 60 of chapter 1 of Introduction to Probability by Blitzstein and Hwang.

Basically the question walks you through reasoning about the bootstrap sampling procedure. Given $(a_1, ..., a_n)$ non-repeated numbers, $n\geq2$, you create a sample by sampling $n$ observations with replacement.

The question is: let $\textbf{b}_1$ be the most likely bootstrap sample, an $p_1$ the probability of getting $\textbf{b}_1$ and let $\textbf{b}_2$ be the least likely bootstrap sample, an $p_2$ the probability of getting $\textbf{b}_2$. What is $\frac{p_1}{p_2}$?

In my studies I found that:

a) there are $n^n$ ordered samples, since for each element of a sample, there are $n$ choices.

b) there are ${2n - 1 \choose n}$ unordered samples due to the stars and bars argument.

c) some samples from the ordered scheme are more represented in the unordered case.


I think I have the question figured out, I just don't have a way of checking1.

When you compare the ordered samples to the unordered samples, one can see that some will be more represented and other less. For example take, with $n=2$ and $(a_1, a_2) = (3, 1)$. The ordered samples are $(1,1)$, $(3,1)$, $(1,3)$ and $(3,3)$. In the unordered case, the sample $(3,1)$ is more likely then $(1, 1)$ by a factor of 2. This gives us a hint that the number of permutations of the sample is the key.

Generically, the least likely sample $\textbf{b}_2$ is one where all the numbers are the same, since there is only one way of forming that sample. There are $n$ ways of getting a one element bootstrap sample, one for each element of $(a_1, ..., a_n)$. So $p_2 = \frac{n}{n^n} = \frac{1}{n^{n-1}}$.

Now, the most likely sample $\textbf{b}_1$ is the one where there are the most number of permutations. That is, the one where all elements of $\textbf{b}_1$ are different and therefore is equal to $(a_1, ..., a_n)$, since one repetition would cause the number of permutations to decrease. There is only one unordered sample where all elements are the same, that is $(a_1, ..., a_n)$. And there are $n!$ number of ways to sample it from the ordered samples. So $p_1 = \frac{n!}{n^n} = \frac{(n-1)!}{n^{n-1}}$.

Conclusively, $\frac{p_1}{p_2} = (n-1)!$ making $\textbf{b}_1$ $(n-1)!$ times more likely then $\textbf{b}_2$ during the sampling process.

Update with the probability of an arbitrary sample, as a suggestion by @Xi'an. A bootstrap sample boils down to the following:

  • which elements were sampled ($k$ as the number of elements)
  • how many times each element was sampled ($k_i$ as the number of times element $i$ was sampled, such that $\sum_{i=1}^{n}k_i = n$)
  • how many permutations can be made given the previous.

So, the number of ways to choose $k$ numbers from the $n$ $(a_1,..., a_n)$ is simply ${n \choose k}$. And so, given the vector of counts $$\textbf{v} = (k_1,...k_n) $$ such that $\sum_{i=1}^{n}k_i = n$, we can form the multinomial coefficient representing the permutations with repeated elements ${n \choose \textbf{v}}$ or equivalently ${n \choose k_1,...k_n} = \frac{n!}{k_1! \cdot ... \cdot k_n!}$ .

This leads to, by the multiplication rule, to the following probability:

$$ p_{k, \textbf{v}} = \frac{{n \choose k}\cdot{n \choose k_1,...,k_n}}{n^n} $$

For the cases of the sample $\textbf{b}_1$, $\textbf{b}_2$ the probabilities $p_1$ and $p_2$ are represented by $p_{n, (1,1,...,1)}$ and $p_{1, (n, 0,...0)}$, respectively. They simplify to:

$$ p_1 = p_{n, (1,1,...,1)} = \frac{{n \choose n}\cdot{n \choose 1,...,1}}{n^n} = \frac{1\cdot n!}{n^n} = \frac{(n-1)!}{n^{n-1}} $$

$$ p_2 = p_{1, (n, 0,...,0)} = \frac{{n \choose 1}\cdot{n \choose n,0,...,0}}{n^n} = \frac{n \cdot 1}{n^n} = \frac{1}{n^{n-1}} $$

1 I also just love the bootstrap, and take any chance of understanding it more technically.

| cite | improve this answer | |
  • 1
    $\begingroup$ Ah, yes! I was thinking of that. It would relate to the multinomial coefficient, since there would be repeated elements. I'll just think of a nice notation and update the answer! $\endgroup$ – Guilherme Marthe Mar 25 at 16:28
  • $\begingroup$ @Xi'an I think that my addition is what you suggested, right? $\endgroup$ – Guilherme Marthe Mar 25 at 20:33
  • $\begingroup$ Thanks for the addition. I am uncertain though that it is the correct answer. Check for instance Feller (1970, vol. 1, Section II.5, p.39, eqn (5.3)). $\endgroup$ – Xi'an Mar 26 at 7:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.