sábado, 9 de abril de 2011

Una hormiga amenazada

Enunciado

Cuando hay que recorrer un laberinto, y la probabilidad de ir desde una cámara a otras se mantiene a lo largo del tiempo, hay una forma muy simple de calcular la probabilidad de acabar en una u otra salida, que se puede usar en cualquier tipo de laberinto.

Para empezar, las salidas se consideran las únicas posiciones estables (en este caso, la única salida es la muerte de la hormiga), y por pequeña que sea la probabilidad de llegar a ellas, la probabilidad de seguir en el laberinto queda multiplicada en cada unidad de tiempo por un factor, de forma que la probabilidad de no seguir en el laberinto y alcanzar una de las salidas crece de forma exponencial, es decir, que la probabilidad de no alcanzar nunca ninguna salida es 0.

En nuestro caso, la probabilidad de alcanzar alguno de los vértices "envenenados", por tanto, es 1.

El método para calcular la probabilidad de acabar en alguna de las soluciones, se plantea de la siguiente forma. Se usan tantas variables como nodos hay en el laberinto multiplicado por las salidas (si hay 6 nodos y 2 salidas, se usan 12 variables). Cada una de esas variables representa la probabilidad de acabar en una de las salidas partiendo de uno de los nodos. Después, para cada uno de los valores, se calcula dónde va a estar en el siguiente paso y con qué probabilidad. La probabilidad de llegar a la salida indicada desde ese inicio será igual a la suma de las probabilidades de llegar a la salida indicada desde el siguiente lugar, multiplicada por la probabilidad de llegar a él. El resultado, es un sistema de tantas incógnitas como hayamos usado y tantas ecuaciones como incógnitas. Seguro que será determinado, debido a un resultado de probabilidad.

En nuestro caso se pueden usar menos variables, ya que sólo hay dos tipos de casilla (según su posición respecto a los vértices envenenados). Unos, son los unidos con los envenenados (3, 4, 5 y 6) y otros, los que no (1, 2).

La probabilidad de llegar a 7 empezando desde 1, por ejemplo, la vamos a representar por x. La de llegar a 8 empezando desde 1, será 1 - x (ya que sólo hay dos salidas). Por simetría, la de llegar a 8 desde 2 será x y a 7 desde 2 será 1 - x.

La probabilidad de llegar a 7 desde 3 o 6, o de llegar a 8 desde 4 o 5 será y. La probabilidad de llegar a 8 desde 3 o 6, o de llegar a 7 desde 4 o 5 será 1 - y.

Si nos situamos en el punto 1, con probabilidad 1/3 la hormiga pasa a 2, 5 o 4, de donde tenemos la igualdad x = (1 - x)/3 + (1 - y)/3 + (1 - y)/3. Quitando denominadores y simplificando, 4x + 2y = 3.

Por otra parte, si nos situamos en un 5, por ejemplo, tenemos que pasa con probabilidad 1/3 a 8, 6 o 1, por lo que y = 1/3 + (1-y)/3 + (1-x)/3. De nuevo, quitando denominadores, 4y + x = 3. Tenemos dos ecuaciones, despejamos 2y en la primera, teniendo 2y = 3 - 4x, de donde 6 - 8x + x = 3, es decir que 7x = 3, por lo que x = 3/7.

Por tanto la respuesta a la segunda pregunta es que, partiendo del vértice 1, la probabilidad de morir en el 7 es 3/7 y la de morir en el 8 es 4/7.

También es posible simular mediante una sencilla hoja de cálculo el laberinto en cuestión y obtener un resultado de forma empírica.