Asymptotyka łacińskiego Hypercube

Próbuję skonstruować dowód na problem, nad którym pracuję, a jednym z założeń, które robię, jest to, że zbiór punktów, z których próbuję, jest gęsty na całej przestrzeni. Praktycznie używam łacińskiego próbkowania hipersześcianu, aby uzyskać punkty w całej przestrzeni próbki. Chciałbym wiedzieć, czy próbki łacińskiej hipersześcianu są gęste na całej przestrzeni, jeśli pozwalasz, by wielkość twojej próbki była ? Jeśli tak, to należy docenić wzmiankę o tym fakcie.$\infty$

Krótka odpowiedź: tak, w sposób probabilistyczny. Możliwe jest wykazanie, że przy dowolnej odległości , dowolnym skończonym podzbiorze przestrzeni próbki i każdej określonej „tolerancji” , dla odpowiednio dużych próbek możemy być się, że prawdopodobieństwo, że istnieje punkt próbki w odległości z jest dla wszystkich .{ x 1 , … , x m } δ > 0 ϵ x i > 1 - δ i = 1 , … , $\epsilon>0$$\{x_1,…,x_m\}$$\delta>0$$\epsilon$$x_i$$>1-\delta$$i=1,…,m$

Długa odpowiedź: nie znam żadnego bezpośrednio związanego cytatu (ale patrz poniżej). Większość literatury na temat próbkowania Latin Hypercube (LHS) dotyczy jej właściwości zmniejszania wariancji. Innym problemem jest to, co oznacza powiedzieć, że wielkość próby ma tendencję do ? W przypadku prostego losowego próbkowania IID próbkę o wielkości można uzyskać z próbki o wielkości , dołączając kolejną niezależną próbkę. W przypadku LHS nie sądzę, abyś mógł to zrobić, ponieważ liczba próbek jest z góry określona w ramach procedury. Wygląda więc na to, że trzeba by wziąć kolejnych niezależnych próbek LHS wielkości .n n - 1 1 , 2 , 3 , . . $\infty$$n$$n-1$$1,2,3,...$

