# What are the most and least likely samples in a bootstrap?

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.

• 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! – Guilherme Marthe Mar 25 at 16:28
• @Xi'an I think that my addition is what you suggested, right? – Guilherme Marthe Mar 25 at 20:33
• 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)). – Xi'an Mar 26 at 7:34