Verteilung von Skalarprodukten zweier zufälliger Einheitsvektoren in Dimensionen

Wenn und zwei unabhängige zufällige Einheitsvektoren in (gleichmäßig auf einer Einheitskugel verteilt), wie lautet die Verteilung ihres Skalarprodukts (Skalarprodukt) ? $\mathbf{x}$ $\mathbf{y}$ $\mathbb{R}^D$ $\mathbf x \cdot \mathbf y$

Ich vermute, als wächst, wird die Verteilung schnell normal (?), Wobei der Mittelwert Null und die Varianz in höheren Dimensionen abnehmen. aber gibt es eine explizite Formel für ? $D$

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

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

σ^{2} (D)

$\sigma^2(D)$

Aktualisieren

Ich habe einige schnelle Simulationen durchgeführt. Wenn man 10000 Paare zufälliger Einheitsvektoren für $D=1000$ , ist leicht zu erkennen, dass die Verteilung ihrer Punktprodukte perfekt Gauß ist (tatsächlich ist sie bereits für ziemlich Gauß $D=100$ ), siehe die Nebenkurve auf der linken Seite. Zweitens habe ich für jedes $D$ Bereich von 1 bis 10000 (mit zunehmenden Schritten) 1000 Paare generiert und die Varianz berechnet. Log-Log-Plot wird rechts gezeigt, und es ist klar, dass die Formel sehr gut durch angenähert ist $1/D$ . Beachten Sie, dass diese Formel für $D=1$ und $D=2$ sogar genaue Ergebnisse liefert (aber ich bin nicht sicher, was später passiert).

Punktprodukte zwischen zufälligen Einheitsvektoren

mathematical-statistics linear-algebra beta-distribution Amöbe sagt Reinstate Monica
quelle

@KarlOskar: Danke, dieser Link ist sehr relevant, und in der Tat macht meine Frage fast ein Duplikat, aber nicht ganz. Es gibt also eine explizite Formel für die eine kumulative Verteilungsfunktion der Punktprodukte ist. Man kann eine Ableitung nehmen, um das PDF zu erhalten und dann das Limit studieren . Die Formel wird jedoch in Form von Betafunktionen und unvollständigen Betafunktionen angegeben, sodass die Berechnungen wahrscheinlich unangenehm sind.

P {(x, y) > ϵ}

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

D \to \infty

$D\to \infty$

Amöbe sagt Reinstate Monica

@KarlOskar: von der gleichmäßigen Verteilung auf einem Einheitskugel in . Um einen Zufallsvektor aus dieser Verteilung zu erzeugen, kann man einen Zufallsvektor aus einem Gaußschen mit einer Einheitsvarianz erzeugen und ihn dann normalisieren.

R^{D}

$\mathbb{R}^D$

Amöbe sagt Reinstate Monica

Antworten:

Da ( wie allgemein bekannt ) eine gleichmäßige Verteilung auf der Einheitskugel durch Normalisieren einer Variantennormalverteilung erhalten wird und das Punktprodukt der normalisierten Vektoren ihr Korrelationskoeffizient ist, sind die Antworten auf die drei Fragen sind: $S^{D-1}$ $D$ $t$

$u= (t+1)/2$ hat eine Beta -Verteilung. $((D-1)/2,(D-1)/2)$
Die Varianz von ist (wie in der Frage spekuliert). $t$ $1/D$
Die standardisierte Verteilung von nähert sich der Normalität mit einer Rate von $t$ $O\left(\frac{1}{D}\right).$

Methode

Die genaue Verteilung des Punktprodukts von Einheitsvektoren ist geometrisch leicht zu erhalten, da dies die Komponente des zweiten Vektors in Richtung des ersten ist. Da der zweite Vektor unabhängig vom ersten ist und gleichmäßig auf der Einheitskugel verteilt ist, ist seine Komponente in der ersten Richtung genauso verteilt wie jede Koordinate der Kugel. (Beachten Sie, dass die Verteilung des ersten Vektors keine Rolle spielt.)

Die Dichte finden

Wenn diese Koordinate die letzte ist, ist die Dichte bei daher proportional zur Oberfläche, die in einer Höhe zwischen und auf der Einheitskugel liegt. Dieser Anteil tritt innerhalb eines Riemens mit der Höhe und dem Radius der im Wesentlichen ein Kegelstumpf ist , der aus einem mit dem Radius der Höhe und Steigung . Woher ist die Wahrscheinlichkeit proportional zu $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.$

