Rozkład produktów skalarnych dwóch losowych wektorów jednostkowych w wymiarach

Jeśli i są dwoma niezależnymi wektorami jednostek losowych w (równomiernie rozmieszczonymi na kuli jednostkowej), jaki jest rozkład ich iloczynu skalarnego (iloczyn skalarny) ? $\mathbf{x}$ $\mathbf{y}$ $\mathbb{R}^D$ $\mathbf x \cdot \mathbf y$

Wydaje mi się, że gdy szybko rośnie rozkład (?) Staje się normalny z zerową średnią i wariancją malejącą w wyższych wymiarach ale czy istnieje wyraźna formuła dla ? $D$

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

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

σ^{2} (D)

$\sigma^2(D)$

Aktualizacja

Przeprowadziłem kilka szybkich symulacji. Po pierwsze, generując 10000 par wektorów jednostek losowych dla $D=1000$ , łatwo zauważyć, że rozkład ich produktów kropkowych jest idealnie gaussowski (w rzeczywistości jest już dość gaussowski dla $D=100$ ), patrz wykres po lewej stronie. Po drugie, dla każdego $D$ zakresie od 1 do 10000 (z rosnącymi krokami) wygenerowałem 1000 par i obliczyłem wariancję. Działka logarytmiczny pokazany jest po prawej stronie, a jasne jest, że formuła jest bardzo dobrze aproksymować $1/D$ . Zauważ, że dla $D=1$ i $D=2$ ta formuła daje nawet dokładne wyniki (ale nie jestem pewien, co się stanie później).

iloczyny między losowymi wektorami jednostek

mathematical-statistics linear-algebra beta-distribution ameba mówi Przywróć Monikę
źródło

@KarlOskar: dziękuję, ten link jest bardzo trafny i faktycznie czyni moje pytanie prawie duplikatem, ale nie całkiem. Istnieje więc wyraźna formuła dla która jest funkcją skumulowanego rozkładu produktów kropkowych. Można pobrać pochodną, aby uzyskać plik PDF, a następnie przestudiować limit . Jednak wzór podano w kategoriach funkcji beta i niekompletnych funkcji beta, więc obliczenia prawdopodobnie będą nieprzyjemne.

P {(x, y) > ϵ}

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

D \to \infty

$D\to \infty$

ameba mówi Przywróć Monikę

@KarlOskar: z rozkładu równomiernego na sferze jednostkowej w . Aby wygenerować losowy wektor z tego rozkładu, można wygenerować losowy wektor z Gaussa o wariancji jednostkowej, a następnie znormalizować go.

R^{D}

$\mathbb{R}^D$

ameba mówi Przywróć Monikę

Odpowiedzi:

Ponieważ ( jak dobrze wiadomo ) równomierny rozkład na sferze jednostkowej uzyskuje się przez normalizację rozkładu normalnego zmiennego a iloczynem kropki znormalizowanych wektorów jest ich współczynnik korelacji, odpowiedzi na trzy pytania to: $S^{D-1}$ $D$ $t$

$u= (t+1)/2$ ma rozkład Beta . $((D-1)/2,(D-1)/2)$
Wariancja jest równa (jak spekulowano w pytaniu). $t$ $1/D$
Standaryzowany rozkład zbliża się do normalności w tempie $t$ $O\left(\frac{1}{D}\right).$

metoda

Dokładny rozkład iloczyn skalarny wektorów jednostkowych można łatwo uzyskać geometrycznie, ponieważ jest składnikiem drugiego wektora w kierunku pierwszego. Ponieważ drugi wektor jest niezależny od pierwszego i jest równomiernie rozmieszczony na kuli jednostkowej, jego komponent w pierwszym kierunku jest rozłożony tak samo, jak dowolna współrzędna kuli. (Zauważ, że rozkład pierwszego wektora nie ma znaczenia.)

Znalezienie gęstości

Pozwalając, że koordynuje się ostatniego, gęstość w jest więc proporcjonalna do obszaru powierzchni do leżenia na wysokości między i w sferze jednostkowej. Ta proporcja występuje w obrębie pasa o wysokości i promieniu który jest w zasadzie stożkiem ściętym zbudowanym z o promieniu wysokości i nachylenia . Skąd prawdopodobieństwo jest proporcjonalne do $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)}})}^{re - 2)}}{\sqrt{1 - t^{2)}}} re t = (1 - t^{2)})^{(re - 3)) / 2)} re t .

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

Pozostawienie pociąga za sobą . Podstawienie tego do powyższego daje element prawdopodobieństwa do stałej normalizującej: $u=(t+1)/2 \in [0,1]$ $t = 2u-1$

{fa}_{re} (u) re u \propto (1 - (2) u - 1)^{2)})^{(re - 3)) / 2)} re (2) u - 1) = {2)}^{re - 2)} (u - u^{2)})^{(re - 3)) / 2)} re 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.$

