Latin Hypercube Sampling Asymptotics

Ich versuche, einen Beweis für ein Problem zu erstellen, an dem ich arbeite, und eine der Annahmen, die ich mache, ist, dass die Menge der Punkte, von denen ich Stichproben mache, über den gesamten Raum dicht ist. Praktisch verwende ich Latin Hypercube Sampling, um meine Punkte über den gesamten Probenraum zu erhalten. Was ich gerne wissen würde, ist, ob lateinische Hypercube-Samples über den gesamten Raum dicht sind, wenn Sie Ihre Sample-Größe zu tendieren lassen $\infty$? Wenn ja, wäre ein Zitat für diese Tatsache sehr dankbar.

Kurze Antwort: Ja, auf probabilistische Weise. Es ist möglich zu zeigen, dass wir bei jedem Abstand , jeder endlichen Teilmenge { x 1 , … , x m } des Probenraums und jeder vorgeschriebenen 'Toleranz' δ > 0 für geeignet große Probengrößen sicher sein können, dass Die Wahrscheinlichkeit, dass es einen Abtastpunkt innerhalb eines Abstands ϵ von x i gibt, ist > 1 - δ für alle i = 1 , … $\epsilon>0$$\{x_1,…,x_m\}$$\delta>0$$\epsilon$$x_i$$>1-\delta$ .$i=1,…,m$

Lange Antwort: Mir sind keine direkt relevanten Zitate bekannt (siehe aber unten). Der größte Teil der Literatur zur Latin Hypercube Sampling (LHS) bezieht sich auf die Varianzreduktionseigenschaften. Das andere Problem ist, was bedeutet es zu sagen, dass die Stichprobengröße zu tendiert ? Für eine einfache IID-Zufallsstichprobe kann eine Stichprobe der Größe n aus einer Stichprobe der Größe n - 1 erhalten werden, indem eine weitere unabhängige Stichprobe angehängt wird. Für LHS glaube ich nicht, dass Sie dies tun können, da die Anzahl der Proben im Rahmen des Verfahrens im Voraus festgelegt wurde. Es scheint also, dass Sie eine Reihe unabhängiger LHS-Proben der Größe 1 , 2 , 3 nehmen müssten $\infty$$n$$n-1$$1,2,3,...$.

