Jakie są znane górne granice tego, jak często norma euklidesowa jednolicie wybranego elementu będzie większy niż podany próg?
Interesują mnie głównie granice, które zbiegają się wykładniczo do zera, gdy jest znacznie mniejsze niż .
uniform
extreme-value
bounds
Ricky Demer
źródło
źródło
Odpowiedzi:
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 ϵ ϵ dd d ϵ ϵ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 )Xi −n⩽k⩽n E[X]=0 Var(Xi)=n(n+1)3
Przypomnij sobie, że i że Var ( X 2 i ) = E [ X 4 i ] - E [ X 2 i ] 2E[X2i]=Var(Xi)+E[Xi]2 Var(X2i)=E[X4i]−E[X2i]2
ZatemE[X2i]=Var(Xi)=n(n+1)3
NiechYi=X2i
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-ddn2n23 2−d dn22
źródło
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+1 i
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
Odtąd możesz użyć nierówności Markowa:∀a>0,P(S≥a)≤1aE(S)
Ta granica wzrasta wraz z , co jest normalne, ponieważ gdy wzrasta , norma euklidesowa staje się większa w porównaniu do ustalonego progu .d ad d a
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: dS∗ d
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 ad P(S>a) d a
źródło