Límites de cola de la norma euclidiana para una distribución uniforme en $\{-n,-(n-1),...,n-1,n\}^d$

Question

¿Cuáles son los límites superiores conocidos sobre la frecuencia de la norma euclidiana de un elemento elegido uniformemente elemento de $\:\{-n,~-(n-1),~...,~n-1,~n\}^d\:$ será mayor que un umbral determinado?

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

Answer 1

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

Voy a dar la versión completa de la solución de Cardenal.

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

Recordemos que $\mathbb{E}[X_i^2] = \text{Var}(X_i) + \mathbb{E}[X_i]^2$ y que $\text{Var}(X_i^2) = \mathbb{E}[X_i^4] - \mathbb{E}[X_i^2]^2$

Así, $\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

Dejemos que $Y_i = X_i^2$

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

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

Answer 2

Si todos los $X_i$ siguen uniformes discretos independientes sobre $[-n, n]$ Entonces, como hay $2n+1$ valores a elegir y su media es 0, tenemos para todos $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 $S$ es la norma euclidiana al cuadrado del vector $(X_1, X_2, ... X_d)$ y por la independencia del $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}$

A partir de aquí se puede utilizar 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 $d$ lo cual es normal porque cuando $d$ se hace más grande la norma euclidiana se hace más grande cuando se compara con un umbral fijo $a$ .

Ahora bien, si se define $S^*$ como una norma cuadrada "normalizada" (que tiene el mismo valor esperado sin importar el tamaño $d$ ) se obtiene:

$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 $d$ pero todavía está lejos de resolver su búsqueda de un límite exponencialmente decreciente. Me pregunto si esto puede deberse a la debilidad de la desigualdad de Markov...

Creo que deberías precisar tu pregunta, porque como se ha dicho anteriormente la norma euclidiana media de tus vectores aumenta linealmente en $d$ por lo que es muy poco probable encontrar un límite superior para $\mathbb{P}(S > a)$ que está disminuyendo en $d$ con un umbral fijo $a$ .