Границы хвоста по евклидовой норме для равномерного распределения по

Какие известны верхние оценки того, как часто евклидова норма равномерно выбранного элемента $\:\{-n,~-(n-1),~...,~n-1,~n\}^d\:$ будет больше заданного порога?

В основном меня интересуют границы, которые экспоненциально сходятся к нулю, когда $n$ намного меньше $d$ .

$d$$d$$\epsilon$$\epsilon^{d}$

Я дам полную версию решения кардинала.

$X_i$$-n \leqslant k \leqslant n$$\mathbb{E}[X] = 0$$\text{Var}(X_i) = \frac{n(n+1)}{3}$

Напомним, что и что$\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$

Таким образом,$\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]$вычисление

Пусть$Y_i = X_i^2$

Я закончу это завтра, но вы можете видеть, что эта переменная имеет среднее значение около , в то время как у менее чем доли точек есть расстояния меньше половины максимального расстояния$\frac{n^2}{3}$$2^{-d}$$\frac{dn^2}{2}$

Если все следуют за независимыми дискретными униформами над , то, поскольку есть значений для выбора и их среднее значение равно 0, мы имеем для всех :$X_i$$[-n, n]$$2n+1$$i$

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

Тогда, если является квадратом евклидовой нормы вектора , и из-за независимости :$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}$

С этого момента вы можете использовать неравенство Маркова:$\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}$

Эта граница увеличивается с , что является нормальным, потому что когда становится больше, евклидова норма становится больше по сравнению с фиксированным порогом .$d$$d$$a$

Теперь, если вы определите как «нормализованную» квадратную норму (которая имеет одно и то же ожидаемое значение независимо от того, насколько велика ), вы получите:$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}$

По крайней мере, эта граница не возрастает с , но она все еще далека от решения вашего стремления к экспоненциально убывающей границе! Интересно, может ли это быть из-за слабости неравенства Маркова ...$d$

Я думаю, вы должны уточнить свой вопрос, потому что, как указано выше, средняя евклидова норма ваших векторов линейно возрастает в , поэтому вы вряд ли найдете верхнюю границу для которая уменьшается в с фиксированным порогом .$d$$\mathbb{P}(S > a)$$d$$a$