Wahrscheinlichkeit, dass gleichmäßig zufällige Punkte in einem Rechteck einen euklidischen Abstand haben, der unter einem bestimmten Schwellenwert liegt

Angenommen, wir haben Punkte in einem Rechteck mit gebundenen , und diese Punkte sind in dieser Ebene gleichmäßig verteilt. (Ich bin mit Statistiken nicht ganz vertraut, daher kenne ich den Unterschied zwischen der einheitlichen Auswahl eines Knotens im Bereich oder der einheitlichen Auswahl der Achse aus und Achse von unabhängig).$n$$[0,a] \times [0,b]$$[0,a] \times [0,b]$$x$$[0,a]$$y$$[0,b]$

Bei einer Entfernungsschwelle möchte ich vielleicht wissen , mit welcher Wahrscheinlichkeit die euklidische Entfernung von zwei Punkten kleiner als , oder genauer gesagt, wie viele Knotenpaare sind kleiner als ?$d$$d$$d$

---

Vielleicht wäre die folgende Beschreibung eindeutig.

Lassen Sie mich dieses Problem spezifizieren. Gegeben Knoten und Schwelle . Diese Punkte sind gleichmäßig in einem Rechteck . Bezeichnen Sie eine Zufallsvariable als die Anzahl der Punktpaare innerhalb des Abstands . Finde .$n$$d$$n$$[0,a] \times [0,b]$$\xi$$d$$E[\xi]$

Wir können dieses Problem mithilfe einiger geometrischer Intuition und Argumente analytisch lösen . Leider ist die Antwort ziemlich lang und etwas chaotisch.

Grundeinstellung

Lassen Sie uns zunächst eine Notation festlegen. Angenommen, wir zeichnen Punkte gleichmäßig zufällig aus dem Rechteck . Wir nehmen ohne Verlust der Allgemeinheit an, dass . Sei die Koordinate des ersten Punktes und die Koordinate des zweiten Punktes. Dann sind , , und voneinander unabhängig, wobei gleichmäßig auf und gleichmäßig auf .$[0,a] \times [0,b]$$0 < b < a$$(X_1,Y_1)$$(X_2,Y_2)$$X_1$$X_2$$Y_1$$Y_2$$X_i$$[0,a]$$Y_i$$[0,b]$

Betrachten Sie den euklidischen Abstand zwischen den beiden Punkten. Dies ist wobeiund.Z 1 = | X 1 - X 2 | Z 2 = | Y 1 - Y 2

$$D = \sqrt{(X_1-X_2)^2 + (Y_1-Y_2)^2} =: \sqrt{ Z_1^2 + Z_2^2} \> ,$$ $Z_1 = |X_1-X_2|$$Z_2 = |Y_1-Y_2|$

Dreiecksverteilungen

Da und unabhängige Uniformen sind, hat eine dreieckige Verteilung, woraushat eine Verteilung mit der Dichtefunktion Die entsprechende Verteilungsfunktion ist für . In ähnlicher Weise isthat die Dichte und die Verteilungsfunktion .X 2 X 1 - X 2 Z 1 = | X 1 - X 2 | f a ( z 1 ) = $X_1$$X_2$$X_1 - X_2$$Z_1 = |X_1 - X_2|$F a

