Representando caminos aleatorios en 2D (I)

Posted: 25/02/2013 in Java
Tags: , , , , ,

Esto va sobre estadística, fractales… y belleza. 😀

Antes que nada haré un pequeño resumen de lo que será este post así como de su organización, ya que este es un tema un tanto complejo por el contenido de otras disciplinas que involucra y que se relacionan entre si.

Este post tiene dos partes: la primera, ésta, que es donde definiré el problema a resolver, el razonamiento a seguir, y alguna consideración matemática más (algunos lo llamarán “la parte aburrida”). La segunda parte es donde echaré mano al código del programa y se verá la acción (ésta será “la parte chula”).

Como dice el título, el objetivo es, de alguna manera, representar gráficamente un fenómeno, llamado camino aleatorio, que se da cuando una partícula se mueve aleatoriamente en un espacio de N dimensiones (en nuestro caso particular, el espacio será de dos dimensiones). Esta manera será via una interfaz gráfica que proporciona el programa GridWorld, en la que inicialmente tenemos un bichito moviéndose discretamente en línea recta (mientras no haya obstáculos por su camino, como piedras u otros bichitos) por un plano dividido en cuadrículas.
A propósito, cuando digo “moviéndose discretamente” me refiero a que el movimiento se compone por un número determinado de pasos, es decir, el movimiento no se da de manera continua, no hay “fluidez”; va a saltos. Pero esto nos viene de lujo porque a la hora de demostrar (o mejor dicho, de convencernos sobre) algunas de las propiedades que exhiben los caminos aleatorios nos facilitará bastante la vida.

Obviamente tendremos que modificar el comportamiento de este bicho para que, en lugar de moverse en línea recta, se mueva de forma totalmente aleatoria. Con un número de pasos lo suficientemente grande y con la escala adecuada, veremos generado lo que se llama un fractal aleatorio. ¡Que no cunda el pánico! La traducción al castellano de todo esto está por llegar.

Finalmente añadiré que, como seguramente más de uno habrá podido sospechar, cada uno de estos pasos son decididos mediante una función de Java — Math.random() — que devuelve números aleatorios comprendidos entre el 0 y el 1 (sin llegar a éste). La idea es dividir este rango de valores en cuatro intervalos de manera que, según si el número aleatorio cae en un intervalo u otro, el bicho del programa gira cero, una, dos o tres veces 90 grados en sentido horario. Por lo tanto, si queremos que el bicho se mueva de forma aleatoria, nos interesa que los números devueltos por Math.random() sean realmente aleatorios.

Y esto nos lleva, por fin, al principio del post. Es necesario hacer una matización: los números aleatorios generados por un ordenador son pseudo-aleatorios. Vamos, que no son aleatorios. Hay que recordar que un ordenador es una máquina determinista y, como tal, no conoce el libre albedrío. En particular, no sabe generar números de forma realmente aleatoria. En su lugar utiliza funciones y parámetros tales (como los obtenidos del reloj de la CPU) que le permiten obtener números que, al menos a simple vista, aparentan ser aleatorios.

Para comprobar qué tan aleatorios son estos números generados por la máquina (o qué tan bien simulan serlo) existen los llamados tests de aleatoriedad. Hay muchos (como los especificados al final de esta página) y para diferentes propósitos. Por ejemplo, es posible que un conjunto de números supere un determinado test de aleatoriedad pero no otro.
Como decía más arriba, para asegurarme de que, al final de todo, consigo pintar un camino aleatorio, nunca está de más someter a alguna que otra prueba funciones como Math.random().

Tengo que confesar que la Estadística nunca ha sido mi fuerte, así que para convencerme de que puedo confiar en esta función he optado por un método estadístico algo más rudimentario, como es el de comprobar que, llamando Math.random() un número grande de veces, puedo obtener algo que se parezca a una distribución de Gauss. El razonamiento es el siguiente:

En cualquier ciencia experimental, una manera de acotar los errores aleatorios que surgen de la medición de una determinada magnitud consiste en repetir dicho experimento (es decir, dicha medición) un número muy grande de veces. Cuantas más veces se repita la medición, más probabilidades hay de acercarse al valor real de la magnitud que pretendemos medir (aunque nunca se alcanza de manera exacta).
Pensemos en el siguiente ejemplo: tenemos un dardo e intentamos lanzarlo a una diana (que huelga decir que está justo en el centro del tablero). Fallamos. Demasiado alto. Ahora tiramos dos dardos más. Volvemos a fallar: uno se ha desviado demasiado a la derecha y el otro ha ido más abajo. Ahora tiramos 20.000 dardos. ¿Os imagináis cómo queda el tablero después de 20.000 tiros? Sí, agujereado por todos los puntos.
Si dividiéramos el tablero en regiones del mismo tamaño, contaríamos aproximadamente el mismo número de puntos en cada una de ellas, ya que, libres de influencias externas (por ejemplo, que los dardos estén manipulados) la probabilidad de fallar tanto “por arriba” como “por abajo” es la misma, por lo que, conforme se va incrementando el número de veces que lo intentamos, el centro geométrico de todos estos tiros se aproxima (que no que coincide) a… ¡la diana! Justamente el centro geométrico del tablero.

