11
$\begingroup$

Just want to check some reasoning.

If my original sample is of size $n$ and I bootstrap it, then my thought process is as follows:

$\frac{1}{n}$ is the chance of any observation drawn from the original sample. To ensure the next draw is not the previously sampled observation, we restrict the sample size to $n-1$. Thus, we get this pattern:

$$ \frac{1}{n} \cdot \frac{1}{n-1} \cdot \frac{1}{n-2} \cdots \frac{1}{n-(n-1)} = \frac{1}{n!}. $$

Is this correct? I stumble on why it can't be $(\frac{1}{n})^n$ instead.

$\endgroup$
7
  • 1
    $\begingroup$ I'm not sure I'm following you. Why do you want to "ensure the next draw is not the previous sample"? In bootstrapping, the idea is to sample with replacement. That is, you do want it to be possible that the next draw is the same as one you've already drawn. $\endgroup$ Jan 23, 2017 at 2:07
  • $\begingroup$ but won't that mean the bootstrapped sample is not the same as the original sample? $\endgroup$
    – Jayant.M
    Jan 23, 2017 at 2:15
  • $\begingroup$ I don't follow you. You don't necessarily want the bootsample to be identical to your sample, you just want to treat the sample as a model of the population. $\endgroup$ Jan 23, 2017 at 2:26
  • 1
    $\begingroup$ So my question is what is the chance that the bootstrap sample IS the same as the original sample. I am interested in the bootstrap being identical to the sample $\endgroup$
    – Jayant.M
    Jan 23, 2017 at 2:36
  • $\begingroup$ Sorry if my question wasn't clear! $\endgroup$
    – Jayant.M
    Jan 23, 2017 at 2:37

1 Answer 1

17
$\begingroup$

Note that at each observation position ($i=1, 2, ..., n$) we can choose any of the $n$ observations, so there are $n^n$ possible resamples (keeping the order in which they are drawn) of which $n!$ are the "same sample" (i.e. contain all $n$ original observations with no repeats; this accounts for all the ways of ordering the sample we started with).

For example, with three observations, a,b and c, you have 27 possible samples:

aaa aab aac aba abb abc aca acb acc 
baa bab bac bba bbb bbc bca bcb bcc 
caa cab cac cba cbb cbc cca ccb ccc 

Six of those contain one each of a, b and c.

So $n!/n^n$ is the probability of getting the original sample back.

Aside - a quick approximation of the probability:

Consider that:

$${\displaystyle {\sqrt {2\pi }}\ n^{n+{\frac {1}{2}}}e^{-n}\leq n!\leq e\ n^{n+{\frac {1}{2}}}e^{-n}}$$

so

$${\displaystyle {\sqrt {2\pi }}\ n^{{\frac {1}{2}}}e^{-n}\leq n!/n^n \leq e\ n^{{\frac {1}{2}}}e^{-n}}$$

With the lower bound being the usual one given for the Stirling approximation (which has low relative error for large $n$).

[Gosper has suggested using $n! \approx \sqrt{(2n+\frac13)\,\pi}n^ne^{-n}$ which would yield the approximation $\sqrt{(2n+\frac13)\pi}\,e^{-n}$ for this probability, which works reasonably well down to $n=3$, or even down to $n=1$ depending on how stringent your criteria are.]


(Response to comment:) The probability of not getting a particular observation in a given resample is $(1-\frac{1}{n})^n$ which for large $n$ is approximately $e^{-1}$.

For details see
Why on average does each bootstrap sample contain roughly two thirds of observations?

$\endgroup$
7
  • $\begingroup$ Thank you! as a point of interest, what is the chance of not getting a particular entry in a sample? for example with the distribution of $a,b,c$ you gave, there is a 8/27 chance of not getting a sample with an $a$ $\endgroup$
    – Jayant.M
    Jan 23, 2017 at 3:14
  • 1
    $\begingroup$ That's already covered in other answers on site but I've added it above (briefly). $\endgroup$
    – Glen_b
    Jan 23, 2017 at 3:26
  • 1
    $\begingroup$ So, this is the probability of getting a sample which is a permutation of the original sample. Instead, the probability of getting exactly the same sequence as in the original sample (thus, same elements in the same order) is $(\frac {1}{n})^n$. Right? $\endgroup$
    – DeltaIV
    Jan 23, 2017 at 8:32
  • 1
    $\begingroup$ @deltaiv yes, only one of the $n!$ arrangements is in the original order. $\endgroup$
    – Glen_b
    Jan 23, 2017 at 9:07
  • 1
    $\begingroup$ Doesn’t Gosper’s approximation work well even down to $n=1$, not just down to $n=3$? I think 0.499 (for $n=2$) is a pretty good approximation to 0.5, and 0.996 (for $n=1$) is also quite close to 1.0. $\endgroup$ Jan 26, 2017 at 21:45

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.