Ogon graniczy z normą euklidesową dla równomiernego rozkładu na

11

Jakie są znane górne granice tego, jak często norma euklidesowa jednolicie wybranego elementu będzie większy niż podany próg?{n, (n1), ..., n1, n}d

Interesują mnie głównie granice, które zbiegają się wykładniczo do zera, gdy jest znacznie mniejsze niż .nd

Ricky Demer
źródło
Łatwo jest odpowiedzieć na progi po prostu obliczasz objętości hipersfer - ale trudniej jest je obliczyć dla . Czy jesteś w jednej z tych sytuacji? tnt>n
whuber
3
Potrzebowałbym. t>n
Ricky Demer
1
W tej chwili nie mam czasu na opublikowanie szczegółowej odpowiedzi, ale w międzyczasie podpowiedź: Porównaj z dwumianową zmienną losową o tej samej średniej wykorzystującej standardową technikę związaną z Chernoffem. To da granicę postaci dla odpowiednich i pod warunkiem, że co ma sens, gdy pomyślisz o tym, co oznacza kwadratowa odległość euklidesowa wynosi. Mam nadzieję, że to pomaga niektórym. a d e - b t 2 a b t > n k(Xk/n)2adebt2abt>nd(n+1)/3n
kardynał

Odpowiedzi:

1

Intuicyjnie powinno być oczywiste, że punkt, którego współrzędne są losowo próbkowane z rozkładu równomiernego, powinien mieć mały moduł z powodu przekleństwa wymiarowości. Jako zwiększa prawdopodobieństwo, że punkt próbki losowo z objętości jednostkę wymiarową piłkę będzie miała odległość mniejszą niż lub równą od środka jest , które gwałtownie spada szybko.d ϵ ϵ dddϵϵd

Dam pełną wersję rozwiązania kardynała.

Niech będzie jedną niezależną kopią dyskretnego, jednolitego rozkładu na liczbach całkowitych . Oczywiście, , i łatwo obliczyć, że - n k n E [ X ] = 0 Var ( X i ) = n ( n + 1 )XinknE[X]=0Var(Xi)=n(n+1)3

Przypomnij sobie, że i że Var ( X 2 i ) = E [ X 4 i ] - E [ X 2 i ] 2E[Xi2]=Var(Xi)+E[Xi]2Var(Xi2)=E[Xi4]E[Xi2]2

ZatemE[Xi2]=Var(Xi)=n(n+1)3

Var(Xi2)=E[Xi4]E[Xi2]2=n(n+1)(3n2+3n+1)15(n(n+1)3)2

E[Xi4]Obliczenie

NiechYi=Xi2

i=1dYi=(Distance of Randomly Sampled Point to Origin)2

Skończę to jutro, ale widać, że ta zmienna ma średnią wartość około , podczas gdy mniej niż część punktów ma odległości mniejsze niż połowa maksymalnej odległości 2-ddn2n232ddn22

Michael K.
źródło
0

Jeśli wszystkie podążają za niezależnymi dyskretnymi mundurami w stosunku do , to ponieważ do wyboru są wartości a ich średnia wynosi 0, mamy dla wszystkich : [ - n , n ] 2 n + 1 iXi[n,n]2n+1i

E(Xi)=0 i

V(Xi)=E((XiE(Xi))2)=E(Xi2)=(2n+1)2112=n(n+1)3

Zatem jeśli jest kwadratową normą euklidesową wektora , a ze względu na niezależność :( X 1 , X 2 , . . . X d ) X iS(X1,X2,...Xd)Xi

S=i=1dXi2

E(S)=i=1dE(Xi2)=dn(n+1)3

Odtąd możesz użyć nierówności Markowa:a>0,P(Sa)1aE(S)

P(Sa)dan(n+1)3

Ta granica wzrasta wraz z , co jest normalne, ponieważ gdy wzrasta , norma euklidesowa staje się większa w porównaniu do ustalonego progu .d adda

Teraz, jeśli zdefiniujesz jako „znormalizowaną” normę do kwadratu (która ma tę samą oczekiwaną wartość, bez względu na to, jak duże ), otrzymasz: dSd

S=1dY=1di=1dXi2

E(S)=n(n+1)3

P(Sa)n(n+1)3a

Przynajmniej ta granica nie rośnie wraz z , ale wciąż daleko jej do rozwiązania poszukiwania wykładniczo malejącej granicy! Zastanawiam się, czy może to być spowodowane słabością nierówności Markowa ...d

Myślę, że powinieneś sprecyzować swoje pytanie, ponieważ, jak wspomniano powyżej, średnia euklidesowa norma twoich wektorów liniowo wzrasta , więc jest bardzo mało prawdopodobne, aby znaleźć górną granicę dla która maleje ze stałym progiem .P ( S > a ) d adP(S>a)da

jubo
źródło