Jest natychmiastowe, że ma rozkład Beta , ponieważ (z definicji) jego gęstość jest również proporcjonalna do $u=(t+1)/2$ $((D-1)/2, (D-1)/2)$

u^{(re - 1) / 2) - 1} {(1 - u)}^{(re - 1) / 2) - 1} = (u - u^{2)})^{(re - 3)) / 2)} \propto {fa}_{re} (u) .

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

Określenie zachowania granicznego

Informacje o zachowaniu ograniczającym wynikają łatwo z tego za pomocą technik elementarnych: można zintegrować, aby uzyskać stałą proporcjonalności ; można zintegrować (na przykład wykorzystując właściwości funkcji Beta) w celu uzyskania momentów, co pokazuje, że wariancja wynosi i zmniejsza się do (skąd, zgodnie z twierdzeniem Czebyszewa, prawdopodobieństwo koncentruje się w pobliżu ); a następnie rozkład graniczny jest przez uwzględnienie wartości gęstości znormalizowanego rozkładu, proporcjonalnego do dla małych wartości $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 ({fa}_{re} (t / \sqrt{re})) & = do (re) + \frac{re - 3)}{2)} \log (1 - \frac{t^{2)}}{re}) \\ = do (re) - (1 / 2) + \frac{3)}{2) re}) t^{2)} + O (\frac{t^{4}}{re}) \\ \to do - \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 }$

gdzie litery reprezentują (log) stałe integracji. Oczywiście szybkość, z jaką zbliża się to do normalności (dla której gęstość logarytmu jest równa ), wynosi $C$ $-\frac{1}{2}t^2$ $O\left(\frac{1}{D}\right).$

Postać

Ten wykres pokazuje gęstości iloczynu dla , w standaryzacji dla wariancji jednostkowej i ich graniczną gęstość. Wartości przy rosną wraz z (od niebieskiego przez czerwony, złoty, a następnie zielony dla standardowej gęstości normalnej). Gęstość dla byłaby nie do odróżnienia od gęstości normalnej przy tej rozdzielczości. $D=4, 6, 10$ $0$ $D$ $D=1000$

Whuber
źródło

(+1) Dziękuję bardzo, @whuber, to świetna odpowiedź! Specjalne podziękowania za wspomnienie słowa „frustum”. Zdarza się, że zaakceptowałem inną odpowiedź na kilka minut przed wysłaniem twojej i nie chciałbym jej teraz odrzucać; nadzieję, że rozumiesz. Szkoda, że nie można zaakceptować obu! Nawiasem mówiąc, zauważ bardzo prosty dowód wyrażenia dla wariancji z tej odpowiedzi: można to zobaczyć bezpośrednio, bez bałagania się z funkcjami beta! Wariancja iloczynu kropkowego jest równa wariancji dowolnej współrzędnej kuli (jak napisałeś), a suma wszystkich powinna wynosić , QED

1 / D

$1/D$

D

$D$

1

$1$

amoeba mówi Przywróć Monikę

To miła obserwacja na temat wariancji.

whuber

@amoeba, ostatnia aktywność również zwróciła moją uwagę tutaj i choć doceniam, że zaakceptowałeś moją odpowiedź, ta jest o wiele pełniejsza. Nie miałbym nic przeciwko, gdybyś się zmienił.

ekvall

@ Student001: jest to uczciwy i hojny komentarz. Zmieniłem przyjętą odpowiedź. Znalazłem też jedno twoje i jedno twoje A, aby głosować, aby to naprawić :)

amoeba mówi Przywróć Monikę

@mat Rozkład jest równy . To sprawia, że jest to rozkład Beta, który został przeskalowany i przesunięty z przedziału na przedział .

t

$t$

2 U - 1

$2U-1$

[0, 1]

$[0,1]$

[- 1, 1]

$[-1,1]$

whuber

Znajdźmy rozkład, a następnie wariancja podąża za standardowymi wynikami. Rozważ produkt wektorowy i napisz go w postaci cosinusowej, tzn. Zauważ, że mamy w którym jest kątem pomiędzy i . W ostatnim kroku użyłem tego dla wszystkich zdarzeń iTeraz rozważmy termin . Oczywiste jest, że ponieważ jest wybierany równomiernie względem powierzchni kuli, nie ma znaczenia, co

