Probabilidad de que puntos uniformemente al azar en un rectángulo tienen distancia euclídea inferior a un umbral dado

Question

Supongamos que tenemos $n$ puntos en una planta rectangular con enlazados $[0,a] \times [0,b]$, y estos puntos se distribuyen de manera uniforme en este plano. (No estoy muy familiarizado con las estadísticas, así que no sé la diferencia entre uniformemente elegir un nodo en el área de $[0,a] \times [0,b]$, o de manera uniforme pick $x$-eje de $[0,a]$ $y$- eje de $[0,b]$ de forma independiente).

Dado un umbral de distancia $d$, puede que desee saber la probabilidad de que dos puntos la distancia Euclídea es menos de $d$, o más precisamente, ¿cuántos pares de nodos de la distancia será menor que $d$?

---

Tal vez la siguiente descripción sería ambigua.

Voy a especificar este problema. Dado $n$ nodos y el umbral de $d$. Estos $n$ puntos están distribuidos de manera uniforme en un rectángulo $[0,a] \times [0,b]$. Denotar una variable aleatoria $\xi$ como el número de pares de puntos dentro de la distancia $d$. Encontrar $E[\xi]$.

Answer 1

Podemos resolver este problema analíticamente utilizando algunos intuición geométrica y argumentos. Por desgracia, la respuesta es bastante largo y un poco desordenado.

La configuración básica

En primer lugar, vamos a establecer algunos de notación. Suponemos que dibujar puntos uniformemente al azar desde el rectángulo $[0,a] \times [0,b]$. Podemos suponer sin pérdida de generalidad que $0 < b < a$. Deje $(X_1,Y_1)$ ser las coordenadas del primer punto y $(X_2,Y_2)$ ser las coordenadas del segundo punto. Entonces, $X_1$, $X_2$, $Y_1$, y $Y_2$ son mutuamente independientes con $X_i$ distribuido de manera uniforme en $[0,a]$ $Y_i$ distribuido de manera uniforme en $[0,b]$.

Considerar la distancia Euclidiana entre dos puntos. Este es $$ D = \sqrt{(X_1-X_2)^2 + (Y_1-Y_2)^2} =: \sqrt{ Z_1^2 + Z_2^2} \> , $$ donde$Z_1 = |X_1-X_2|$$Z_2 = |Y_1-Y_2|$.

Distribuciones triangulares

Desde $X_1$ $X_2$ son independientes de los uniformes, a continuación, $X_1 - X_2$ tiene una distribución triangular, de donde $Z_1 = |X_1 - X_2|$ tiene una distribución con función de densidad $$ f_a(z_1) = \frac{2}{a^2}(a-z_1) ,\quad 0 < z_1 < a \> . $$ La correspondiente función de distribución es$F_a(z_1) = 1 - (1-z_1/a)^2$$0 \leq z_1 \leq a$. Del mismo modo, $Z_2 = |Y_1 - Y_2|$ tiene una densidad de $f_b(z_2)$ y la función de distribución de $F_b(z_2)$.

Tenga en cuenta que desde $Z_1$ es una función sólo de los dos $X_i$ $Z_2$ es una función sólo de la $Y_i$, $Z_1$ $Z_2$ son independientes. De manera que la distancia entre los puntos es la norma euclídea de dos variables aleatorias independientes (con diferentes distribuciones).

El panel de la izquierda de la figura muestra la distribución de las $X_1 - X_2$ y el panel de la derecha muestra $Z_1 = |X_1 - X_2|$ donde $a = 5$ en este ejemplo.

Algunos probabilidad geométrica

Por lo $Z_1$ $Z_2$ son independientes y están apoyadas en $[0,a]$ $[0,b]$ respectivamente. Fijo $d$, la función de distribución de la distancia euclidiana es $$\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 \> . $$

Podemos pensar en este geométricamente como tener una distribución en el rectángulo $[0,a] \times [0,b]$ y considerando un cuarto de círculo de radio de $d$. Nos gustaría saber la probabilidad de que está dentro de la intersección de estas dos regiones. Hay tres diferentes posibilidades a considerar:

La región 1 (naranja): $0 \leq d < b$. Aquí el cuarto de círculo se encuentra completamente dentro del rectángulo.

Región 2 (rojo): $b \leq d \leq a$. Aquí el cuarto de círculo interseca el rectange a lo largo de los bordes superior e inferior.

Región 3 (azul): $a < d \leq \sqrt{a^2 + b^2}$. El cuarto de círculo interseca el rectángulo a lo largo de la parte superior y los bordes derecho.

Aquí está una figura, donde podemos dibujar un ejemplo de un radio de cada uno de los tres tipos. El rectángulo se define por $a = 5$, $b = 4$. La escala de grises de mapa de calor en el interior del rectángulo se muestra la densidad de $f_a(z_1) f_b(z_2) \rd z_1 \rd z_2$ donde las zonas oscuras tienen una mayor densidad y zonas más claras tienen menor densidad. Hacer clic en la figura se abrirá una versión más grande de la misma.

Algunos feo cálculo

Para calcular las probabilidades, tenemos que hacer algunos cálculos. Vamos a considerar cada una de las regiones en la vuelta y vamos a ver de que una común, integral, va a surgir. Esta integral tiene una forma cerrada, aunque no es muy bonita.

Región 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 \>. $$

Ahora, el interior de la integral de los rendimientos de $\frac{1}{a^2}\radius (2 a - \radius)$. Así que, sólo nos queda calcular una integral de la forma $$ G(c) - G(0) = \int_0^c (b - y) \radius (2a - \radio) \rd y \> , $$ donde en este caso de interés $c = d$. La antiderivada de el integrando es $$ \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*} $$

De esto podemos conseguir que $\Pr(D \leq d) = \frac{2}{a^2 b^2} (G(d) - G(0))$.

Región 2: $b \leq d \leq a$.

$$ \Pr(D \leq d) = \frac{2}{a^2 b^2} (G(b) - G(0)) \>, $$ por el mismo razonamiento que para la Región 1, excepto que ahora debemos integrar a lo largo de la $y$-eje de todo el camino hasta el$b$, en lugar de sólo $d$.

Región 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*} $$

Por debajo es una simulación de 20000 puntos en los que la trama de la distribución empírica como el gris puntos y el teórico de la distribución como una línea de color de acuerdo a la región en particular que se aplica.

De la misma simulación, a continuación se trazan los primeros 100 pares de puntos y dibujar líneas entre ellos. Cada uno es de color de acuerdo a la distancia entre el par de puntos y que la región esta distancia cae en.

El número esperado de pares de puntos dentro de la distancia $d$ es simplemente $$ \mathbb E[\xi] = {n \elegir 2} \Pr(D \leq d) \>, $$ por la linealidad de las expectativas.

Answer 2

Si los puntos están verdaderamente distribuidos de manera uniforme, es decir, en un patrón conocido, entonces para cualquier distancia d, se puede simplemente lazo sobre todos los pares y el recuento de aquellos dentro de la distancia. Su probabilidad es (número / n).

Si usted tiene más libertad para elegir cómo los n puntos se distribuyen/recogidas, entonces este es el rectangular versión de la paradoja de Bertrand. La página muestra un número de maneras de responder a esta pregunta se basa en cómo se distribuyen sus puntos.