Wenn ist, ist . Wenn man das in das Vorhergehende einfügt, ergibt sich für das Wahrscheinlichkeitselement eine normalisierende Konstante: $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.$

Es ist unmittelbar, dass eine Beta -Verteilung hat, weil (per Definition) auch seine Dichte proportional zu ist $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).$

Festlegen des Begrenzungsverhaltens

Daraus ergeben sich mit elementaren Techniken leicht Informationen über das Begrenzungsverhalten: kann integriert werden, um die Proportionalitätskonstante ; kann integriert werden (z. B. unter Verwendung von Eigenschaften von Beta-Funktionen), um Momente zu erhalten, die zeigen, dass die Varianz und auf schrumpft (ausgehend von Chebyshevs Theorem wird die Wahrscheinlichkeit in der Nähe von konzentriert) ); und die Grenzverteilung wird dann gefunden, indem Werte der Dichte der standardisierten Verteilung, proportional zu für kleine Werte von berücksichtigt werden $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 }$

wobei die 's (log) Integrationskonstanten darstellen. Offensichtlich ist die Rate, mit der sich dies der Normalität nähert (für die die logarithmische Dichte gleich ), $C$ $-\frac{1}{2}t^2$ $O\left(\frac{1}{D}\right).$

Zahl

Dieses Diagramm zeigt die Dichten des Punktprodukts für , wie auf Einheitsvarianz standardisiert, und ihre Grenzdichte. Die Werte bei erhöhen sich mit (von blau über rot, gold und dann grün für die normale Standarddichte). Die Dichte für wäre bei dieser Auflösung nicht von der normalen Dichte zu unterscheiden. $D=4, 6, 10$ $0$ $D$ $D=1000$

whuber
quelle

(+1) Vielen Dank, @whuber, das ist eine großartige Antwort! Besonderer Dank für die Erwähnung des Wortes "Kegelstumpf". Es ist so, dass ich eine weitere Antwort nur wenige Minuten vor Ihrem Posting angenommen habe und ich sie jetzt nicht mehr ablehnen möchte. Ich hoffe du verstehst. Schade, dass es nicht möglich ist, beides zu akzeptieren! Übrigens, beachten Sie einen sehr einfachen Beweis des Ausdrucks für die Abweichung von dieser Antwort: Man kann ihn direkt sehen, ohne mit Betafunktionen herumzuspielen! Varianz des Punktprodukts zu Varianz jeder Kugel koordinieren gleich (wie Sie geschrieben haben ) und eine Summe aller von ihnen sein sollte , QED

1 / D

$1/D$

D

$D$

1

$1$

Amöbe sagt wieder einzusetzen Monica

Das ist eine schöne Beobachtung über die Abweichungen.

whuber

@amoeba, die jüngste Aktivität hat auch hier wieder meine Aufmerksamkeit erregt, und so sehr ich es schätze, dass Sie meine Antwort akzeptiert haben, so viel voller ist diese. Es würde mir nichts ausmachen, wenn Sie sich ändern würden.

Freitag,

@ Student001: das ist ein fairer und großzügiger Kommentar. Ich habe die akzeptierte Antwort gewechselt. Ich habe auch ein Q und ein A von Ihnen gefunden, um das auszugleichen :)

Amöbe sagt Reinstate Monica

@mat Die Verteilung von ist die von . Das macht es zu einer Beta-Verteilung, die skaliert und vom Intervall in das Intervall verschoben wurde .

t

$t$

2 U - 1

$2U-1$

[0, 1]

$[0,1]$

[- 1, 1]

$[-1,1]$

whuber

Lassen Sie uns anhand der Standardergebnisse die Verteilung und dann die Varianz bestimmen. Betrachten Sie das Vektorprodukt und schreiben Sie es in seine Kosinusform, dh beachten Sie, dass wir wobei der Winkel zwischen und . Im letzten Schritt habe ich das für alle Ereignisse undBetrachte nun den Term . Es ist klar, dass es keine Rolle spielt, was ist, da Bezug auf die Kugeloberfläche gleichmäßig gewählt wird

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$ eigentlich ist nur der winkel zwischen und bedeutung. Somit ist der Term innerhalb der Erwartung als Funktion von tatsächlich konstant und wir können annehmen, dassDann erhalten wiraber da die erste Koordinate eines normalisierten in wir, wir das asymptotische Ergebnis dieser Arbeit aufrufen dass Gauß mit der Varianz .

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$