P. (x^{'} y \leq t) = P. (| x | | y | sałata θ \leq t) = P. (sałata θ \leq t) = mi P. (sałata θ \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$

mi P. (ZA ∣ b) : = mi [mi [χ_{ZA} ∣ b]] = mi χ_{ZA} = P. (ZA) .

$\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$ faktycznie jest tylko kąt między i sprawach. Tak więc termin wewnątrz oczekiwania jest faktycznie stały w funkcji i możemy wlog założyć, żeNastępnie otrzymujemyale ponieważ jest pierwszą współrzędną znormalizowanego wektora gaussowskiego w mamy, że jest gaussowskim z wariancją przez wywołanie asymptotycznego wyniku tego artykułu .

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$

Aby uzyskać wyraźny wynik wariancji, użyj faktu, że iloczyn skalarny oznacza zero przez niezależność i, jak pokazano powyżej, rozkłada się jak pierwsza współrzędna . Według tych wyników znalezienie oznacza znalezienie . Zauważmy, że dla konstrukcji więc możemy napisać gdzie ostatnia równość wynika z tego, że współrzędne są identycznie rozmieszczone. , odkryliśmy, że $x$ $\text{Var}(x'y)$ $\mathbb{E}x_1^2$ $x'x=1$

1 = mi x^{'} x = mi \sum_{ja = 1}^{n} x_{ja}^{2)} = \sum_{ja = 1}^{n} mi x_{ja}^{2)} = n mi 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
źródło

Dziękuję, ale jestem zdezorientowany: czym dokładnie jest „pożądany wynik” i jak wynika z ostatniego równania? Ostateczny rozkład prawdopodobieństwa powinien zależeć .

D

$D$

ameba mówi Przywróć Monikę

W rzeczywistości sposób, w jaki wynik wynika z ostatniego równania, jest dokładnie omawiany w wątku math.SE , który znaleziono. Dotyczy dystrybucji beta itp., A zachowanie ograniczające jest (dla mnie) dalekie od oczywistych. Chyba nie powinien być prościej bezpośredni sposób, aby zobaczyć, że .

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

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

ameba mówi Przywróć Monikę

Zależy to od wymiaru, ponieważ , gdzie jest wygenerowanym wektorem gaussowskim. Zaktualizuję odpowiedź później dzisiaj lub jutro.

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

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

z

$z$

ekvall

Wow, świetnie, twój ostatni link zawiera granicę tego wyrażenia obejmującego odwrotne funkcje beta (które bałam się obliczyć) w trzecim równaniu na stronie 1. Więc uzupełnij rozumowanie: jeśli kula ma promień , wtedy jest (asymptotycznie) dystrybuowany jako . Co oznacza, że dla promienia kuli wariancji jednostka jest -krotnie mniejsza, czyli . Jednak nadal mam obawy: sprawdziłem od 1 do 4, a wydaje się dawać dokładną wariancję, mimo że rozkłady dla D = 1 lub D = 2 są bardzo dalekie od normalnych. Powodem tego powinien być głębszy powód.

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

ameba mówi Przywróć Monikę

@amoeba Tak, zaktualizowano o tym dowód.

ekvall

Aby odpowiedzieć na pierwszą część pytania, oznacz . Definiują Iloczyn elementami od i oznaczoną tu jako zostaną rozdzielone zgodnie ze wspólnym dystrybucji i . następnie od , $Z = \langle X,Y \rangle = \sum X_i Y_i$

{fa}_{Z_{ja}} (z_{ja}) = \int_{- \infty}^{\infty} {fa}_{Z_{1}, \dots, Z_{re}} (z_{1}, \dots, z_{re}) re z_{ja}

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

{fa}_{Z_{ja}} (z_{ja}) = \int_{- \infty}^{\infty} {fa}_{X_{ja}, Y_{ja}} (x, \frac{z_{ja}}{x}) \frac{1}{| x |} re 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$

{fa}_{Z} (z) = \int_{- \infty}^{\infty} \dots \int_{- \infty}^{\infty} {fa}_{Z_{1}, \dots, Z_{re}} (z_{1}, \dots, z_{re}) δ (z - \sum z_{ja}) re z_{1} \dots re z_{re}

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

W drugiej części myślę, że jeśli chcesz powiedzieć coś interesującego o asymptotycznym zachowaniu , musisz przynajmniej założyć niezależność i , a następnie zastosować CLT. $\sigma$ $X$ $Y$

Na przykład, jeśli chcesz założyć, że mają tę samą wartość z i możesz powiedz, że i . $\{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$

Tomek
źródło

Dziękuję, ale jestem zdezorientowany co do drugiej części. i są oczywiście niezależne, dodam to do pytania. Mówisz, że , i to brzmi rozsądnie, ale jakie jest asymptotyczne zachowanie ? Myślę, że ekspresja szukam powinna zależeć wyłącznie od . Nawiasem mówiąc w 2D jeśli się nie mylę, zastanawiam się, czy to prawda w wyższych wymiarach ...

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$

Amoeba mówi Przywróć Monikę

Czy naprawdę jest możliwe, aby był niezależny, biorąc pod uwagę, że i mają długość jednostkową?

z_{i}

$z_i$

X

$X$

Y

$Y$

ekvall

@tom: Przy okazji, to błędne: 2D wynosi 1, to , która jest równa 1/2. Zaktualizowałem moje pytanie o niektóre wyniki symulacji. Wydaje się, że wzór jest poprawna .

V a r (z_{i})

$\mathrm{Var}(z_i)$

V a r (z)

$\mathrm{Var}(z)$

1 / D

$1/D$

ameba mówi Przywróć Monikę