Quais são os limites superiores conhecidos de quantas vezes a norma euclidiana de um elemento uniformemente escolhido de será maior que um determinado limite?
Estou interessado principalmente em limites que convergem exponencialmente em zero quando é muito menor que .
uniform
extreme-value
bounds
Ricky Demer
fonte
fonte
Respostas:
Intuitivamente, deve ser óbvio que um ponto cujas coordenadas são amostradas aleatoriamente a partir da distribuição uniforme deve ter um pequeno módulo devido à maldição da dimensionalidade. À medida que aumenta, a probabilidade de um ponto amostrado aleatoriamente a partir do volume da bola unitária dimensional ter distância menor ou igual a do centro é , que cai exponencialmente rapidamente.d £ £ dd d ϵ ϵd
Vou dar a versão completa da solução do cardeal.
Seja uma cópia independente de uma distribuição discreta e uniforme sobre os números inteiros . Claramente, , e é facilmente calculado queXi −n⩽k⩽n E[X]=0 Var(Xi)=n(n+1)3
Lembre-se de que e queE[X2i]=Var(Xi)+E[Xi]2 Var(X2i)=E[X4i]−E[X2i]2
Assim,E[X2i]=Var(Xi)=n(n+1)3
SejaYi=X2i
Terminarei isso amanhã, mas você pode ver que essa variável tem uma média de cerca de , enquanto menos de fração de pontos tem distâncias inferiores a metade da distância máximan23 2−d dn22
fonte
Se todos os seguem uniformes discretos independentes sobre , então como existem valores para escolher e sua média é 0, temos para todos :Xi [−n,n] 2n+1 i
Então, se é a norma euclidiana quadrada do vetor e por causa da independência do :S (X1,X2,...Xd) Xi
A partir daqui, você pode usar a desigualdade de Markov:∀a>0,P(S≥a)≤1aE(S)
Esse limite aumenta com , o que é normal porque quando aumenta, a norma euclidiana aumenta quando comparada a um limite fixo .d d a
Agora, se você definir como uma norma quadrada "normalizada" (que tem o mesmo valor esperado, independentemente do tamanho ), você obtém:S∗ d
Pelo menos esse limite não aumenta com , mas ainda está longe de resolver sua busca por um limite decrescente exponencialmente! Gostaria de saber se isso pode ser devido à fraqueza da desigualdade de Markov ...d
Eu acho que você deveria precisar sua pergunta, porque, como afirmado acima, a norma euclidiana média de seus vetores aumenta linearmente em , então é muito improvável que você encontre um limite superior para que está diminuindo em com um limite fixo .d P(S>a) d a
fonte