Schwanzgrenzen der euklidischen Norm für eine gleichmäßige Verteilung auf

Was sind bekannte Obergrenzen dafür, wie oft die euklidische Norm eines einheitlich gewählten Elements von wird größer als ein gegebener Schwellenwert sein?$\:\{-n,~-(n-1),~...,~n-1,~n\}^d\:$

Ich interessiere mich hauptsächlich für Grenzen, die exponentiell gegen Null konvergieren, wenn viel kleiner als .$n$$d$

Intuitiv sollte es offensichtlich sein, dass ein Punkt, dessen Koordinaten zufällig aus der Gleichverteilung abgetastet werden, aufgrund des Fluches der Dimensionalität einen kleinen Modul haben sollte. Wenn $d$ zunimmt, ist die Wahrscheinlichkeit, dass ein zufällig aus dem Volumen der $d$ dimensionalen Einheitskugel abgetasteter Punkt einen Abstand von weniger als oder gleich $\epsilon$ von der Mitte hat, $\epsilon^{d}$ , der exponentiell schnell abfällt.

Ich werde die Vollversion von Kardinals Lösung geben.

Sei eine unabhängige Kopie einer diskreten, gleichmäßigen Verteilung über die ganzen Zahlen - n ⩽ k ⩽ n . Es ist klar, dass E [ X ] = 0 ist , und es ist leicht zu berechnen, dass Var ( X i ) = n ( n + 1 $X_i$$-n \leqslant k \leqslant n$$\mathbb{E}[X] = 0$$\text{Var}(X_i) = \frac{n(n+1)}{3}$

Man erinnere sich, dass und dass Var ( X 2 i ) = E [ X 4 i ] - E [ X 2 i ] $\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$

Somit ist $\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$

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

Sei $Y_i = X_i^2$

Ich werde das morgen beenden, aber Sie können sehen, dass diese Variable einen Mittelwert von ungefähr , während weniger als2-dBruchteil von Punkten Abstände haben, die weniger als die Hälfte des maximalen Abstandesdn2$\frac{n^2}{3}$$2^{-d}$$\frac{dn^2}{2}$

Wenn alle unabhängig diskrete Uniformen folgen über [ - n , n ] , dann gibt es 2 n + 1 Werte zur Auswahl und deren Mittelwert 0 ist , haben wir für alle i :$X_i$$[-n, n]$$2n+1$$i$

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

$\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}$

Then if $S$ is the squared euclidean norm of vector $(X_1, X_2, ... X_d)$, and because of the independence of the $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}$

$\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}$

This bound rises with $d$, which is normal because when $d$ gets larger the euclidean norm gets larger when compared to a fixed threshold $a$.

Now if you define $S^*$ as a "normalized" squared norm (that has the same expected value no matter how big $d$) you get:

$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}$

At least this bound doesn't rise with $d$, but it still far from solves your quest for an exponentially decreasing bound! I wonder if this can be due to the weakness of the Markov inequality...

I think you should precise your question, because as stated above the mean euclidean norm of your vectors linearly rises in $d$, so you are very unlikely to find an upper bound for $\mathbb{P}(S > a)$ that is decreasing in $d$ with a fixed threshold $a$.