¿Por qué en promedio cada muestra de bootstrap contiene aproximadamente dos tercios de las observaciones?

He correr a través de la afirmación de que cada muestra bootstrap (o árbol de embolsado) contendrán en promedio aproximadamente $2/3$ de las observaciones.

Yo entiendo que la posibilidad de no ser seleccionado en cualquiera de $n$ extrae de $n$ muestras con reemplazo es $(1- 1/n)^n$ , lo que equivale a aproximadamente $1/3$ posibilidad de no ser seleccionado.

¿Qué es una explicación matemática de por qué esta fórmula siempre da $\approx 1/3$ ?

$\lim_{n\to\infty}(1- 1/n)^n=e^{-1}$
$e^{-1} =1/e \approx 1/3$

No funciona en muy pequeño , por ejemplo, en , . Pasa en , pasa en y en . Una vez que vaya más allá de , es una mejor aproximación que .$n$$n=2$$(1- 1/n)^n=\frac{1}{4}$$\frac{1}{3}$$n=6$$0.35$$n=11$$0.366$$n=99$$n=11$$\frac{1}{e}$$\frac{1}{3}$

La línea discontinua gris está en ; la línea roja y gris está en .$\frac{1}{3}$$\frac{1}{e}$

En lugar de mostrar una derivación formal (que se puede encontrar fácilmente), voy a dar un resumen (que es un argumento intuitivo y manual) de por qué un resultado (ligeramente) más general es válido:

$$e^x = \lim_{n\to \infty} \left(1 + x/n \right)^n$$

(Muchas personas consideran que esto es la definición de , pero puede probarlo a partir de resultados más simples, como definir como .)$\exp(x)$$e$$\lim_{n\to \infty} \left(1 + 1/n \right)^n$

Hecho 1: Esto se desprende de los resultados básicos sobre potencias y exponenciación$\exp(x/n)^n=\exp(x)\quad$

Hecho 2: cuando es grande, Esto se deduce de la expansión de la serie para .$n$$\exp(x/n) \approx 1+x/n\quad$$e^x$

(Puedo dar argumentos más completos para cada uno de estos, pero supongo que ya los conoce)

Sustituya (2) en (1). Hecho. (Para que esto funcione como un argumento más formal tomaría algo de trabajo, porque tendrías que demostrar que los términos restantes en el Hecho 2 no se vuelven lo suficientemente grandes como para causar un problema cuando se toma el poder . Pero esto es intuición en lugar de una prueba formal).$n$

[Alternativamente, solo tome la serie Taylor para en primer orden. Un segundo enfoque fácil es tomar la expansión binomial de tomar el límite término por término, mostrando que da los términos en la serie para .]$\exp(x/n)$$\left(1 + x/n \right) ^n$$\exp(x/n)$

Entonces, si , simplemente sustituya .$e^x = \lim_{n\to \infty} \left(1 + x/n \right) ^n$$x=-1$

Inmediatamente, tenemos el resultado en la parte superior de esta respuesta,$\lim_{n\to\infty}(1- 1/n)^n=e^{-1}$

---

Como Gung señala en los comentarios, el resultado en su pregunta es el origen de la regla de arranque 632

por ejemplo, ver

Efron, B. y R. Tibshirani (1997),
"Mejoras en la validación cruzada: el método Bootstrap .632+",
Journal of the American Statistical Association vol. 92, núm. 438. (junio), págs. 548-560

Más precisamente, cada muestra de bootstrap (o árbol en bolsas) contendrá de la muestra.$1-\frac{1}{e} \approx 0.632$

Veamos cómo funciona el bootstrap. Tenemos una muestra original con elementos en ella. Dibujamos artículos con reemplazo de este conjunto original hasta que tengamos otro conjunto de tamaño .$x_1, x_2, \ldots x_n$$n$$n$

De eso, se deduce que la probabilidad de elegir cualquier elemento (digamos, ) en el primer sorteo es . Por lo tanto, la probabilidad de no elegir ese elemento es . Eso es solo para el primer sorteo; hay un total de sorteos, todos los cuales son independientes, por lo que la probabilidad de nunca elegir este elemento en ninguno de los sorteos es .$x_1$$\frac{1}{n}$$1 - \frac{1}{n}$$n$$(1-\frac{1}{n})^n$

Ahora, pensemos en lo que sucede cuando hace más y más grande. Podemos tomar el límite cuando va hacia el infinito, usando los trucos de cálculo habituales (o Wolfram Alpha): $n$$n$

$$\lim_{n \rightarrow \infty} \big(1-\frac{1}{n}\big)^n = \frac{1}{e} \approx 0.368$$

Esa es la probabilidad de que un artículo no sea ​​elegido. Resta de uno para encontrar la probabilidad de que el elemento sea elegido, lo que te da 0.632.

El muestreo con reemplazo se puede modelar como una secuencia de ensayos binomiales donde se selecciona el "éxito". Para un conjunto de datos original de instancias, la probabilidad de "éxito" es la probabilidad de "falla" es . Para un tamaño de muestra de , la distribución binomial da las probabilidades de seleccionar una instancia exactamente veces:$n$$1/n$$(n-1)/n$$b$$x$

$$P(x,b,n) = \bigl(\frac{1}{n}\bigr)^{x} \bigl(\frac{n-1}{n}\bigr)^{b-x} {b \choose x}$$

En el caso específico de una muestra de bootstrap, el tamaño de la muestra es igual al número de instancias . Dejando que acerque al infinito, obtenemos:$b$$n$$n$

$$\lim_{n \rightarrow \infty} \bigl(\frac{1}{n}\bigr)^{x} \bigl(\frac{n-1}{n}\bigr)^{n-x} {n \choose x} = \frac{1}{ex!}$$

Si nuestro conjunto de datos original es grande, podemos usar esta fórmula para calcular la probabilidad de que una instancia se seleccione exactamente veces en una muestra de arranque. Para , la probabilidad es , o aproximadamente . La probabilidad de que una instancia se muestree al menos una vez es, por lo tanto, .$x$$x = 0$$1/e$$0.368$$1 - 0.368 = 0.632$

No hace falta decir que deduje minuciosamente esto con lápiz y papel, y ni siquiera consideré usar Wolfram Alpha.

Simplemente agregando a la respuesta de @retsreg esto también se puede demostrar con bastante facilidad a través de la simulación numérica en R:

N <- 1e7 # number of instances and sample size
bootstrap <- sample(c(1:N), N, replace = TRUE)
round((length(unique(bootstrap))) / N, 3)
## [1] 0.632

Esto se puede ver fácilmente contando. ¿Cuántas muestras posibles totales? n ^ n. ¿Cuántos NO contienen un valor específico? (n-1) ^ n. Probabilidad de que una muestra no tenga un valor específico - (1-1 / n) ^ n, que es aproximadamente 1/3 en el límite.