$$f_a(z_1) = \frac{2}{a^2}(a-z_1) ,\quad 0 < z_1 < a \> .$$ 0 ≤ z 1 ≤ a Z 2 = | Y 1 - Y 2 | f b ( z 2 ) F b ( z 2$F_a(z_1) = 1 - (1-z_1/a)^2$$0 \leq z_1 \leq a$$Z_2 = |Y_1 - Y_2|$$f_b(z_2)$$F_b(z_2)$

Beachten Sie, dass seit eine Funktion nur von den beiden ist und ist nur eine Funktion der , dann und sind unabhängig. Der Abstand zwischen den Punkten ist also die euklidische Norm zweier unabhängiger Zufallsvariablen (mit unterschiedlichen Verteilungen).X i Z 2 Y i Z 1 Z $Z_1$$X_i$$Z_2$$Y_i$$Z_1$$Z_2$

Das linke Feld der Abbildung zeigt die Verteilung von und das rechte Feld zeigtDabei ist in diesem Beispiel.Z 1 = | X 1 - X 2 | a = $X_1 - X_2$$Z_1 = |X_1 - X_2|$$a = 5$

Eine geometrische Wahrscheinlichkeit

So und sind unabhängig und werden auf unterstützte und ist. Für festes lautet die Verteilungsfunktion des euklidischen Abstands $Z_1$$Z_2$$[0,a]$$[0,b]$$d$

$$\renewcommand{\Pr}{\mathbb P}\newcommand{\rd}{\,\mathrm{d}} \Pr(D \leq d) = \iint_{\{z_1^2+z_2^2 \leq d^2\}} f_a(z_1) f_b(z_2) \rd z_1 \rd z_2 \> .$$

Wir können uns dies geometrisch als eine Verteilung auf dem Rechteck und einen Viertelkreis mit dem Radius . Wir möchten die Wahrscheinlichkeit kennen, die innerhalb des Schnittpunkts dieser beiden Regionen liegt. Es gibt drei verschiedene Möglichkeiten:$[0,a] \times [0,b]$$d$

Region 1 (orange): . Hier liegt der Viertelkreis vollständig innerhalb des Rechtecks.$0 \leq d < b$

Region 2 (rot): . Hier schneidet der Viertelkreis den Rechteck entlang der Ober- und Unterkante.$b \leq d \leq a$

Region 3 (blau): . Der Viertelkreis schneidet das Rechteck am oberen und rechten Rand.$a < d \leq \sqrt{a^2 + b^2}$

Hier ist eine Abbildung, in der wir einen Beispielradius für jeden der drei Typen zeichnen. Das Rechteck ist definiert durch , . Die Graustufen-Heatmap innerhalb des Rechtecks ​​zeigt die Dichte wobei dunkle Bereiche eine höhere Dichte und hellere Bereiche eine geringere Dichte aufweisen. Durch Klicken auf die Abbildung wird eine größere Version davon geöffnet.b = 4 f a ( z 1 ) f b ( z 2$a = 5$$b = 4$$f_a(z_1) f_b(z_2) \rd z_1 \rd z_2$

Ein hässlicher Kalkül

Um die Wahrscheinlichkeiten zu berechnen, müssen wir einige Berechnungen durchführen. Betrachten wir nacheinander jede Region und sehen, dass ein gemeinsames Integral entsteht. Dieses Integral hat eine geschlossene Form, obwohl es nicht sehr hübsch ist.

Region 1 : .$0 \leq d < b$

$$\newcommand{\radius}{\sqrt{d^2 - y^2}} \Pr(D \leq d) = \int_0^d \int_0^{\radius} f_b(y) f_a(x) \rd x \rd y = \int_0^d f_b(y) \int_0^{\radius} f_a(x) \rd x \rd y \>.$$

Das innere Integral ergibt nun . Wir müssen also ein Integral der Form berechnen wobei in diesem Fall von Interesse . Das Antiderivativ des Integranden ist $\frac{1}{a^2}\radius (2 a - \radius)$

$$G(c) - G(0) = \int_0^c (b - y) \radius (2a - \radius) \rd y \> ,$$ $c = d$ $$\begin{align*} G(y) &= \int (b - y) \radius (2a - \radius) \rd y \\ &= \frac{a}{3} \radius ( y (3 b - 2 y) + 2 d^2) \\ &\quad + \,a b d^2 \tan^{-1}\Big(\frac{y}{{\scriptstyle \radius}}\Big) - b d^2 y \\ &\quad + \,\frac{b y^3}{3} + \frac{(d y)^2}{2} - \frac{y^4}{4} \> . \end{align*}$$

Daraus ergibt sich .$\Pr(D \leq d) = \frac{2}{a^2 b^2} (G(d) - G(0))$

Region 2 : .$b \leq d \leq a$

$$\Pr(D \leq d) = \frac{2}{a^2 b^2} (G(b) - G(0)) \>,$$ nach den gleichen Überlegungen wie für Region 1, außer dass wir jetzt integrieren müssen entlang der Achse bis nach statt nur .$y$$b$$d$

Region 3 : . $a < d \leq \sqrt{a^2 + b^2}$

$$\begin{align*} \Pr(D \leq d) &= \int_0^\sqrt{d^2-a^2} f_b(y)\rd y + \int_{\sqrt{d^2-a^2}}^b f_b(y) \int_{0}^\radius f_a(x) \rd x \rd y \\ &= F_b(\sqrt{d^2-a^2}) + \frac{2}{a^2 b^2} (G(b) - G(\sqrt{d^2-a^2})) \end{align*}$$

Im Folgenden finden Sie eine Simulation von 20000 Punkten, in der wir die empirische Verteilung als graue Punkte und die theoretische Verteilung als Linie darstellen, die entsprechend der jeweiligen Region gefärbt ist.

Aus derselben Simulation zeichnen wir unten die ersten 100 Punktepaare und zeichnen Linien zwischen ihnen. Jedes ist entsprechend dem Abstand zwischen dem Punktpaar und dem Bereich, in den dieser Abstand fällt, gefärbt.

Die erwartete Anzahl von Punktpaaren innerhalb des Abstands ist einfach durch Linearität der Erwartung.E [ ξ ] = ($d$

$$\mathbb E[\xi] = {n \choose 2} \Pr(D \leq d) \>,$$

Wenn die Punkte wirklich gleichmäßig verteilt sind, dh in einem festen bekannten Muster, können Sie für jede Entfernung d einfach alle Paare durchlaufen und diejenigen innerhalb der Entfernung zählen. Ihre Wahrscheinlichkeit ist (diese Zahl / n).

Wenn Sie die zusätzliche Freiheit haben, auszuwählen, wie die n Punkte verteilt / ausgewählt werden, ist dies die rechteckige Version des Bertrand-Paradoxons . Diese Seite zeigt eine Reihe von Möglichkeiten zur Beantwortung dieser Frage, je nachdem, wie Sie Ihre Punkte verteilen.