Dlaczego średnio każda próbka bootstrap zawiera około dwie trzecie obserwacji?

Mam natknąć się na twierdzeniu, że każda próbka bootstrap (lub workach drzewa) będą zawierały średnio około $2/3$ z obserwacjami.

I zrozumieć, że prawdopodobieństwo nie wybiera się w jednym z $n$ czerpie $n$ próbek z wymianą jest $(1- 1/n)^n$ , co przekłada się na około $1/3$ przypadek nie zostanie wybrane.

Co jest matematycznym wyjaśnienie dlaczego ta formuła zawsze daje $\approx 1/3$ ?

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

Nie działa przy bardzo małym - np. Przy , . Przechodzi przy , przechodzi przy , a przez . Gdy przekroczysz , jest lepszym przybliżeniem niż .$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}$

Szara linia przerywana to ; czerwona i szara linia to .$\frac{1}{3}$$\frac{1}{e}$

Zamiast przedstawiać formalne wyprowadzenie (które można łatwo znaleźć), przedstawię zarys (jest to intuicyjny, praktyczny argument), dlaczego (nieco) bardziej ogólny wynik zawiera:

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

(Wiele osób podejmuje to być definicja z , ale można to udowodnić z prostszych wyników takich jak definiowanie jako .)$\exp(x)$$e$$\lim_{n\to \infty} \left(1 + 1/n \right)^n$

Fakt 1: Wynika to z podstawowych wyników na temat mocy i potęgowania$\exp(x/n)^n=\exp(x)\quad$

Fakt 2: Gdy jest duże, Wynika to z rozszerzenia szeregu dla .$n$$\exp(x/n) \approx 1+x/n\quad$$e^x$

(Mogę podać pełniejsze argumenty dla każdego z nich, ale zakładam, że już je znasz)

Zastępuje (2) w (1). Gotowy. (Aby działało to jako bardziej formalny argument, zajęłoby trochę pracy, ponieważ musiałbyś wykazać, że pozostałe warunki w Fakcie 2 nie stają się wystarczająco duże, aby spowodować problem, gdy przejmie się władzę . Ale to intuicja zamiast formalnego dowodu).$n$

[Alternatywnie, po prostu weź serię Taylora dla do pierwszego rzędu. Drugim łatwym podejściem jest wzięcie dwumianowego rozszerzenia i przyjęcie limitu termin po semestrze, pokazując, że daje on warunki w szeregu dla .]$\exp(x/n)$$\left(1 + x/n \right) ^n$$\exp(x/n)$

Więc jeśli , wystarczy podstawić .$e^x = \lim_{n\to \infty} \left(1 + x/n \right) ^n$$x=-1$

Natychmiast mamy wynik u góry tej odpowiedzi:$\lim_{n\to\infty}(1- 1/n)^n=e^{-1}$

---

Jak wskazuje Gung w komentarzach, wynikiem twojego pytania jest pochodzenie reguły 632 bootstrap

np. patrz

Efron, B. i R. Tibshirani (1997),
„Improvements on Cross-Validation: The .632+ Bootstrap Method”,
Journal of the American Statistics Association Vol. 92, nr 438. (Jun), s. 548–560

Dokładniej, każda próbka bootstrap (lub spakowane drzewo) będzie zawierać próbki.$1-\frac{1}{e} \approx 0.632$

Zobaczmy, jak działa bootstrap. Mamy oryginalną próbkę z elementami w niej. Rysujemy elementy z zamiennikiem z tego oryginalnego zestawu, dopóki nie otrzymamy innego zestawu o rozmiarze .$x_1, x_2, \ldots x_n$$n$$n$

Z tego wynika, że ​​prawdopodobieństwo wybrania dowolnego elementu (powiedzmy ) przy pierwszym losowaniu wynosi . Dlatego prawdopodobieństwo nie wybrania tego elementu wynosi . To tylko pierwsze losowanie; jest w sumie losowań, z których wszystkie są niezależne, więc prawdopodobieństwo, że nigdy nie wybierzesz tego elementu na żadnym z losowań, wynosi .$x_1$$\frac{1}{n}$$1 - \frac{1}{n}$$n$$(1-\frac{1}{n})^n$

Zastanówmy się teraz, co się stanie, gdy coraz większe. Możemy przyjąć limit, gdy idzie w kierunku nieskończoności, używając zwykłych sztuczek rachunku różniczkowego (lub Wolfram Alpha): $n$$n$

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

Takie jest prawdopodobieństwo, że element nie zostanie wybrany. Odejmij go od jednego, aby znaleźć prawdopodobieństwo wyboru przedmiotu, co daje 0,632.

Pobieranie próbek z wymianą można modelować jako sekwencję prób dwumianowych, w których wybierany jest „sukces”. Dla oryginalnego zestawu danych instancji prawdopodobieństwo „sukcesu” wynosi , a prawdopodobieństwo „awarii” wynosi . Dla wielkości próbki prawdopodobieństwo wybrania instancji dokładnie razy daje rozkład dwumianowy:$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}$$

W konkretnym przypadku próbki ładowania początkowego wielkość próbki jest równa liczbie instancji . Pozwalając zbliżyć się do nieskończoności, otrzymujemy:$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!}$$

Jeśli nasz oryginalny zestaw danych jest duży, możemy użyć tej formuły do ​​obliczenia prawdopodobieństwa, że ​​wystąpienie zostanie wybrane dokładnie razy w próbce ładowania początkowego. Dla prawdopodobieństwo wynosi lub około . Prawdopodobieństwo, że próbka zostanie co najmniej raz pobrana, wynosi zatem .$x$$x = 0$$1/e$$0.368$$1 - 0.368 = 0.632$

Nie trzeba dodawać, że skrupulatnie wyprowadziłem to z pióra i papieru i nawet nie rozważałem użycia Wolfram Alpha.

Dodając do odpowiedzi @ retsreg, można to również dość łatwo zademonstrować za pomocą symulacji numerycznej w 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

Można to łatwo zliczyć. Ile wszystkich możliwych próbek? n ^ n. Ile NIE zawiera określonej wartości? (n-1) ^ n. Prawdopodobieństwo, że próbka nie będzie miała określonej wartości - (1-1 / n) ^ n, co stanowi około 1/3 granicy.