Límites de cola en la norma euclidiana para una distribución uniforme en

Lo que se conoce como límites superiores con qué frecuencia la norma euclidiana de un elemento uniformemente elegido de será mayor que un umbral dado?$\:\{-n,~-(n-1),~...,~n-1,~n\}^d\:$

Me interesan principalmente los límites que convergen exponencialmente a cero cuando es mucho menor que .$n$$d$

Intuitivamente, debería ser obvio que un punto cuyas coordenadas se muestrean al azar de la distribución uniforme debe tener un módulo pequeño debido a la maldición de la dimensionalidad. A medida que aumenta, la probabilidad de que un punto muestreado al azar del volumen de la bola de la unidad dimensional tenga una distancia menor o igual a desde el centro es , que cae exponencialmente rápido.d ϵ ϵ $d$$d$$\epsilon$$\epsilon^{d}$

Daré la versión completa de la solución de Cardinal.

Sea una copia independiente de una distribución discreta y uniforme sobre los enteros . Claramente, , y se calcula fácilmente que$X_i$$-n \leqslant k \leqslant n$$\mathbb{E}[X] = 0$$\text{Var}(X_i) = \frac{n(n+1)}{3}$

Recuerde que y que$\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$

Por lo tanto,$\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]$ cálculo

Deje$Y_i = X_i^2$

Terminaré esto mañana, pero puedes ver que esta variable tiene una media de aproximadamente , mientras que menos de fracción de puntos tiene distancias menos de la mitad de la distancia máxima$\frac{n^2}{3}$$2^{-d}$$\frac{dn^2}{2}$

Si todas las siguen uniformes discretos independientes sobre , entonces como hay para elegir y su media es 0, tenemos para todo :$X_i$$[-n, n]$$2n+1$$i$

$\mathbb{E}(X_i)= 0$ , y

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

Entonces, si es la norma euclidiana al cuadrado del vector , y debido a la independencia de :$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}$

De aquí en adelante, podría usar la desigualdad de Markov:$\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}$

Este límite aumenta con , lo cual es normal porque cuando hace más grande, la norma euclidiana se hace más grande en comparación con un umbral fijo .$d$$d$$a$

Ahora, si define como una norma al cuadrado "normalizada" (que tiene el mismo valor esperado, no importa cuán grande ) obtenga:$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}$

¡Al menos este límite no aumenta con , pero aún está lejos de resolver su búsqueda de un límite decreciente exponencialmente! Me pregunto si esto puede deberse a la debilidad de la desigualdad de Markov ...$d$

Creo que debe precisar su pregunta, porque como se indicó anteriormente, la norma euclidiana media de sus vectores aumenta linealmente en , por lo que es muy poco probable que encuentre un límite superior para que esté disminuyendo en con un umbral fijo .$d$$\mathbb{P}(S > a)$$d$$a$