En el caso del ejemplo obtenemos una distribución de Gauss, es decir, una función que tiene esta forma:

normal1

El eje horizontal representa el valor de nuestras mediciones (en el ejemplo podrían ser las coordenadas, con el origen (0,0) situado en la diana, de cada agujero que hemos hecho en el tablero), y el eje vertizal la probabilidad con que podemos obtener esos valores. En la imagen \mu representa la media de todos los valores que hemos obtenido y \sigma la varianza. Una de las propiedades más llamativas de la distribución de Gauss es que, independientemente de los valores de las mediciones, el 68% de éstas tienden a estar dentro del intervalo [\mu - \sigma, \mu + \sigma], coincidiendo el valor más probable precisamente con \mu , la media aritmética.

He utilizado esta segunda idea para comprobar que los números aleatorios generados por Math.random() (que recordemos que devuelve números naturales más pequeños que 1) forman algo parecido a una distribución normal. Y digo “algo parecido” porque el hecho de que la media aritmética de todos los números coincida justamente con la media de los dos extremos (que sería el equivalente a la diana de nuestro tablero), 0.5, no significa realmente nada, ya que además necesitaríamos comprobar que el 68% de los valores obtenidos caen dentro de [\mu - \sigma, \mu + \sigma], pero como el fin último de este post no es la estadística y tampoco se trata de aburrir (en exceso) al personal, vamos a hacer un acto de fe y vamos a asumir que la distribución obtenida de invocar muchas veces Math.random() se ajusta a la de la campana de Gauss.

Alguien podría quejarse diciendo que eso es mucho asumir, ya que podría ser que Math.random() devolviera todo el rato valores como 0.4, 0.6, 0.6, 0.4, 0.6… y la media de todo eso nos saldría muy cercana a 0.5, y es verdad, así que aquí está la prueba visual de que, al menos en un primer momento, podemos confiar en Math.random():

Click para ampliar

Click para ampliar

Ahora vamos a comprobar si la media de un conjunto de valores lo suficientemente grande, pongamos de 100.000.000 valores, se aproxima a 0.5:

Click para ampliar

Click para ampliar

(El código que hace esto lo he subido aquí.)

La primera media nos da 0.499993… y la segunda 0.50001… Tiene buena pinta. Podemos seguir adelante.
Por aburrido y doloroso que haya sido esto, era necesario para asegurarnos de que al final, utilizando esta función de Java, podemos simular un movimiento realmente aleatorio y de que, en consecuencia, los patrones que vamos viendo a grandes escalas resulten todavía ¡más increíbles! 🙂

Pero… ¿qué es un fractal y qué tiene que ver con todo esto? Aunque el tema por si mismo merece un post aparte, haré un esbozo de lo que son estas entidades matemáticas. Fractal proviene de la palabra latina fractus, que significa roto o fracturado. Esto es debido a que los fractales son objetos que no tienen dimensión entera, sino dimensión fraccionaria (de hecho, la primera definición formal que se dio para este tipo de objetos ya involucraba explícitamente el concepto de dimensión).
Una de las primeras definiciones más típicas (y amigables) que se da sobre ellos viene a ser así: un fractal es una forma geométrica que puede ser subdividada en partes, siendo cada una de ellas una copia (o una réplica muy parecida) a escala reducida del fractal entero. Esta propiedad es conocida como autosimilitud, y es la que también aparece a grandes escalas en los caminos aleatorios.

Como dicen que una imagen vale más que mil palabras, aquí podéis trastear con uno de los fractales más conocidos que hay: el conjunto de Mandelbrot. Podéis ir acercando el zoom a cada una de sus “ramas”, por ejemplo, para ver en qué consiste exactamente esto de la autosimilitud.
Un último apunte sobre los fractales. Aunque los fractales más conocidos son los descritos mediante funciones matemáticas iteradas sobre ellas mismas infinitas veces (idealmente), no hay que verlos como unos objetos exóticos que nada tienen que ver con la realidad. Véase por ejemplo el problema de cuánto mide la costa de Gran Bretaña.

Dicho esto, vámonos ya a la segunda parte. 🙂

