Warum enthält jede Bootstrap-Stichprobe im Durchschnitt ungefähr zwei Drittel der Beobachtungen?

Ich habe über die Behauptung ausgeführt , dass jede Bootstrap Probe (oder eingetütet Baum) im Durchschnitt enthält etwa $2/3$ der Beobachtungen.

Ich verstehe , dass die Wahrscheinlichkeit , sich in keiner der ausgewählt ist $n$ von zieht $n$ Proben mit Ersatz ist $(1- 1/n)^n$ , die etwa ausarbeitet $1/3$ Chance, nicht ausgewählt zu werden.

Was ist eine mathematische Erklärung dafür , warum diese Formel immer gibt $\approx 1/3$ ?

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

Es funktioniert nicht bei sehr kleinem - zB bei , . Es passiert bei , passiert bei und bei . Wenn Sie über hinausgehen , ist eine bessere Annäherung als .$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}$

Die graue gestrichelte Linie befindet sich bei . Die rote und graue Linie befindet sich bei .$\frac{1}{3}$$\frac{1}{e}$

Anstatt eine formale Ableitung zu zeigen (die leicht gefunden werden kann), werde ich einen Umriss (das ist ein intuitives, handwaviges Argument) geben, warum ein (etwas) allgemeineres Ergebnis gilt:

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

(Viele Leute halten dies für die Definition von , aber Sie können es durch einfachere Ergebnisse wie die Definition von als beweisen .)$\exp(x)$$e$$\lim_{n\to \infty} \left(1 + 1/n \right)^n$

Fakt 1: Dies folgt aus grundlegenden Ergebnissen über Potenzen und Potenzierung$\exp(x/n)^n=\exp(x)\quad$

Fakt 2: Wenn groß ist, Dies folgt aus der Reihenerweiterung für .$n$$\exp(x/n) \approx 1+x/n\quad$$e^x$

(Ich kann zu jedem dieser Punkte ausführlichere Argumente anführen, aber ich gehe davon aus, dass Sie sie bereits kennen.)

Ersetzen Sie (2) in (1). Getan. (Damit dies als formelleres Argument funktioniert, ist etwas Arbeit erforderlich, da Sie zeigen müssen, dass die verbleibenden Terme in Fakt 2 nicht groß genug werden, um ein Problem zu verursachen, wenn sie zur Potenz . Aber das ist Intuition eher als formeller Beweis.)$n$

[Alternativ können Sie auch die Taylor-Reihe für zur ersten Ordnung nehmen. Ein zweiter einfacher Ansatz besteht darin, die Binomialerweiterung von nehmen und das Limit termweise zu bestimmen. Dabei werden die Terme in der Reihe für .]$\exp(x/n)$$\left(1 + x/n \right) ^n$$\exp(x/n)$

Wenn also , ersetzen Sie einfach .$e^x = \lim_{n\to \infty} \left(1 + x/n \right) ^n$$x=-1$

Wir haben sofort das Ergebnis oben in dieser Antwort:$\lim_{n\to\infty}(1- 1/n)^n=e^{-1}$

---

Wie Gung in Kommentaren ausführt, ist das Ergebnis Ihrer Frage der Ursprung der 632-Bootstrap-Regel

zB sehen

Efron, B. und R. Tibshirani (1997),
"Improvements on Cross-Validation: The .632+ Bootstrap Method",
Journal der American Statistical Association Vol. 92, Nr. 438. (Jun), S. 548-560

Genauer gesagt enthält jedes Bootstrap-Beispiel (oder jeder eingesackte Baum) des Beispiels.$1-\frac{1}{e} \approx 0.632$

Sehen wir uns an, wie der Bootstrap funktioniert. Wir haben ein Originalmuster von mit Elementen. Wir zeichnen Artikel mit Ersatz aus diesem Originalsatz, bis wir einen weiteren Satz der Größe .$x_1, x_2, \ldots x_n$$n$$n$

Daraus folgt, dass die Wahrscheinlichkeit, einen Gegenstand (zB ) bei der ersten Ziehung zu wählen, . Daher ist die Wahrscheinlichkeit , diesen Gegenstand nicht zu wählen, . Das ist nur für die erste Auslosung; Es gibt insgesamt Ziehungen, die alle unabhängig voneinander sind. Daher ist die Wahrscheinlichkeit, dass Sie diesen Gegenstand bei keiner Ziehung auswählen, .$x_1$$\frac{1}{n}$$1 - \frac{1}{n}$$n$$(1-\frac{1}{n})^n$

Überlegen wir nun, was passiert, wenn immer größer wird. Wir können die Grenze nehmen, wenn gegen Unendlich geht, indem wir die üblichen Kalkültricks (oder Wolfram Alpha) : $n$$n$

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

Das ist die Wahrscheinlichkeit, dass ein Gegenstand nicht ausgewählt wird. Subtrahieren Sie es von eins, um die Wahrscheinlichkeit zu ermitteln, mit der der ausgewählte Artikel ausgewählt wird. Dies ergibt 0,632.

Die Abtastung mit Ersetzung kann als Folge von Binomialversuchen modelliert werden, bei denen "Erfolg" eine ausgewählte Instanz ist. Für einen ursprünglichen Datensatz von Instanzen beträgt die Wahrscheinlichkeit eines "Erfolges" und die Wahrscheinlichkeit eines "Scheiterns" . Bei einer Stichprobengröße von ergibt sich die Wahrscheinlichkeit, dass eine Instanz genau mal ausgewählt wird, aus der Binomialverteilung:$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}$$

Im speziellen Fall eines Bootstrap-Beispiels entspricht die Beispielgröße der Anzahl der Instanzen . Letting gegen unendlich, erhalten wir:$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!}$$

Wenn unser ursprünglicher Datensatz groß ist, können wir diese Formel verwenden, um die Wahrscheinlichkeit zu berechnen, dass eine Instanz in einem Bootstrap-Beispiel genau mal ausgewählt wird. Für beträgt die Wahrscheinlichkeit oder ungefähr . Die Wahrscheinlichkeit, dass eine Instanz mindestens einmal abgetastet wird, beträgt somit .$x$$x = 0$$1/e$$0.368$$1 - 0.368 = 0.632$

Unnötig zu erwähnen, dass ich dies sorgfältig mit Stift und Papier hergeleitet habe und nicht einmal daran gedacht habe, Wolfram Alpha zu verwenden.

Wenn Sie nur die Antwort von @ retsreg hinzufügen, können Sie dies auch ganz einfach durch numerische Simulation in R demonstrieren:

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

Dies kann leicht durch Zählen gesehen werden. Wie viele mögliche Proben insgesamt? n ^ n. Wie viele enthalten keinen bestimmten Wert? (n-1) ^ n. Wahrscheinlichkeit, dass eine Stichprobe keinen bestimmten Wert hat - (1-1 / n) ^ n, was etwa 1/3 der Grenze entspricht.