Asymptotyka łacińskiego Hypercube

11

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.

kjetil b halvorsen
źródło
4
Tak, przy założeniu ciągłego rozkładu, ponieważ dla każdego ϵ>0 możesz ustawić liczbę podziałów, aby wszystkie przedziały dla każdej zmiennej miały szerokość <ϵ/2 . Tak więc co najmniej jeden hiperinterwał (tj. Objętość próbki) jest ściśle zawarty w hiperszerze szerokości ϵ wokół dowolnego wybranego punktu. (Komentarz, nie odpowiedź, ponieważ wszystko, co wiem o LHS, pochodzi z Wikipedii sprzed dziesięciu minut ...)
Creosote
To prawda, ale nie sądzę, że można go łatwo wykorzystać do pokazania gęstości dużych próbek Latin Hypercube. Powodem tego jest to, że punkty próbkowane w LHS nie są niezależne: istnienie punktu próbkowego w określonym hiperinterval uniemożliwia pojawienie się innych punktów próbnych w tym samym rzędzie / kolumnie (lub niezależnie od tego, jaki jest dla tego termin wielowymiarowy) .
S. Catterall przywraca Monikę
@ Creosote, czy uważasz, że możesz bardziej sformalizować swoją odpowiedź?
@RustyStatistician, proszę rozwinąć swój post otwierający, aby wyjaśnić, w sposób formalny, jak wymaga tego dowód, co rozumiesz przez „zestaw punktów, z których próbuję, jest gęsty na całej przestrzeni”. Dzięki.
Creosote
Jeśli wezmę początkową próbkę Latin Hypercube, w której jest tak duża, uważamy ją za niedoskonałą, czy ta próbka jest gęsta? n

Odpowiedzi:

6

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 , , mϵ>0{x1,,xm}δ>0ϵxi>1δ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 , . . .nn11,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 , .1,2,3,...[0,1)2nn n ε > 0Xn=(Xn1,Xn2,...,Xnn)nnϵ>0[ 0 , 1 ) d P ( m i n 1 k nXx w przestrzeni próbki (przyjmowanej jako ) mamy ( jako ).[0,1)dnP(min1knXnkxϵ)0n

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 nX n kXnnU([0,1)d)v ϵ d ϵ

P(min1knXnkxϵ)=k=1nP(Xnkxϵ)(1vϵ2d)n0
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 nXnXnU([0,1)d)Xnk,kn

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 nX n k - x ϵ )ϵ>0x[0,1)dPn=P(min1knXnkxϵ)f : [ 0 , 1 ] dR f ( z ) = 1 z ϵ x f ( z )Pn0f:[0,1]dRf(z)=1zϵxY n : = f(z)=0μ = [ 0 , 1 ], d FYn:=n(μ^LHSμ)dN(0,Σ)μ L H S = 1μ=[0,1]df(z)dzμ^LHS=1ni=1nf(Xni) .

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>0nPn=P(Yn=-nμ<Llim sup P nlim sup P ( Y n < - L ) = Φ ( - LPn=P(Yn=nμ)P(Yn<L)ΦLPn0lim supPnlim supP(Yn<L)=Φ(LΣ)ΦLPn0

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 , . . .ϵxϵxϵ>0m i n 1 j m P ( m i n 1 k nX n k - x j< ϵ ) 1 n {x1,...,xm}min1jmP(min1knXnkxj<ϵ)1 (jako ).n

S. Catterall Przywróć Monikę
źródło
Mam dwa pytania: 1) Jeśli masz tylko próbkę o rozmiarze gdzie jest duże, czy to zmienia argument? I 2) próbki łacińskich hipersześcianów mogą mieć dowolny zakres wartości (niekoniecznie tylko (0,1)), więc czy to również zmienia odpowiedź? nnn
Czy zechciałbyś też wyjaśnić, dlaczego dla wystarczająco dużej liczby będziemy mieć ? Zakładamy, że oznacza to, że dla dużych , dojdzie do zera, ponieważ w dystrybucji to ? - nn μ L H S N(nμnμ^LHSN(0,Σ)
@RustyStatistician Wszystko jest zdefiniowane w kategoriach skończonych próbek, tj. ale duże. Na końcu dodałem dodatkowe wyjaśnienie, aby wyjaśnić, co się dzieje. Inne zakresy wartości można łatwo dostosować ((0,1) nie jest specjalne), o ile objętość przestrzeni próbki jest skończona. n<
S. Catterall przywraca Monikę
Czy potrafisz rozwinąć swoją krótką odpowiedź?
@RustyStatistician Krótka odpowiedź jest nieformalnym streszczeniem mojej długiej odpowiedzi, która, jak sądzę, zgodzi się, jest już dość skomplikowana! Tak więc, jak zasugerowano powyżej, dobrze byłoby, gdybyś mógł przepisać swoje pytanie w bardziej formalny sposób, aby wiedzieć, czy moja próba odpowiedzi jest właściwa (pod względem odpowiedzi na zamierzone pytanie), czy nie.
S. Catterall przywraca Monikę
3

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 ϵ>0ϵn

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=2/ϵm d 1[0,1)dmdϵ n ϵ1/mϵnϵ

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 d1mdnd( 1 - m - d ) nn(1md)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 .mdm d ( 1[0,1)d n md(1md)nn


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 ×ϵmϵ × ϵ ϵ × ϵm×m ϵ×ϵϵ×ϵ

wprowadź opis zdjęcia tutaj

(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 - m(1/m)dmd nm11mdnm1

(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>mn=6mn1×n1m1×m11md(1md)n nn .

(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=10n=50n

wprowadź opis zdjęcia tutaj

Kreozot
źródło
Czy ten argument dotyczy jakiegoś ogólnego okresu? Zamiast ? [0,1)
Tak, dla dowolnych skończonych wymiarów. Teraz powinienem być jaśniejszy, kiedy naprawiłem dowód.
Creosote,
czy można dać 1-d, a nawet 2-d obraz tego dowodu? Jestem w tym bardzo zagubiony.
Gotowe. W razie potrzeby chętnie odpowiemy na dalsze pytania.
Creosote
Wielkie dzieki! To zdecydowanie pomaga teraz w intuicji.