¿Cuál es la probabilidad de que un polígono n-sided hecho de n puntos aleatorios distintos en el círculo contenga el centro?
Respuesta
¿Demasiados anuncios?
Si usted escoge $n$ distintos puntos en el círculo, entonces el casco convexo de estos no contienen el centro de la circunferencia si y sólo si hay una línea a través del centro de tal forma que todos los $n$ puntos se encuentran en el mismo lado de la línea. O en otras palabras, si todos se encuentran en un ángulo de menos de $\pi$.
Distribuciones de probabilidad
Voy a empezar con algunas bastante algebraica de derivación. Si usted encuentra esto muy complicado, saltar el último párrafo para que sea más intuitivo descripción. Si usted siente que su intuición podría fácilmente confundir a usted, se adhieren al enfoque más formal.
Basado en la observación anterior, me había concentrado en el ángulo de $\alpha_n$ atravesado por $n$ puntos. Esta es una variable aleatoria, por lo que se puede describir mediante una función de densidad de probabilidad o la función de distribución acumulativa. Vamos a escribir $F_n$ para la función de distribución acumulativa (es decir, $F_n(x) = \Pr(\alpha_n\le x))$ $f_n=\frac{\mathrm d}{\mathrm dx}F_n$ para la función de densidad de probabilidad.
Como fundación, el caso de un solo punto puede ser expresado mediante la delta de Dirac "función", desde el ángulo abarcado por un solo punto, siempre es exactamente cero. Así que usted consigue $f_1(x)=\delta(x)$ $F_1(x)=1$ no negativos $x$.
Luego viene una parte recursiva, que podría ser más fácil de comprender mediante el uso de la función de distribución acumulativa de primera. ¿Cuál es la probabilidad de que el ángulo no es mayor que $x$?
$$F_{n+1}(x) = \int_{y=0}^x \frac{y+2(x-y)}{2\pi}f_n(y) \;\mathrm dy$$
¿Cómo se puede leer esto? Así, la probabilidad de que para el $(n+1)$-ésimo punto de que el ángulo es en la mayoría de las $x$, usted tiene que considerar todos los casos donde la anterior $n$ puntos se distribuyeron más de algunos de los más pequeños del ángulo de $y$, y, a continuación, qué tan probable es que el nuevo punto de mentira dentro de este ángulo $y$ o dentro de la cantidad extra $(x-y)$ en cualquiera de los lados del ángulo a $y$. Esta formulación no tomar wrap-around en cuenta correctamente, por lo que se producirá un error de $x>\pi$, pero al final todo lo que necesitamos es $x\le\pi$ así que debe estar bien. Vamos a dividir que la función, así que es más fácil de integrar.
$$F_{n+1}(x) = \frac{x}{\pi}\int_{y=0}^x f_n(y)\;\mathrm dy - \frac1{2\pi}\int_{y=0}^x y\,f_n(y)\;\mathrm dy$$
Hacia una forma cerrada
Entonces, ¿qué fórmulas tenemos explícitamente? Os pongo algunas de estas fórmulas en mi sistema de álgebra computacional (Sage). Todas las fórmulas siguientes se supone $0\le x\le\pi$.
\begin{align*} F_1(x) &= 1 & f_1(x) &= \delta(x) \\ F_2(x) &= \frac x\pi & f_2(x) &= \frac 1\pi \\ F_3(x) &= \frac{3x^2}{4\pi^2} & f_3 &= \frac{3x}{2\pi^2} \\ F_4(x) &= \frac{x^3}{2\pi^3} & f_4 &= \frac{3x^2}{2\pi^3} \\ F_5(x) &= \frac{5x^4}{16\pi^4} & f_5 &= \frac{5x^3}{4\pi^3} \\ F_6(x) &= \frac{3x^5}{16\pi^5} & f_6 &= \frac{15x^4}{16\pi^5} \\ F_7(x) &= \frac{7x^6}{64\pi^6} & f_7 &= \frac{21x^5}{32\pi^6} \\ &\;\vdots &&\;\vdots \end{align*}
Ahora es el momento de ver un patrón aquí, para la columna de la izquierda en particular. Es fácil ver que los exponentes de $x$ $\pi$ aumentando con cada paso. Usted también puede notar que los números en el denominador tienden a ser potencias de dos. Asumiendo esto, no es difícil encontrar una regla para el resto de entero en el numerador. Usted termina para arriba con
$$F_n(x) = n\left(\frac{x}{2\pi}\right)^{n-1}\qquad f_n(x) = \frac{n(n-1)}{2\pi}\left(\frac{x}{2\pi}\right)^{n-2} = \frac{n}{2\pi}F_{n-1}(x)$$
Ahora necesitamos $F_n(\pi)$ ya que queremos saber la probabilidad de que todos los puntos de abarcar un ángulo de menos de $\pi$.
$$F_n(\pi) = n\left(\frac{\pi}{2\pi}\right)^{n-1} = 2^{1-n}n$$
Usted obtener los valores
\begin{align*} F_1(\pi)&=\frac11=1\\ F_2(\pi)&=\frac{2}{2}=1\\ F_3(\pi)&=\frac{3}{4}\\ F_4(\pi)&=\frac{4}{8}=\frac12\\ F_5(\pi)&=\frac{5}{16}\\ F_6(\pi)&=\frac{6}{32}=\frac{3}{16}\\ &\;\vdots \end{align*}
Recuerde que esta es la probabilidad de todos los puntos de la mentira en la mitad, es decir, de la convex hull no contiene el centro. Las posibilidades de que contiene el centro son, obviamente, lo contrario de eso.
$$p=1-F_n(\pi)=1-2^{1-n}n$$
Más intuitiva derivación
También hay una diferente, menos formales, pero más intuitiva para derivar esta fórmula. Si le doy una orientada a la línea por el centro, ¿cuál es la probabilidad de un punto al azar, acostado sobre el lado positivo de esa línea? Obviamente $1/2$. Si empiezo con un punto de $A_1$, y definir una línea de que a través de el centro, entonces la probabilidad de que el siguiente $n-1$ puntos acostado sobre el lado positivo de que la línea se $(1/2)^{n-1}$. Pero esto depende de la elección de una adecuada punto como el punto de partida. Si tenemos tres puntos, tenemos que comprobar si todos los puntos están en el lado positivo de la línea definida por $A_1$ o de la línea definida por $A_2$ o de la línea definida por $A_3$. En la mayoría de uno de estos puede ser el caso (porque si $A_i$ es en el lado positivo de la línea definida por $A_j$, $A_j$ tiene que estar en el lado negativo de la línea definida por $A_i$). Por lo que simplemente puede agregar probabilidades, lo que significa tres veces $(1/2)^2$ en este caso, o $n\cdot(1/2)^{n-1}=2^{1-n}n$ en general. Que es lo que se deriva de la de $F_n(\pi)$. La probabilidad de que el polígono no contiene el centro es de nuevo el complemento de esta, $1-2^{1-n}n$.
