Estimación de Monte-Carlo de la longitud media de la cuerda en un polígono

Question

Esta es una más de las "estadísticas" de la versión de mi Matemáticas.SE problema .

Pregunta Deje $\mathbf{P}$ ser un polígono convexo de $m$ lados. Elija dos de sus bordes al azar, y además elegir un punto al azar en cada uno de estos bordes, y calcular la longitud de la cuerda. Si repetimos este proceso $n$ veces y media el acorde longitudes que así obtenida, se obtiene una estimación de $\hat{\ell}_n$ de la espera que la longitud de la cuerda $\ell$$\mathbf{P}$. Entonces, ¿qué tan grande debe $n$ ser para asegurarse de que $\hat{\ell}_n$ difiere de $\ell$ (por ejemplo) a un máximo del 5%,con un nivel de confianza de (digamos) del 95%, y, precisamente, ¿cómo debemos recoger las muestras?

Tenga en cuenta que la determinación de la espera que la longitud de la cuerda analíticamente conduce a intratable integrales como se muestra en la mi SE post. También,tenga en cuenta que hay múltiples no equivalentes maneras de definir a la espera de la longitud de la cuerda de $\mathbf{P}$; el que nos necesita aquí es $\ell = \lim_{n\rightarrow \infty} \hat{\ell}_n$.

Answer 1

Esta es realmente una pregunta acerca de la integración numérica, ya que reduce de inmediato al problema de hallar la distancia media entre dos segmentos de recta en el plano.

Monte-Carlo de integración serían inútiles e ineficaces en comparación con otros métodos que están disponibles, incluyendo

1. Directo de la analítica de la integración. Esto es complicado pero se puede hacer.

2. Numérico de cuadratura. Métodos de adaptación será exacta.

3. La analítica de la integración de la media de la distancia entre un punto y un segmento de línea y numérico de la cuadratura de que la media distancia.

4. Discretos aproximaciones, tales como sumas de Riemann, la Regla Trapezoidal, etc.

Debido a que la distancia media de la función en (3) es diferenciable y varía de forma relativamente lenta, simple métodos numéricos, tales como la Regla de Simpson de trabajo. Es mejor realizar la integración numérica sobre el más corto de los dos segmentos de línea. En los experimentos en los que me parece que el uso de los extremos y el punto medio de la Regla de Simpson normalmente se le da mejor que el 1% de precisión y el uso de cinco puntos equidistantes es mucho mejor que eso. (El más duro de los casos ocurren cuando dos lados son igual de largo, paralelo, y muy juntos.) Si usted lo necesita, usted puede hacer el análisis para estimar la la Regla de Simpson de error y de forma adaptativa disminuir la separación entre los puntos.

Para el problema original, las aproximaciones a veces sobreestimar y a veces subestiman la media distancia, por lo que se podría esperar que en algunos cancelación de errores.

En cualquier caso, que sin duda conseguirá 5% de precisión utilizando el método (3). Para un $n$ de lados del polígono se requiere de $n$ cálculos (cada uno de los constantes costo) por vértice y $n-1$ cálculos por medio de un costo de $O(n^2)$. Los cálculos individuales de punto medio del segmento distancias requieren básicos de aritmética, cuatro raíces cuadradas, y dos logaritmos, por lo que son de fácil y rápido. (Mathematica calcula unos 7.500 media del segmento segmento distancias por núcleo por segundo).

Si usted quiere evitar a todos, pero el más simple aritmética, puede aproximado de cada segmento segmento integral con un doble en la Regla de Simpson de paso, uno para cada segmento (método 4). Con tres puntos de división (que requieren el cálculo de nueve distancias) que va a lograr el 5% de precisión. Con cinco puntos de división (25 de distancias) va a ser mejor que el 1% de precisión (generalmente mejor que 0,05%), excepto muy cerca de segmentos paralelos. En Mathematica, con su interpretado sobrecarga, de hecho esta técnica es sólo un medio tan rápido como método (3).

---

Este gráfico muestra (negativo) de registro (en base 10) errores relativos para 1000 segmentos distribuidos al azar cerca de la estación de una unidad de segmento (que es el más grande de los dos). E. g., un valor de 2 es un 1% de error; un valor de 6 es un 0.0001% de error. Esta es una gran prueba, porque la peor de las actuaciones se producen cuando los segmentos están cruzando o cerca de hacerlo, situaciones que son imposibles o poco probables en polígonos convexos. (Tenga en cuenta que la menor posible distancia media es de 1/4 (para un infinitesimalmente segmento corto cerca de la mitad de la unidad de segmento).)

Donde la aproximación es alta, el error es mostrado en el derecho, y donde la aproximación es baja, el error es mostrado en la izquierda. Puntos azules son los tres puntos por los tres puntos de la Regla de Simpson de cálculo (método 4) y los puntos rojos son los tres puntos de la Regla de Simpson de cálculo (método 3).

Normalmente el método 3 (rojo) tiene mucho mejor que el 2% de precisión y es mejor que el método 4 (azul), que en algunos casos tiene casi el 10% de error. Método 3 tiene una tendencia a sobrestimar ligeramente (más de sus valores a la derecha). Ambos métodos casi siempre obtener el mejor que 0,1% de precisión (una altura de 3 o más en la trama), especialmente en distancias promedio mayor que el lado más largo. Esto implica que si se desea mejorar la exactitud, centrarse en primer lugar en las inmediaciones de las aristas de un polígono convexo.

En esta parcela de 1000 segmentos, el más brillante, más grueso, más roja que tienen el mayor error relativo para el Método 3. El negro segmento es el de referencia (unidad) segmento.