Musi również istnieć jakiś sposób interpretacji „gęstej” granicy, ponieważ wielkość próby ma tendencję do . Gęstość nie wydaje się utrzymywać w sposób deterministyczny dla LHS, np. W dwóch wymiarach, można wybrać sekwencję próbek LHS o wielkości tak, aby wszystkie trzymały się przekątnej . Konieczna wydaje się więc pewna definicja probabilistyczna. Pozwolić, dla każdego , jest próbka o wymiarach generowane według pewnej stochastycznego mechanizmu. Załóżmy, że dla różnych próbki te są niezależne. Następnie, aby zdefiniować asymptotyczną gęstość, możemy tego wymagać dla każdego i dla każdego1 , 2 , 3 , . . . [ 0 , 1 ), 2 N X N = ( X n 1 , X n 2 , $\infty$$1,2,3,...$$[0,1)^2$$n$n n ε > $X_n=(X_{n1},X_{n2},...,X_{nn})$$n$$n$$\epsilon>0$[ 0 , 1 ) d P ( m i n 1 ≤ k ≤ n ‖ $x$ w przestrzeni próbki (przyjmowanej jako ) mamy ( jako ).$[0,1)^d$n→$P(min_{1\leq k\leq n} \|X_{nk}-x\|\geq \epsilon)\to0$$n\to \infty$

Jeżeli próbka jest otrzymana przez pobranie niezależnych próbek z rozkładu („losowe próbkowanie IID”), to gdzie jest objętością wymiarowej kuli o promieniu . Tak więc z pewnością losowe próbkowanie IID jest asymptotycznie gęste. n U ( [ 0 , 1 ) d ) P ( m i n 1 ≤ k ≤ n ‖ X n $X_n$$n$$U([0,1)^d)$v ϵ d

Rozważmy teraz przypadek, w którym próbki są uzyskiwane przez LHS. Twierdzenie 10.1 w tych uwagach stwierdza, że ​​wszystkie elementy próbki są rozłożone jako . Jednak permutacje zastosowane w definicji LHS (choć niezależne dla różnych wymiarów) indukują pewną zależność między członami próbki ( ), więc mniej oczywiste jest, że właściwość gęstości asymptotycznej utrzymuje się.X n U ( [ 0 , 1 ) d ) X n k , k ≤ $X_n$$X_n$$U([0,1)^d)$$X_{nk}, k\leq n$

Napraw i . Zdefiniuj . Chcemy pokazać, że . Aby to zrobić, możemy skorzystać z Propozycji 10.3 w tych notatkach , która jest rodzajem Twierdzenia o granicy centralnej dla próbkowania Latin Hypercube. Zdefiniuj przez jeżeli jest w kuli o promieniu wokół , przeciwnym razie Następnie Propozycja 10.3 mówi nam, że gdzie ix ∈ [ 0 , 1 ) d P n = P ( m i n 1 ≤ k ≤ n ‖ X n k - x ‖ ≥ ϵ $\epsilon\gt 0$$x\in [0,1)^d$$P_n=P(min_{1\leq k\leq n} \|X_{nk}-x\|\geq \epsilon)$f : [ 0 , 1 ] d → R f ( z ) = 1 z ϵ x f ( z $P_n\to 0$$f:[0,1]^d\to\mathbb{R}$$f(z)=1$$z$$\epsilon$$x$Y n : = $f(z)=0$μ = ∫ [ 0 , 1 ], d$Y_n:=\sqrt n (\hat{\mu}_{LHS}-\mu)\xrightarrow{d} N(0,\Sigma)$μ L H S = $\mu=\int_{[0,1]^d} f(z) dz$$\hat{\mu}_{LHS}=\frac{1}{n}\sum_{i=1}^n f(X_{ni})$ .

Weź . W końcu, dla wystarczająco dużego , będziemy mieli . Więc w końcu będziemy mieli . Dlatego , gdzie jest standardowym normalnym cdf. Ponieważ był arbitralny, wynika z tego, że zgodnie z wymaganiami.n - $L>0$$n$Pn=P(Yn=-$-\sqrt n\mu\lt -L$lim sup P n ≤ lim sup P ( Y n < - L ) = Φ ( - $P_n=P(Y_n=-\sqrt n \mu)\le P(Y_n\lt -L)$ΦLPn→$\limsup P_n\le \limsup P(Y_n\lt -L)=\Phi(\frac{-L}{\sqrt\Sigma})$$\Phi$$L$$P_n\to 0$

Dowodzi to asymptotycznej gęstości (jak zdefiniowano powyżej) zarówno dla losowego próbkowania iid, jak i LHS. Nieformalnie, oznacza to, że podane żadnego i wszelkie w przestrzeni próbkowania, prawdopodobieństwo, że próbka trafia do wewnątrz z może być wykonana jako zbliżona do 1, jak należy, wybierając wielkość próbki dostatecznie duża. Łatwo jest rozszerzyć pojęcie gęstości asymptotycznej, aby zastosować ją do skończonych podzbiorów przestrzeni próbki - poprzez zastosowanie tego, co już wiemy, do każdego punktu w skończonym podzbiorze. Bardziej formalnie oznacza to, że możemy pokazać: dla dowolnego i dowolnego skończonego podzbioru przestrzeni próbki,x ε x ε > 0 { x 1 , . . $\epsilon$$x$$\epsilon$$x$$\epsilon>0$m i n 1 ≤ j ≤ m P ( m i n 1 ≤ k ≤ n ‖ X n k - x j ‖ < ϵ ) → 1 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$ (jako ).$n\to\infty$

Nie jestem pewien, czy tego właśnie chcesz, ale proszę bardzo.

Powiedzmy, że próbujesz LHS punktów od . Będziemy bardzo nieformalnie argumentować, że dla każdego oczekiwana liczba pustych (hiper) prostopadłościanów o rozmiarze w każdym wymiarze spada do zera jako .[ 0 , 1 $n$$[0,1)^d$ϵ n → $\epsilon>0$$\epsilon$$n\to\infty$

Niech , aby jeśli podzielimy równomiernie na maleńkie prostopadłościany - powiedzmy mikrokuboidy - o szerokości wówczas każda prostopadłościan- zawiera co najmniej jeden mikrokuboid. Jeśli więc możemy wykazać, że oczekiwana liczba niespróbkowanych mikrokuboidów wynosi zero, w granicach od , to skończymy. (Zauważ, że nasze mikrokuboidy są ułożone na regularnej siatce, ale kuboidy mogą znajdować się w dowolnej pozycji).$m=\lceil 2/\epsilon \rceil$m d$[0,1)^d$$m^d$ϵ n → ∞ $1/m$$\epsilon$$n\to\infty$$\epsilon$

Szansa całkowitego pominięcia danego mikrokuboidu w pierwszym punkcie próbki wynosi , niezależnie od , ponieważ pierwszy zestaw współrzędnych próbki (pierwszy punkt próbki) można dowolnie wybierać. Biorąc pod uwagę, że w pierwszych kilku punktach próbkowania wszystkie pominęły ten mikrokuboid, kolejne punkty próbne będą trudniejsze do pominięcia (średnio), więc szansa na brak wszystkich punktów jest mniejsza niż . n $1-m^{-d}$$n$$d$( 1 - m - d ) $n$$(1-m^{-d})^n$

W jest mikrokuboidów , więc oczekiwana liczba, która jest pominięta, jest ograniczona przez - ponieważ dodają oczekiwania - co jest zero w limicie jako .$m^d$m d ( $[0,1)^d$ n → $m^d(1-m^{-d})^n$$n\to\infty$

Aktualizacje ...

(1) Oto zdjęcie pokazujące, jak dla danego można wybrać wystarczająco duże, aby zagwarantować, że siatka „mikrokuboidów” (kwadraty na tej dwuwymiarowej ilustracji) ma co najmniej jeden mikrokuboid w obrębie dowolny region wielkości . Pokazałem dwa „losowo” wybrane regiony i wybarwiłem na fioletowo dwa mikrokuboidy, które zawierają.m m $\epsilon$$m$ϵ × ϵ ϵ × $m\times m$ $\epsilon\times\epsilon$$\epsilon\times\epsilon$

(2) Weź pod uwagę każdy konkretny mikrokuboid. Ma objętość , ułamek całej przestrzeni. Tak więc pierwsza próbka LHS - która jest jedyną wybraną całkowicie swobodnie - będzie tęsknić z prawdopodobieństwem . Jedynym ważnym faktem jest to, że jest to stała wartość (pozwolimy , ale utrzymamy stałą), która jest mniejsza niż .m - d 1 - $(1/m)^d$$m^{-d}$ n→∞m$1-m^{-d}$$n\to\infty$$m$$1$

(3) Pomyśl teraz o liczbie punktów próbnych . Zilustrowałem na zdjęciu . LHS działa w drobnej siatce tych super-małych „nanokuboidów” (jeśli wolisz), a nie większych wielkości „mikrokuboidów”, ale tak naprawdę nie jest to ważne w dowodzie. Dowód potrzebuje jedynie lekko machającego ręką stwierdzenia, że ​​stopniowo staje się ono coraz trudniejsze, aby nadal tracić dany mikrokuboid, gdy rzucasz więcej punktów. Było więc prawdopodobieństwo dla pierwszego brakującego punktu LHS, ale mniej niż dla wszystkich brakujących : to zero w limicie, ponieważn = 6 m n - 1 × n - 1 m - 1 × m - 1 1 - m - d ( 1 - m - d ) n n n → $n>m$$n=6m$$n^{-1}\times n^{-1}$$m^{-1}\times m^{-1}$$1-m^{-d}$$(1-m^{-d})^n$ $n$$n\to\infty$ .

(4) Wszystkie te epsilony nadają się na dowód, ale nie są świetne dla twojej intuicji. Oto kilka zdjęć ilustrujących i punktów próbki, z zaznaczonym największym pustym prostokątnym obszarem. (Siatka jest siatką próbkowania LHS - „nanokuboidy”, o których mowa wcześniej.) Powinno być „oczywiste” (w pewnym niejasnym intuicyjnym sensie), że największy pusty obszar zmniejszy się do arbitralnie małego rozmiaru jako liczba punktów próbki .n = 50 n → $n=10$$n=50$$n\to\infty$