Limites de queue sur la norme euclidienne pour une distribution uniforme sur

11

Quelles sont les limites supérieures connues de la fréquence à laquelle la norme euclidienne d'un élément uniformément choisi de sera supérieur à un seuil donné?{n, (n1), ..., n1, n}d

Je m'intéresse principalement aux bornes qui convergent exponentiellement vers zéro lorsque est bien inférieur à .nd

Ricky Demer
la source
Il est facile de répondre aux seuils calculez simplement les volumes d'hypersphères - mais plus difficile à déterminer pour . Êtes-vous dans l'une ou l'autre de ces situations? t > ntnt>n
whuber
3
J'aurais besoin de. t>n
Ricky Demer
1
Je n'ai pas le temps de poster une réponse détaillée pour le moment, mais voici un indice en attendant: Comparez à une variable aléatoire binomiale avec la même moyenne utilisant la technique liée de Chernoff standard. Cela produira une limite de la forme pour et appropriés à condition que qui ait du sens une fois que vous pensez à ce que signifie la moyenne de la distance euclidienne au carré est. J'espère que cela aide certains. a d e - b t 2 a b t > n k(Xk/n)2adebt2abt>nd(n+1)/3n
cardinal

Réponses:

1

Intuitivement, il devrait être évident qu'un point dont les coordonnées sont échantillonnées au hasard à partir de la distribution uniforme devrait avoir un petit module en raison de la malédiction de la dimensionnalité. Au fur et à mesure que augmente, la probabilité qu'un point échantillonné au hasard dans le volume de la boule des unités dimensionnelles ait une distance inférieure ou égale à rapport au centre est , qui chute exponentiellement rapidement.ddϵϵd

Je vais donner la version complète de la solution du cardinal.

Soit une copie indépendante d'une distribution discrète et uniforme sur les entiers . Clairement, , et il est facile de calculer queXinknE[X]=0Var(Xi)=n(n+1)3

Souvenez-vous que et queE[Xi2]=Var(Xi)+E[Xi]2Var(Xi2)=E[Xi4]E[Xi2]2

Ainsi,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

E[Xi4] calcul

SoitYi=Xi2

i=1dYi=(Distance of Randomly Sampled Point to Origin)2

Je terminerai cela demain, mais vous pouvez voir que cette variable a une moyenne d'environ , tandis que moins de fraction de points ont des distances inférieures à la moitié de la distance maximalen232ddn22

Michael K
la source
0

Si tous les suivent des uniformes discrets indépendants sur , alors comme il y a valeurs à choisir et leur moyenne est 0, nous avons pour tout :Xi[n,n]2n+1i

E(Xi)=0 , et

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

Alors si est la norme euclidienne au carré du vecteur , et à cause de l'indépendance du :S(X1,X2,...Xd)Xi

S=i=1dXi2

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

À partir de là, vous pouvez utiliser l'inégalité de Markov:a>0,P(Sa)1aE(S)

P(Sa)dan(n+1)3

Cette limite augmente avec , ce qui est normal car lorsque devient plus grand, la norme euclidienne devient plus grande par rapport à un seuil fixe .dda

Maintenant, si vous définissez comme une norme au carré "normalisée" (qui a la même valeur attendue, quelle que soit la taille de ), vous obtenez:Sd

S=1dY=1di=1dXi2

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

P(Sa)n(n+1)3a

Au moins, cette limite ne monte pas avec , mais elle est loin de résoudre votre quête d'une limite décroissante exponentiellement! Je me demande si cela peut être dû à la faiblesse de l'inégalité de Markov ...d

Je pense que vous devriez préciser votre question, car comme indiqué ci-dessus, la norme euclidienne moyenne de vos vecteurs augmente linéairement en , il est donc très peu probable que vous trouviez une limite supérieure pour qui diminue en avec un seuil fixe .dP(S>a)da

jubo
la source