Distribuição de produtos escalares de dois vetores unitários aleatórios em dimensões

Se e são dois vetores de unidades aleatórias independentes em (distribuídos uniformemente em uma esfera de unidades), qual é a distribuição do produto escalar (produto escalar) ? $\mathbf{x}$ $\mathbf{y}$ $\mathbb{R}^D$ $\mathbf x \cdot \mathbf y$

Eu acho que conforme cresce a distribuição rapidamente (?) Se torna normal com média zero e variância diminuindo em dimensões mais altas mas existe uma fórmula explícita para ? $D$

lim_{D \to \infty} σ^{2} (D) \to 0,

$\lim_{D\to\infty}\sigma^2(D) \to 0,$

σ^{2} (D)

$\sigma^2(D)$

Atualizar

Fiz algumas simulações rápidas. Primeiro, gerando 10000 pares de vetores de unidades aleatórias para $D=1000$ , é fácil ver que a distribuição de seus produtos pontuais é perfeitamente gaussiana (na verdade, já é bastante gaussiana para $D=100$ ), veja a subtrama à esquerda. Segundo, para cada $D$ variando de 1 a 10000 (com etapas crescentes), gerei 1000 pares e calculei a variação. Gráfico log-log é mostrado à direita, e é claro que a fórmula é muito bem aproximada por $1/D$ . Observe que, para $D=1$ e $D=2$ esta fórmula fornece resultados exatos (mas não sei ao certo o que acontece depois).

produtos pontuais entre vetores unitários aleatórios

mathematical-statistics linear-algebra beta-distribution ameba diz Restabelecer Monica
fonte

@KarlOskar: obrigado, este link é muito relevante e, de fato, torna minha pergunta quase duplicada, mas não totalmente. Portanto, existe uma fórmula explícita para que é uma função de distribuição cumulativa dos produtos pontuais. Pode-se usar um derivado para obter o PDF e depois estudar o limite de . No entanto, a fórmula é dada em termos de funções beta e funções beta incompletas, portanto os cálculos provavelmente serão desagradáveis.

P {(x, y) > ϵ}

$P\{(\mathbf{x}, \mathbf{y})>\epsilon\}$

D \to \infty

$D\to \infty$

Ameba diz Reinstate Monica

@KarlOskar: a partir da distribuição uniforme sobre uma esfera unidade em . Para gerar um vetor aleatório a partir dessa distribuição, pode-se gerar um vetor aleatório a partir de um Gaussiano com uma variação de unidade e normalizá-lo.

R^{D}

$\mathbb{R}^D$

Ameba diz Reinstate Monica

Respostas:

Como ( como é sabido ) uma distribuição uniforme na esfera unitária é obtida normalizando uma distribuição normal variável e o produto escalar de vetores normalizados é seu coeficiente de correlação, as respostas para as três perguntas são: $S^{D-1}$ $D$ $t$

$u= (t+1)/2$ tem uma distribuição Beta . $((D-1)/2,(D-1)/2)$
A variação de é igual a (conforme especulado na pergunta). $t$ $1/D$
A distribuição padronizada de aproxima da normalidade a uma taxa de $t$ $O\left(\frac{1}{D}\right).$

Método

A distribuição exata do produto escalar dos vetores unitários é facilmente obtida geometricamente, porque esse é o componente do segundo vetor na direção do primeiro. Como o segundo vetor é independente do primeiro e é uniformemente distribuído na esfera unitária, seu componente na primeira direção é distribuído da mesma forma que qualquer coordenada da esfera. (Observe que a distribuição do primeiro vetor não importa.)

Encontrando a densidade

Deixando que a coordenada seja a última, a densidade em é, portanto, proporcional à área da superfície situada a uma altura entre e na esfera unitária. Essa proporção ocorre dentro de uma faixa de altura e raio que é essencialmente um tronco cônico construído a partir de um de raio de altura e inclinação . De onde a probabilidade é proporcional a $t \in [-1,1]$ $t$ $t+dt$ $dt$ $\sqrt{1-t^2},$ $S^{D-2}$ $\sqrt{1-t^2},$ $dt$ $1/\sqrt{1-t^2}$

\frac{{(\sqrt{1 - t^{2}})}^{D - 2}}{\sqrt{1 - t^{2}}} d t = (1 - t^{2})^{(D - 3) / 2} d t .

