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

11

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, (n1), ..., n1, n}d

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

Ricky Demer
quelle
Dies ist leicht zu beantworten für Schwellenwerte tn berechnen nur Volumina von Hypersphären - aber schwieriger für berechnen t>n. Befindest du dich in einer dieser Situationen?
whuber
3
Ich würde brauchen t>n.
Ricky Demer
1
Ich habe momentan keine Zeit, eine detaillierte Antwort zu veröffentlichen, aber hier ist in der Zwischenzeit ein Hinweis: Vergleichen Sie k(Xk/n)2 mit einer binomialen Zufallsvariablen mit demselben Mittelwert unter Verwendung der Standard-Chernoff-gebundenen Technik. Dies ergibt eine Grenze der Form adebt2 für geeignetes a und b vorausgesetzt t>nd(n+1)/3n , was sinnvoll ist, wenn Sie über den Mittelwert der quadratischen euklidischen Entfernung nachdenken. Hoffe das hilft einigen.
Kardinal

Antworten:

1

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 ϵ von der Mitte hat, ϵ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 )XinknE[X]=0Var(Xi)=n(n+1)3

Man erinnere sich, dass und dass Var ( X 2 i ) = E [ X 4 i ] - E [ X 2 i ] 2E[Xi2]=Var(Xi)+E[Xi]2Var(Xi2)=E[Xi4]E[Xi2]2

Somit ist E[Xi2]=Var(Xi)=n(n+1)3

Var(Xi2)=E[Xi4]E[Xi2]2=n(n+1)(3n2+3n+1)15(n(n+1)3)2

BerechnungE[Xi4]

Sei Yi=Xi2

i=1dYi=(Distance of Randomly Sampled Point to Origin)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 Abstandesdn2betragenn232ddn22

Michael K.
quelle
0

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 :Xi[n,n]2n+1i

undE(Xi)=0

V(Xi)=E((XiE(Xi))2)=E(Xi2)=(2n+1)2112=n(n+1)3

Then if S is the squared euclidean norm of vector (X1,X2,...Xd), and because of the independence of the Xi:

S=i=1dXi2

E(S)=i=1dE(Xi2)=dn(n+1)3

a>0,P(Sa)1aE(S)

P(Sa)dan(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=1dY=1di=1dXi2

E(S)=n(n+1)3

P(Sa)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 P(S>a) that is decreasing in d with a fixed threshold a.

jubo
quelle