Почему в среднем каждый образец начальной загрузки содержит примерно две трети наблюдений?

Я перебежать утверждение , что каждый образец самозагрузки (или в мешках дерево) будет содержать в среднем примерно $2/3$ наблюдений.

Я понимаю , что шанс не был выбран в любом из $n$ черпает из $n$ образцов с замены $(1- 1/n)^n$ , которая работает примерно $1/3$ шанс не был выбран.

Что такое математическое объяснение , почему эта формула всегда дает $\approx 1/3$ ?

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

Он не работает при очень малых $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}$ .

Серая пунктирная линия находится в $\frac{1}{3}$ ; красно-серая линия находится в $\frac{1}{e}$ .

Вместо того, чтобы показывать формальный вывод (который легко найти), я собираюсь дать план (это интуитивно понятный аргумент), почему (немного) более общий результат имеет место:

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

(Многие люди принимают это будет определение из , но вы можете доказать это из более простых результатов , таких как определение , как .)$\exp(x)$$e$$\lim_{n\to \infty} \left(1 + 1/n \right)^n$

Факт 1: Это следует из основных результатов о степенях и возведении в степень$\exp(x/n)^n=\exp(x)\quad$

Факт 2: Когда большое, Это следует из разложения в ряд для .$n$$\exp(x/n) \approx 1+x/n\quad$$e^x$

(Я могу дать более полные аргументы для каждого из них, но я предполагаю, что вы уже знаете их)

Заменить (2) в (1). Выполнено. (Чтобы это работало как более формальный аргумент, потребовалась бы некоторая работа, потому что вам нужно было бы показать, что оставшиеся термины в факте 2 не становятся достаточно большими, чтобы вызвать проблему при переходе к степени . Но это интуиция а не формальное доказательство.)$n$

[В качестве альтернативы просто возьмите ряд Тейлора для до первого порядка. Второй простой подход состоит в том, чтобы взять биномиальное разложение и взять ограничение по терминам, показывая, что оно дает члены в ряду для .]$\exp(x/n)$$\left(1 + x/n \right) ^n$$\exp(x/n)$

Так что если , просто подставьте .$e^x = \lim_{n\to \infty} \left(1 + x/n \right) ^n$$x=-1$

Сразу же у нас есть результат в верхней части этого ответа,$\lim_{n\to\infty}(1- 1/n)^n=e^{-1}$

---

Как указывает Ганг в комментариях, результатом вашего вопроса является происхождение правила начальной загрузки 632

например, см.

Efron, B. и R. Tibshirani (1997),
«Усовершенствования перекрестной проверки: метод начальной загрузки .632+»,
журнал Американской статистической ассоциации Vol. 92, № 438. (Jun), с. 548-560.

Точнее, каждый образец начальной загрузки (или дерево в мешках) будет содержать образца.$1-\frac{1}{e} \approx 0.632$

Давайте рассмотрим, как работает бутстрап. У нас есть оригинальный образец с элементами в нем. Мы рисуем элементы с заменой из этого исходного набора, пока у нас не будет другого набора размера .$x_1, x_2, \ldots x_n$$n$$n$

Из этого следует, что вероятность выбора какого-либо одного предмета (скажем, ) в первом тираже равна . Следовательно, вероятность того, что вы не выберете этот элемент, равна . Это только для первого розыгрыша; Всего существует ничьих, все из которых независимы, поэтому вероятность того, что этот пункт никогда не будет выбран ни в одной из ничьих, равна .$x_1$$\frac{1}{n}$$1 - \frac{1}{n}$$n$$(1-\frac{1}{n})^n$

Теперь давайте подумаем о том, что происходит, когда становится все больше и больше. Мы можем взять предел, когда стремится к бесконечности, используя обычные трюки с исчислением (или Wolfram Alpha): $n$$n$

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

Это вероятность того, что предмет не выбран. Вычтите его из единицы, чтобы найти вероятность выбора предмета, что дает 0,632.

Выборка с заменой может быть смоделирована как последовательность биномиальных испытаний, где «успех» является выбранным экземпляром. Для исходного набора данных из экземпляров вероятность «успеха» равна , а вероятность «отказа» равна . Для размера выборки вероятность выбора экземпляра ровно раз определяется биномиальным распределением:$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}$$

В конкретном случае выборки начальной загрузки размер выборки равен числу экземпляров . Позволяя приближаться к бесконечности, мы получаем:$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!}$$

Если наш исходный набор данных большой, мы можем использовать эту формулу для вычисления вероятности того, что экземпляр будет выбран ровно раз в образце начальной загрузки. Для вероятность составляет или примерно . Таким образом, вероятность выборки экземпляра хотя бы один раз составляет .$x$$x = 0$$1/e$$0.368$$1 - 0.368 = 0.632$

Само собой разумеется, я кропотливо получил это, используя ручку и бумагу, и даже не думал об использовании Wolfram Alpha.

Просто добавив к ответу @ retsreg, это также можно легко продемонстрировать с помощью численного моделирования в 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

Это можно легко увидеть, считая. Сколько всего возможных образцов? п ^ п. Сколько НЕ содержит определенного значения? (П-1) ^ п. Вероятность того, что образец не имеет определенного значения - (1-1 / n) ^ n, что составляет около 1/3 в пределе.