$\frac{\left(\sqrt{1 - t^2}\right)^{D-2}}{\sqrt{1 - t^2}}\,dt = (1 - t^2)^{(D-3)/2} dt.$

Deixar implica . Substituindo isso no precedente, o elemento de probabilidade é convertido em uma constante de normalização: $u=(t+1)/2 \in [0,1]$ $t = 2u-1$

f_{D} (u) d u \propto (1 - (2 u - 1)^{2})^{(D - 3) / 2} d (2 u - 1) = 2^{D - 2} (u - u^{2})^{(D - 3) / 2} d u .

$f_D(u)du \; \propto \; (1 - (2u-1)^2)^{(D-3)/2} d(2u-1) = 2^{D-2}(u-u^2)^{(D-3)/2}du.$

É imediato que tenha uma distribuição Beta , porque (por definição) sua densidade também é proporcional a $u=(t+1)/2$ $((D-1)/2, (D-1)/2)$

u^{(D - 1) / 2 - 1} {(1 - u)}^{(D - 1) / 2 - 1} = (u - u^{2})^{(D - 3) / 2} \propto f_{D} (u) .

$u^{(D-1)/2-1}\left(1-u\right)^{(D-1)/2-1} = (u-u^2)^{(D-3)/2} \; \propto \; f_D(u).$

Determinando o comportamento limitante

As informações sobre o comportamento limitador seguem facilmente isso usando técnicas elementares: pode ser integrado para obter a constante de proporcionalidade ; pode ser integrado (usando propriedades das funções Beta, por exemplo) para obter momentos, mostrando que a variação é e diminui para (daí, pelo Teorema de Chebyshev, a probabilidade está se concentrando perto de ); ea distribuição limitadora é então encontrada considerando valores da densidade da distribuição padronizada, proporcional a para valores pequenos de $f_D$ $\frac{\Gamma \left(\frac{n}{2}\right)}{\sqrt{\pi } \Gamma \left(\frac{D-1}{2}\right)}$ $t^k f_D(t)$ $1/D$ $0$ $t=0$ $f_D(t/\sqrt{D}),$ $t$ :

\begin{aligned} \log (f_{D} (t / \sqrt{D})) & = C (D) + \frac{D - 3}{2} \log (1 - \frac{t^{2}}{D}) \\ = C (D) - (1 / 2 + \frac{3}{2 D}) t^{2} + O (\frac{t^{4}}{D}) \\ \to C - \frac{1}{2} t^{2} \end{aligned}

$\eqalign{ \log(f_D(t/\sqrt{D})) &= C(D) + \frac{D-3}{2}\log\left(1 - \frac{t^2}{D}\right) \\ &=C(D) -\left(1/2 + \frac{3}{2D}\right)t^2 + O\left(\frac{t^4}{D}\right) \\ &\to C -\frac{1}{2}t^2 }$

onde os representam constantes (log) de integração. Evidentemente, a taxa na qual isso se aproxima da normalidade (para a qual a densidade do log é igual a ) é $C$ $-\frac{1}{2}t^2$ $O\left(\frac{1}{D}\right).$

Figura

Este gráfico mostra as densidades do produto escalar para , conforme padronizado para a variação unitária, e sua densidade limitante. Os valores em aumentam com (de azul a vermelho, dourado e depois verde para a densidade normal padrão). A densidade para seria indistinguível da densidade normal nesta resolução. $D=4, 6, 10$ $0$ $D$ $D=1000$

whuber
fonte

(+1) Muito obrigado, @whuber, esta é uma ótima resposta! Agradecimentos especiais por mencionar a palavra "frustum". Acontece que aceitei outra resposta apenas alguns minutos antes de você postar a sua e não gostaria de aceitá-la agora; espero que você entenda. Pena que não é possível aceitar os dois! A propósito, observe uma prova muito simples da expressão de variação dessa resposta: é possível vê-la diretamente sem mexer nas funções beta! A variação do produto escalar é igual à variação de qualquer coordenada de esfera (como você escreveu), e uma soma de todos os deles deve ser , QED

1 / D

$1/D$

D

$D$

1

$1$

ameba diz Reinstate Monica

Essa é uma boa observação sobre as variações.

whuber

@amoeba, a atividade recente também chamou minha atenção aqui novamente e, por mais que eu aprecie que você tenha aceitado minha resposta, essa é muito mais completa. Eu não me importaria se você mudasse.

Ekvall

