El problema de los cuatro puntos

En esta entrada se plantea un problema de probabilidad complicado de resolver analíticamente pero cuya solución puede aproximarse fácilmente por métodos de Montecarlo (simulación).

En 1864, Sylvester propuso la primera versión de un problema de geometría estocástica que se conoce con el nombre de problema de los cuatro puntos:

Al seleccionar cuatro puntos aleatoriamente en el plano, demostrar que vale 1/4 la probabilidad de que el conjunto convexo más pequeño que los contiene (su cierre convexo) sea un triángulo.

Un ejemplo de situación en la que ocurre el suceso cuya probabilidad queremos calcular es el siguiente:ejemplosylvesterPor el contrario, si el punto negro no perteneciera al triángulo definido por los tres puntos rojos no habría ocurrido el suceso en el que estamos interesados ya que el cierre convexo sería un cuadrilátero.

Tal y como lo planteó Sylvester el problema es ambiguo mientras no se dé un significado preciso a la frase seleccionar cuatro puntos aleatoriamente en el plano. Esto explica que diferentes autores obtuvieran diferentes probabilidades, y diferentes a 1/4, en función del significado que atribuían a esa frase. Esto es lo que ocurre también en la más conocida paradoja de Bertrand.

Posteriormente se planteó el problema de forma completamente precisa: sea S\subset \mathbb{R}^2 un cuerpo convexo (es decir, un conjunto convexo y compacto con interior no vacío). Si se seleccionan cuatro puntos aleatoria y uniformemente sobre S, ¿cuál es la probabilidad p(S) de que el cierre convexo de los cuatro puntos sea un triángulo?

La solución depende de S y se puede demostrar que \frac{35}{12\pi^2} \leq p(S)\leq \frac{1}{3} para cualquier S, con lo que la probabilidad siempre está entre 0.29 y 0.33 más o menos.

Una solución aproximada mediante simulación  

A continuación vamos a aproximar la solución del problema para cuatro puntos seleccionados en el cuadrado unidad S=[0,1]^2 mediante una pequeña simulación. La siguiente función de R genera cuatro puntos en el cuadrado unidad y devuelve TRUE o FALSE en función de si el cierre convexo es un triángulo o no, y este experimento se lleva a cabo B veces.

sylvester.cuadrado = function(B){
replicate(B, length(chull(cbind(runif(4), runif(4)))) == 3)
}

La obtención del cierre convexo con R mediante el comando chull  (así como la aplicación del cierre convexo en ecología) la hemos tratado en una entrada anterior del blog.

Hemos usado la función anterior para seleccionar (10000 veces) 4 puntos en el cuadrado unidad. Posteriormente calculamos la proporción de veces en las que el cierre convexo resultó ser un triángulo:

# Ejemplo
set.seed(100) # para reproducir los resultados
B = 10000
resultado = sylvester.cuadrado(B)
sum(resultado) / B

En el ejemplo anterior, a partir de 10000 realizaciones obtenemos la aproximación p(S)\approx 0.302. En 1867, Woolhouse probó que el valor exacto para S=[0,1]^2 es p(S)=11/35\approx 0.3056. Puede comprobarse que si T es una transformación afín no singular, entonces p(T(S))=p(S). Por lo tanto, la probabilidad para cualquier rectángulo es también 11/35.

Ejercicio: escribir una función de R similar a la anterior para aproximar el valor de p(S) cuando S es un círculo (o elipse) y cuando S es un triángulo. Comprobar que, aparentemente, la probabilidad para un círculo es menor que para un cuadrado, y ésta es menor que para un triángulo.

El problema variacional 

Algo más tarde, en 1885, Sylvester se interesó por el problema de qué forma debería tener S para que p(S) alcanzara su valor máximo y su valor mínimo. Conjeturó que el valor mínimo se alcanza para el círculo y el máximo para el triángulo. Una prueba rigurosa de esta conjetura no se obtuvo hasta 1917 y se debe a Blaschke.

Los resultados mencionados en esta nota han sido tomados de Pfiefer (1989). Allí se puede encontrar que los valores exactos de p(S) para el triángulo y el círculo son, respectivamente, 1/3 y 35/(12\pi^2), valores que permitirán comprobar si la solución del ejercicio propuesto más arriba es correcta y que, junto con la solución del problema variacional, justifican las cotas para p(S) que mencionamos más arriba. También se pueden encontrar las principales ideas involucradas en las demostraciones de los resultados.

Referencia

Pfiefer, R.E. (1989). The historical development of JJ Sylvester’s four point problem. Mathematics Magazine, 309–317.

Anuncios
Esta entrada fue publicada en probabilidad, R y etiquetada , , . Guarda el enlace permanente.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s