Batas ekor pada norma Euclidean untuk distribusi seragam pada

Apa yang diketahui batas atas pada seberapa sering norma Euclidean dari elemen yang dipilih secara seragam dari akan lebih besar dari ambang yang diberikan?$\:\{-n,~-(n-1),~...,~n-1,~n\}^d\:$

Saya terutama tertarik pada batas yang konvergen secara eksponensial ke nol ketika jauh lebih kecil dari .$n$$d$

Secara intuitif, harus jelas bahwa titik yang koordinat sampelnya secara acak dari distribusi seragam harus memiliki modulus kecil karena kutukan dimensi. Ketika meningkat, probabilitas bahwa titik sampel secara acak dari volume bola satuan dimensi akan memiliki jarak kurang dari atau sama dengan dari pusat adalah , yang turun secara eksponensial cepat.d ϵ ϵ $d$$d$$\epsilon$$\epsilon^{d}$

Saya akan memberikan versi lengkap dari solusi kardinal.

Biarkan menjadi satu salinan independen dari diskrit, distribusi seragam di atas bilangan bulat . Jelas, , dan mudah dihitung bahwa - n ⩽ k ⩽ n E [ X ] = 0 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}$

Ingat bahwa dan itu 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$

Dengan demikian,$\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]$ perhitungan

Biarkan$Y_i = X_i^2$

Saya akan menyelesaikan ini besok, tetapi Anda dapat melihat bahwa variabel ini memiliki rata-rata sekitar , sementara kurang dari pecahan poin memiliki jarak kurang dari setengah jarak maksimum 2-ddn$\frac{n^2}{3}$$2^{-d}$$\frac{dn^2}{2}$

Jika semua mengikuti seragam diskrit independen di atas , maka karena ada nilai yang dapat dipilih dan rata-ratanya adalah 0, kami memiliki untuk semua : [ - n , n ] 2 n + 1 $X_i$$[-n, n]$$2n+1$$i$

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

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

Maka jika adalah norma vektor , dan karena independensi :( X 1 , X 2 , . . . X d ) X $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}$

Dari sini Anda dapat menggunakan ketidaksetaraan 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}$

Batas ini naik dengan , yang normal karena ketika semakin besar norma euclidean semakin besar jika dibandingkan dengan ambang batas tetap .d $d$$d$$a$

Sekarang jika Anda mendefinisikan sebagai norma kuadrat "dinormalisasi" (yang memiliki nilai harapan yang sama tidak peduli seberapa besar ) Anda dapatkan:$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}$

Setidaknya batas ini tidak naik dengan , tetapi masih jauh dari menyelesaikan pencarian Anda untuk batas yang menurun secara eksponensial! Saya bertanya-tanya apakah ini bisa disebabkan oleh kelemahan ketimpangan Markov ...$d$

Saya pikir Anda harus tepat pertanyaan Anda, karena seperti yang dinyatakan di atas rata-rata norma euclidean vektor Anda naik secara linear dalam , jadi Anda sangat tidak mungkin menemukan batas atas untuk yang menurun dalam dengan ambang batas tetap .P ( S > a ) d $d$$\mathbb{P}(S > a)$$d$$a$