@ Student001: este é um comentário justo e generoso. Troquei a resposta aceita. Eu também encontrei um Q e um A para votar de forma a compensar isso :)

ameba diz Reinstate Monica

@mat A distribuição de é a de . Isso o torna uma distribuição Beta que foi dimensionada e alterada do intervalo para o intervalo .

t

$t$

2 U - 1

$2U-1$

[0, 1]

$[0,1]$

[- 1, 1]

$[-1,1]$

whuber

Vamos encontrar a distribuição e a variação segue pelos resultados padrão. Considere o produto vetorial e escreva em sua forma cosseno, ou seja, observe que temos onde é o ângulo entre e . Na última etapa, usei isso para quaisquer eventos eAgora considere o termo . É claro que, como é escolhido uniformemente em relação à superfície da esfera, não importa o que

P (x^{'} y \leq t) = P (| x | | y | \cos θ \leq t) = P (\cos θ \leq t) = E P (\cos θ \leq t ∣ y),

$P(x'y\leq t)=P(|x||y|\cos\theta\leq t)=P(\cos\theta\leq t)=\mathbb{E}P(\cos\theta\leq t\mid y),$

θ

$\theta$

x

$x$

y

$y$

A

$A$

B

$B$

E P (A ∣ B) := E [E [χ_{A} ∣ B]] = E χ_{A} = P (A) .

$\mathbb EP(A\mid B):=\mathbb{E}[\mathbb{E}[\chi_A\mid B]]=\mathbb{E}\chi_A=P(A).$

P (\cos θ \leq t ∣ y)

$P(\cos\theta\leq t\mid y)$

x

$x$

y

$y$ na verdade, apenas o ângulo entre e importante. Assim, o termo dentro da expectativa é realmente constante em função de e podemos assumir queEntão obtemos quemas como é a primeira coordenada de um vetor gaussiano normalizado em temos que é gaussiano com variação invocando o resultado assintótico deste artigo .

x

$x$

y

$y$

y

$y$

y = [1, 0, 0, \dots]^{'} .

$y=[1,0,0,\dots ]'.$

P (x^{'} y \leq t) = P (x_{1} \leq t) .

$P(x'y\leq t)=P\left( x_1\leq t\right).$

x_{1}

$x_1$

R^{n},

$\mathbb{R}^n,$

x^{'} y

$x'y$

1 / n

$1/n$

Para um resultado explícito da variação, use o fato de que o produto escalar é zero com independência e, como mostrado acima, distribuído como a primeira coordenada de . Por esses resultados, encontrar equivale a encontrar . Agora, observe que, por construção , podemos escrever onde a última igualdade segue a partir da qual as coordenadas de são identicamente distribuídas. Juntando as coisas, descobrimos que $x$ $\text{Var}(x'y)$ $\mathbb{E}x_1^2$ $x'x=1$

1 = E x^{'} x = E \sum_{i = 1}^{n} x_{i}^{2} = \sum_{i = 1}^{n} E x_{i}^{2} = n E x_{1}^{2},

$1=\mathbb{E}x'x=\mathbb{E}\sum_{i=1}^nx_i^2=\sum_{i=1}^n\mathbb{E}x_i^2=n\mathbb{E}x_1^2,$

x

$x$

Var (x^{'} y) = E x_{1}^{2} = 1 / n

$\text{Var}(x'y)=\mathbb{E}x_1^2=1/n$

ekvall
fonte

Obrigado, mas estou confuso: o que exatamente é "o resultado desejado" e como se segue da última equação? A distribuição final probabilidade deve depender .

D

$D$

Ameba diz Reinstate Monica

Na verdade, como o resultado segue da sua última equação é exatamente o que é discutido no segmento math.SE que você encontrou. Envolve distribuições beta etc., e o comportamento limitador (para mim) está longe de ser óbvio. Eu acho que deve haver uma maneira mais simples direta ao ver que .

σ^{2} (D) \approx 1 / D

$\sigma^2(D) \approx 1/D$

Ameba diz Reinstate Monica

Depende da dimensão desde , em que é o vetor gaussiano gerado. Atualizarei a resposta mais tarde hoje ou amanhã.

x_{1} = z_{1} | z |^{- 1}

$x_1=z_1 |z|^{-1}$

z

$z$

Ekvall

Uau, ótimo, seu último link fornece o limite dessa expressão envolvendo funções beta inversas (que eu tinha medo de calcular) na terceira equação na página 1. Portanto, para concluir o raciocínio: se a esfera tiver raio , então é (assintoticamente) distribuído como . O que significa que para a esfera de raio variância unidade é vezes menor, isto é, . No entanto, ainda tenho uma preocupação: verifiquei de 1 a 4 e parece dar variação exata , embora as distribuições de D = 1 ou D = 2 estejam muito longe do normal. Deve haver uma razão mais profunda por trás disso.

\sqrt{D}

$\sqrt{D}$

x_{1}

$x_1$

N (0, 1)

$\mathcal{N}(0,1)$

D

$D$

1 / D

$1/D$

D

$D$

1 / D

$1/D$

amoeba diz Restabelecer Monica

@amoeba Sim, atualizado com uma prova disso.

ekvall

Para responder à primeira parte da sua pergunta, indique . Definem O produto dos elementos de e aqui indicados como serão distribuídos de acordo com a distribuição conjunta de e . desde então , $Z = \langle X,Y \rangle = \sum X_i Y_i$

f_{Z_{i}} (z_{i}) = \int_{- \infty}^{\infty} f_{Z_{1}, \dots, Z_{D}} (z_{1}, \dots, z_{D}) d z_{i}

$f_{Z_i}(z_i) = \int_{-\infty}^\infty f_{Z_1,\ldots,Z_D}(z_1,\ldots,z_D) \: d z_i$

i^{t h}

$i^{th}$

X

$X$

Y

$Y$

Z_{i}

$Z_i$

X_{i}

$X_i$

Y_{i}

$Y_i$

f_{Z_{i}} (z_{i}) = \int_{- \infty}^{\infty} f_{X_{i}, Y_{i}} (x, \frac{z_{i}}{x}) \frac{1}{| x |} d x

$f_{Z_i}(z_i) = \int_{-\infty}^\infty f_{X_i,Y_i}(x,\frac{z_i}{x})\frac{1}{|x|}dx$

Z = \sum Z_{i}

$Z = \sum Z_i$

f_{Z} (z) = \int_{- \infty}^{\infty} \dots \int_{- \infty}^{\infty} f_{Z_{1}, \dots, Z_{D}} (z_{1}, \dots, z_{d}) δ (z - \sum z_{i}) d z_{1} \dots d z_{d}

$f_Z(z) = \int_{-\infty}^\infty \ldots \int_{-\infty}^\infty f_{Z_1,\ldots,Z_D} (z_1,\ldots,z_d) \: \delta(z - \sum z_i)\: dz_1\ldots d z_d$

Para a segunda parte, acho que se você quiser dizer algo interessante sobre o comportamento assintótico de precisará pelo menos assumir a independência de e e aplicar um CLT. $\sigma$ $X$ $Y$

Por exemplo, se você estava disposto a assumir que são identificados com e você poderia diga que e . $\{Z_1,\ldots,Z_D\}$ $\mathbb{E}[Z_i] = \mu$ $\mathbb{V}[Z_i] = \sigma^2$ $\sigma^2(D) = \frac{\sigma^2}{D}$ $\lim_{D\to\infty} \sigma^2(D) = 0$

tom
fonte

Obrigado, mas estou confuso com a segunda parte. É claro que e devem ser independentes, acrescentarei isso à questão. Você diz que , e isso parece razoável, mas qual é o comportamento assintótico de ? Eu acho que a expressão que eu estou procurando deve depender somente de . A propósito, em 2D se não me engano, pergunto-me se isso permanece verdadeiro em dimensões mais altas ...

X

$X$

Y

$Y$

σ^{2} (D) = V a r (z_{i}) / D

$\sigma^2(D) = \mathrm{Var}(z_i)/D$

V a r (z_{i})

$\mathrm{Var}(z_i)$

D

$D$

V a r (z_{i}) = 1 / 2

$\mathrm{Var}(z_i)=1/2$

ameba diz Reinstate Monica

É realmente possível que o seja independente, dado o requisito de que e tenham comprimento unitário?

z_{i}

$z_i$

X

$X$

Y

$Y$

Ekvall

@ tom: A propósito, eu estava enganado: em 2D é 1, é que é igual a 1/2. Atualizei minha pergunta com alguns resultados de simulação. Parece que a fórmula correcta é .

V a r (z_{i})

$\mathrm{Var}(z_i)$

V a r (z)

$\mathrm{Var}(z)$

1 / D

$1/D$

Ameba diz Reinstate Monica