Es muss auch eine Möglichkeit geben, "dicht" im Grenzbereich zu interpretieren, da die Stichprobengröße tendenziell zu tendiert . Die Dichte scheint für LHS nicht deterministisch zu sein, z. B. in zwei Dimensionen. Sie können eine Folge von LHS-Proben der Größe 1 , 2 , 3 , . . . so dass sie alle an der Diagonale von [ 0 , 1 ) 2 festhalten . Es scheint also eine Art probabilistische Definition notwendig zu sein. Für jedes n sei X n = ( X n 1 , X n 2 , . $\infty$$1,2,3,...$$[0,1)^2$$n$ festhalten, sei eine Probe der Größe n, die nach einem stochastischen Mechanismus erzeugt wurde. Angenommen, für verschiedene n sind diese Stichproben unabhängig. Um dann die asymptotische Dichte zu definieren, benötigen wir dies möglicherweise für jeden$X_n=(X_{n1},X_{n2},...,X_{nn})$$n$$n$ und für jedes x im Probenraum (angenommen [ 0 , 1 ) d ) P ( m i n 1 ≤ k ≤ n ‖ X. n k - x ‖ ≥ $\epsilon>0$$x$$[0,1)^d$ (als n → ∞ ).$P(min_{1\leq k\leq n} \|X_{nk}-x\|\geq \epsilon)\to0$$n\to \infty$

Wenn die Probe wird berechnet, indem erhält n unabhängige Proben aus dem U ( [ 0 , 1 ) , d ) Verteilung ( 'IID Stichproben') , dann P ( m i n 1 ≤ k ≤ n ‖ X n k - x ‖ ≥ ϵ ) = n ∏ k = 1 P ( ‖ X n k - x ‖ ≥ $X_n$$n$$U([0,1)^d)$ wobei v ϵ das Volumen der d- dimensionalen Kugel mit dem Radius ϵ ist . IID-Zufallsstichproben sind also sicherlich asymptotisch dicht.

Betrachten Sie nun den Fall, dass die Proben durch LHS erhalten werden. Satz 10.1 in diesen Anmerkungen besagt, dass die Mitglieder der Stichprobe X n alle als U ( [ 0 , 1 ) d ) verteilt sind . Die bei der Definition von LHS verwendeten Permutationen (obwohl für verschiedene Dimensionen unabhängig) induzieren jedoch eine gewisse Abhängigkeit zwischen den Mitgliedern der Probe ( X n k , k ≤ $X_n$$X_n$$U([0,1)^d)$$X_{nk}, k\leq n$ ), so dass es weniger offensichtlich ist, dass die Eigenschaft der asymptotischen Dichte gilt.

Fix und x ∈ [ 0 , 1 ) d . Definieren P n = P ( m i n 1 ≤ k ≤ n ‖ X n k - x ‖ ≥ & egr; ) . Wir wollen zeigen, dass P n → 0 ist . Zu diesem Zweck können wir in diesen Anmerkungen Satz 10.3 verwenden , der eine Art zentraler Grenzwertsatz für die lateinische Hypercube-Abtastung darstellt. Definiere f : $\epsilon\gt 0$$x\in [0,1)^d$$P_n=P(min_{1\leq k\leq n} \|X_{nk}-x\|\geq \epsilon)$$P_n\to 0$ durch f ( z ) = 1, wenn z in der Kugel mit dem Radius ϵ um x liegt ,andernfalls f ( z ) = 0 . Dann sagt uns Satz 10.3, dass Y n : = $f:[0,1]^d\to\mathbb{R}$$f(z)=1$$z$$\epsilon$$x$$f(z)=0$woμ=∫ [ 0 , 1 ] d f(z$Y_n:=\sqrt n (\hat{\mu}_{LHS}-\mu)\xrightarrow{d} N(0,\Sigma)$ , und μ L H S = $\mu=\int_{[0,1]^d} f(z) dz$ .$\hat{\mu}_{LHS}=\frac{1}{n}\sum_{i=1}^n f(X_{ni})$

Nimm . Schließlich haben wir für groß genug n - $L>0$$n$. Schließlich haben wir alsoPn=P(Yn=-$-\sqrt n\mu\lt -L$. Daher istlim supPn≤lim supP(Yn<-L)=Φ( - $P_n=P(Y_n=-\sqrt n \mu)\le P(Y_n\lt -L)$, wobeiΦdas normale Standard-cdf ist. DaLbeliebig war, folgt, dassPn→0nach Bedarf ist.$\limsup P_n\le \limsup P(Y_n\lt -L)=\Phi(\frac{-L}{\sqrt\Sigma})$$\Phi$$L$$P_n\to 0$

Dies beweist die asymptotische Dichte (wie oben definiert) sowohl für die Zufallsstichprobe als auch für die LHS. Informell bedeutet dies, dass bei einem beliebigen und einem beliebigen x im Stichprobenraum die Wahrscheinlichkeit, dass die Stichprobe innerhalb von ϵ von x liegt , so nahe an 1 gebracht werden kann, wie Sie möchten, indem Sie die ausreichend große Stichprobengröße auswählen. Es ist einfach, das Konzept der asymptotischen Dichte so zu erweitern, dass es auf endliche Teilmengen des Probenraums angewendet wird - indem das, was wir bereits wissen, auf jeden Punkt in der endlichen Teilmenge angewendet wird. Formal bedeutet dies, dass wir zeigen können: für jede ϵ > 0 und jede endliche Teilmenge { x 1 , . . . , $\epsilon$$x$$\epsilon$$x$$\epsilon>0$ des Probenraums ist m i n 1 ≤ j ≤ m P ( m i n 1 ≤ k ≤ n ‖ X n k - x j ‖ < ϵ ) → 1 (als n → ∞ ).$\{x_1,...,x_m\}$$min_{1\leq j\leq m} P(min_{1\leq k\leq n} \|X_{nk}-x_j\|\lt \epsilon)\to 1$$n\to\infty$

Ich bin mir nicht sicher, ob dies genau das ist, was Sie wollen, aber hier geht es weiter.

Sie sind LHS-Abtastung von Punkten aus [ 0 , 1 ) d , sagen wir. Wir werden sehr informell argumentieren, dass für jedes ϵ > 0 die erwartete Anzahl leerer (Hyper-) Quader der Größe ϵ in jeder Dimension als n → ∞ auf Null geht .$n$$[0,1)^d$$\epsilon>0$$\epsilon$$n\to\infty$

Lassen so dass , wenn wir unterteilen [ 0 , 1 ) d gleichmäßig in m d kleine Quader - microcuboids , sagen sie - mit einer Breite von 1 / m dann jedem breiten- ε Quader mindestens eine microcuboid enthält. Wenn wir also zeigen können, dass die erwartete Anzahl nicht abgetasteter Mikrokuboide Null ist, in der Grenze als n → ∞ , dann sind wir fertig. (Beachten Sie, dass unsere Mikrokuboide in einem regelmäßigen Gitter angeordnet sind, die ϵ- Kuboide sich jedoch in jeder Position befinden können.)$m=\lceil 2/\epsilon \rceil$$[0,1)^d$$m^d$$1/m$$\epsilon$$n\to\infty$$\epsilon$

Die Wahrscheinlichkeit, dass ein gegebenes Mikrokuboid mit dem ersten Abtastpunkt vollständig fehlt, beträgt , unabhängig von n , da der erste Satz von d Abtastkoordinaten (erster Abtastpunkt) frei gewählt werden kann. Angesichts der Tatsache, dass die ersten Stichprobenpunkte alle dieses Mikrokuboid verfehlt haben, fällt es nachfolgenden Stichprobenpunkten (im Durchschnitt) schwerer, es zu übersehen, sodass die Wahrscheinlichkeit, dass alle n Punkte fehlen, geringer als ( 1 - m - d ) n ist .$1-m^{-d}$$n$$d$$n$$(1-m^{-d})^n$

Es gibt Mikrokuboide in [ 0 , 1 ) d , so dass die erwartete Anzahl, die übersehen wird, oben durch m d ( 1 - m - d ) n begrenzt ist - weil sich die Erwartungen addieren - was im Grenzwert Null als n → ist ∞ .$m^d$$[0,1)^d$$m^d(1-m^{-d})^n$$n\to\infty$

Aktualisierung ...

$\epsilon$$m$$m\times m$ $\epsilon\times\epsilon$$\epsilon\times\epsilon$

$(1/m)^d$$m^{-d}$$1-m^{-d}$$n\to\infty$$m$$1$.

(3) Denken Sie nun über die Anzahl der Stichprobenpunkte nach $n>m$. Ich habe illustriert$n=6m$in dem Bild. LHS arbeitet in einem feinen Netz dieser winzigen Winzlinge$n^{-1}\times n^{-1}$ sized "nanocuboids" (if you will), not the larger $m^{-1}\times m^{-1}$ sized "microcuboids", but actually that's not important in the proof. The proof only needs the slightly hand-waving statement that it gets gradually harder, on average, to keep missing a given microcuboid as you throw down more points. So it was a probability of $1-m^{-d}$ for the first LHS point missing, but less than $(1-m^{-d})^n$ for all $n$ of them missing: that's zero in the limit as $n\to\infty$.

(4) All these epsilons are fine for a proof but aren't great for your intuition. So here are a couple of pictures illustrating $n=10$ and $n=50$ sample points, with the largest empty rectangular area highlighted. (The grid is the LHS sampling grid -- the "nanocuboids" referred to earlier.) It should be "obvious" (in some vague intuitive sense) that the largest empty area will shrink to arbitrarily small size as the number of sample points $n\to\infty$.