Um ein explizites Ergebnis der Varianz zu erhalten, verwenden Sie die Tatsache, dass das Skalarprodukt Null als Unabhängigkeit bedeutet und, wie oben gezeigt, wie die erste Koordinate von . Nach diesen Ergebnissen entspricht das Finden von dem Finden von . Beachten Sie nun, dass pro Konstruktion und somit wobei die letzte Gleichheit daraus folgt, dass die Koordinaten von identisch verteilt sind. Beim Zusammenfügen haben wir festgestellt, dass $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
quelle

Danke, aber ich bin verwirrt: Was genau ist "das gewünschte Ergebnis" und wie folgt es aus der letzten Gleichung? Die endgültige Wahrscheinlichkeitsverteilung sollte von abhängen .

D

$D$

Amöbe sagt Reinstate Monica

Wie das Ergebnis aus Ihrer letzten Gleichung hervorgeht, ist genau das, was Sie im math.SE-Thread gefunden haben. Es handelt sich um Betaverteilungen usw., und das einschränkende Verhalten ist (für mich) alles andere als offensichtlich. Ich denke, es sollte einen einfacheren direkten Weg geben, um dieses .

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

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

Amöbe sagt Reinstate Monica

Dies hängt von der Dimension ab, da , wobei der generierte Gaußsche Vektor ist. Ich werde die Antwort später heute oder morgen aktualisieren.

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

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

z

$z$

ekvall

Wow, toll, Ihr letztes Glied stellt die Grenze dieses Ausdrucks , den inversen Beta - Funktionen (was ich habe Angst , zu berechnen) in der dritten Gleichung auf Seite 1. So die Argumentation zu vervollständigen: Wenn die Kugel des Radius , dann wird (asymptotisch) als . Das bedeutet , dass für den Bereich des Einheitsradius Varianz - mal kleiner, dh . Ich habe jedoch immer noch Bedenken: Ich habe nach von 1 bis 4 gesucht, und scheint eine exakte Varianz zu ergeben , obwohl die Verteilungen für D = 1 oder D = 2 weit vom Normalen entfernt sind. Es sollte einen tieferen Grund dafür geben.

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

Amöbe sagt Reinstate Monica

@amoeba Ja, aktualisiert mit einem Beweis dafür.

Freitag,

Um den ersten Teil Ihrer Frage zu beantworten, bezeichnen Sie . Definiere Das Produkt der -Elemente von und die hier als werden, werden gemäß der gemeinsamen Verteilung von und . dann seit , $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$

Für den zweiten Teil denke ich, dass Sie, wenn Sie etwas Interessantes über das asymptotische Verhalten von sagen möchten, mindestens die Unabhängigkeit von und annehmen und dann eine CLT anwenden müssen. $\sigma$ $X$ $Y$

Wenn Sie beispielsweise annehmen , dass die mit und Sie dies Sagen Sie, dass und . $\{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
quelle

Danke, aber ich bin verwirrt über den zweiten Teil. und sollen natürlich unabhängig sein, das werde ich der Frage hinzufügen. Sie sagen, dass , und das klingt vernünftig, aber wie ist das asymptotische Verhalten von ? Ich denke, der gesuchte Ausdruck sollte nur von abhängen . Übrigens in 2D wenn ich mich nicht irre, frage ich mich, ob dies in höheren Dimensionen wahr bleibt ...

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$

Amöbe sagt Reinstate Monica

Ist es wirklich möglich, dass unabhängig ist, , dass und eine Längeneinheit haben?

z_{i}

$z_i$

X

$X$

Y

$Y$

ekvall

@ Tom: Übrigens, ich war verwechselt: in 2D 1 ist, ist es , die gleich 1/2 ist. Ich habe meine Frage mit einigen Simulationsergebnissen aktualisiert. Die richtige Formel scheint .

V a r (z_{i})

$\mathrm{Var}(z_i)$

V a r (z)

$\mathrm{Var}(z)$

1 / D

$1/D$

Amöbe sagt Reinstate Monica