Advertisements
Comments
  1. […] ← Representando caminos aleatorios en 2D (I) […]

    • Roxana Ugaz says:

      Hola
      yo estoy interezada en aprender mas hacerca de programacion en visul basic para caminos aleatorios, es muy interesante y un tema que quiero analizar en mi carrera de ingenieria civil
      podrias orientarme con mas bibliografia o incluso sugerirme algun programa que haga ya este tipo de analisis?
      Saludos
      Roxana

  2. Roxana Ugaz says:

    Daniel otra pregunta,
    Un consejo para una persona que se quiere iniciar en programacion con Visul Basic. Donde debe de empezar, que curso o bibliografia deberia de utilizar.
    Seriamos dos personas o incluso tres personas que estariamos interesadas en aprender este tema, pero hay una caracteristica, no somos chicos, chicos que recien terminamos la carrera, asi que tenemos conocimientos, pero queremos aprender el lenguaje de programacion para orientarlo en la carrera que tenemos. Alguna sugerencia, o alguien para esta tarea? tiene que ser en ingles por que la mayoria solo habla ingles….
    Saludos
    Roxana

    • Hola Roxana,

      Me alegro mucho de serte de ayuda. Antes de responder a tus preguntas, me gustaría preguntarte por qué quieres iniciarte con Visual Basic. ¿Hay algún requerimiento de tu investigación que te obligue a trabajar expresamente con este lenguaje? Te lo pregunto porque si quieres orientar un lenguaje de programación a la carrera que tienes, esto es, utilizarlo para realizar cálculos numéricos o para procesar grandes volúmenes de datos, existen mejores lenguajes de programación para aprender y utilizar.
      Uno de los problemas de Visual Basic es que necesita utilizar plataformas muy pesadas como .NET para compilar y depurar los programas, aparte de que es propietario (con los problemas a largo plazo que ello conlleva) y, para rematar, ni siquiera está concebido para este tipo de tareas (es un lenguaje de programación orientado a eventos).

      Si me permites aconsejarte, te recomendaría que empieces con un lenguaje como Python (http://es.wikipedia.org/wiki/Python), que además de ser enseñarte mejores prácticas de programación que VB, trae muchas librerías independientes destinadas a la comunidad científica y matemática, como por ejemplo SciPy (http://www.scipy.org/). También está Matlab (http://www.mathworks.es/products/matlab/), que probablemente conocerás, y que es un lenguaje ampliamente utilizado por matemáticos e ingenieros.
      También puedes aprender C (http://es.wikipedia.org/wiki/C_(lenguaje_de_programaci%C3%B3n)), que, al igual que Python, es un lenguaje de propósito general y muy adaptable a todos los campos. C es, con diferencia, uno de los lenguajes más poderosos y eficientes que existen, pero programar en éste también es más laborioso y no suele ser fácil de aprender como primer lenguaje de programación, sobre todo porque te obliga a cuidar detalles que, en principio, a un programador novato (y no tan novato) no le interesan realmente, como puede ser el acceso y el manejo dinámico de la memoria de forma manual. Pero a pesar de no ser un lenguaje demasiado “simpático” para quien se inicia, es un lenguaje excelente y que, en mi opinión personal, todo buen programador debería de haber aprendido en algún momento de su vida.

      Dicho esto, si quieres (o debes) seguir con Visual Basic, puedes empezar descargándote el Visual Studio Express (http://www.visualstudio.com/en-us/products/visual-studio-express-vs.aspx), que es un entorno de desarrollo gratuito y más liviano que su análogo de pago, aunque no tan completo. Si tienes dinero (y un ordenador potente también) puedes instalarte Visual Studio 2013 (http://www.visualstudio.com/), que ya lo trae todo.

      Aunque es cierto eso que dices de que la mayor parte de documentación está en inglés, hay libros y tutoriales medianamente buenos que están escritos en español. Éste es el mejor que he podido encontrar:

      http://www.desarrolloweb.com/manuales/48/

      Microsoft también ofrece la documentación oficial en español (aunque la guía anterior me ha parecido más amigable y menos áspera):

      http://msdn.microsoft.com/es-es/library/y4wf33f0.aspx

      Y aquí tienes el foro oficial de dudas (también en español) para desarrolladores de Visual Basic, por si tienes algún problema y necesitas ayuda:

      http://social.msdn.microsoft.com/Forums/es-ES/home?forum=vbes

      Esto es todo por ahora. No entiendo nada sobre lo que estás investigando, pero lo que me has explicado sobre la geometría de los depósitos de relaves me ha sonado a que es un tema muy interesante, así que te deseo mucho éxito en tu investigación y que ojalá puedas obtener los resultados más satisfactorios posibles 🙂

      Si necesitas algo más, estaré contento de poder ayudarte. Ya sabes donde encontrarme 🙂

      Un saludo.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s