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,~-(n-1),~...,~n-1,~n\}^d\:$

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

uniform extreme-value bounds

— 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?

t \leq n

$t\le n$

t > n

$t \gt n$

— whuber

3

Potrzebowałbym.

t > n

$\: 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.

\sum_{k} (X_{k} / n)^{2}

$\sum_k (X_k/n)^2$

a^{d} e^{- b t^{2}}

$a^d e^{-b t^2}$

a

$a$

b

$b$

t > n \sqrt{d (n + 1) / 3 n}

$t > n \sqrt{d (n+1)/3n}$

— kardynał

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$ $d$ $\epsilon$ $\epsilon^{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 $X_i$ $-n \leqslant k \leqslant n$ $\mathbb{E}[X] = 0$ $\text{Var}(X_i) = \frac{n(n+1)}{3}$

Przypomnij sobie, że i że $\mathbb{E}[X_i^2] = \text{Var}(X_i) + \mathbb{E}[X_i]^2$ $\text{Var}(X_i^2) = \mathbb{E}[X_i^4] - \mathbb{E}[X_i^2]^2$

Zatem $\mathbb{E}[X_i^2] = \text{Var}(X_i) = \frac{n(n+1)}{3}$

$\text{Var}(X_i^2) = \mathbb{E}[X_i^4] - \mathbb{E}[X_i^2]^2 = \frac{n(n+1)(3n^2 + 3n + 1)}{15} - \left( \frac{n(n+1)}{3} \right)^2$

$\mathbb{E}[X_i^4]$ Obliczenie

Niech $Y_i = X_i^2$

\sum_{i = 1}^{d} Y_{i} = (Distance of Randomly Sampled Point to Origin)^{2}

$\sum_{i=1}^d Y_i = (\text{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 $\frac{n^2}{3}$ $2^{-d}$ $\frac{dn^2}{2}$

— 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 : $X_i$ $[-n, n]$ $2n+1$ $i$

$\mathbb{E}(X_i)= 0$ i

$\mathbb{V}(X_i)= \mathbb{E}\left((X_i - \mathbb{E}(X_i))^2\right)= \mathbb{E}(X_i^2)= \frac{(2n+1)^2 - 1}{12}= \frac{n(n+1)}{3}$

Zatem jeśli jest kwadratową normą euklidesową wektora , a ze względu na niezależność : $S$ $(X_1, X_2, ... X_d)$ $X_i$

$S= \sum_{i=1}^d X_i^2$

$\mathbb{E}(S)= \sum_{i=1}^d \mathbb{E}(X_i^2) = d \frac{n(n+1)}{3}$

Odtąd możesz użyć nierówności Markowa: $\forall a >0, \mathbb{P}(S \geq a) \leq \frac{1}{a}\mathbb{E}(S)$

$\mathbb{P}(S \geq a) \leq \frac{d}{a}\frac{n(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$ $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: $S^*$ $d$

$S^*= \frac{1}{d} Y = \frac{1}{d} \sum_{i=1}^d X_i^2$

$\mathbb{E}(S^*) = \frac{n(n+1)}{3}$

$\mathbb{P}(S \geq a) \leq \frac{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 . $d$ $\mathbb{P}(S > a)$ $d$ $a$

— jubo
źródło