Volver al origen

mayo 18, 2007

Carlos vive en una ciudad infinita, en la que las calles son numeradas y a su vez los números de las calles horizontales coinciden con los de las calles verticales (o sea, existe la esquina 3 horizontal y 3 vertical). Carlos vive en la esquina de 0 y 0. Un día Carlos decide ir a caminar, y al salir de su casa repite infinitamente estos pasos:

1)Elige en qué dirección caminar

2)Camina una cuadra en esa dirección

 Cada vez que llega a una esquina hace lo mismo. Carlos puede seguir derecho una cuadra más, volver una cuadra para atrás, o doblar a la derecha o izquierda y hacer una cuadra en alguna de esas dos direcciones.

 Carlos no tiene preferencia por ninguna esquina ni ningún recorrido en particular. Demostrar que la probabilidad de que Carlos vuelva a su casa es 1.

(lo escribí de esta manera y le puse el nombre Carlos apropósito para hacer honor al informalismo pero la idea que creo que todos la entienden pero por las dudas la digo de nuevo si la quieren más formal es demostrar que si vamos sumando alguno de los vectores (0,1); (1,0); (0,-1); (-1,0) infinitamente la probabilidad de que alguna de las sumas parciales sea 0 es 1)

7 comentarios to “Volver al origen”

  1. severius said

    Severius dice:

    Esto anda para números positivos en general:

    Lema: Si hacemos un camino aleatorio en el plano (un tipo está parado en el origen y en cada paso elige ir a uno de los puntos vecinos con probabilidad ${1 \over 4}$ cada uno) entonces la probabilidad de que pase por un punto $P$ cualquiera es 1.

    Demostración: en vez de mirar la probabilidad, vamos a mirar la cantidad esperada de veces que el tipo va a pasar por $P$. Es claro que si la probabilidad de pasar por $P$ fuera $p

  2. severius said

    No sé por qué el comment quedó cortado al medio, así que voy a intentar de nuevo.

    Esto anda para números positivos en general:

    Lema: Si hacemos un camino aleatorio en el plano (un tipo está parado en el origen y en cada paso elige ir a uno de los puntos vecinos con probabilidad ${1 \over 4}$ cada uno) entonces la probabilidad de que pase por un punto $P$ cualquiera es 1.

    Demostración: en vez de mirar la probabilidad, vamos a mirar la cantidad esperada de veces que el tipo va a pasar por $P$. Es claro que si la probabilidad de pasar por $P$ fuera $p

  3. unimbecil said

    severius, tu mensaje quedo cortado de nuevo.

    Problema interesante: Que pasa si la ciudad de Carlos es tridimensional? (o sea que ahora existe tambien la posibilidad de moverse 1 cuadra hacia arriba/abajo en cada paso).

    La respuesta no es facil.

  4. ltaravilse said

    Pablo Amster dijo que si la ciudad de Carlos tenía infinitos pisos con infinitos subsuelos y la mamá de Carlos se quedaba en la puerta de su casa esperandolo a que vuelva podía esperar tranquila que Carlos no iba a volver… O sea la probabilidad es 0

  5. unimbecil said

    No, no es cero, pero tampoco es 1.

  6. charlydif said

    Aca va una demostracion del que paseo aleatorio vuelve al origen con probabilidad 1, es lo mismo que hizo Severius pero en los terminos en los que alguna vez lo pensamos (funciones generatrices y etc..). Es mas divertido entender combinatoriamente las cuentas que siguen pero es mas facil escribirlo asi.

    Sea a_k la cantidad de caminos de k pasos que empiezan y terminan en el origen. Y sea b_k la cantidad de caminos de largo k que empiezan y terminan en el origen pero en ningun paso intermedio pasaron por él. Pongamos ademas a_0=1 y b_0=0. No es dificil ver quepara n\geq 1

    a_n=a_0b_n+a_1b_{n-1}+\ldots+a_{n-1}b_1+a_nb_0

    (recordar que b_0=0). Luego si ponemos

    A(z)=a_0+a_1z+a_2z^2+\ldots+a_nz^n+\ldots
    B(z)=b_0+b_1z+b_2z^2+\ldots+b_nz^n+\ldots

    Entonces A(z)B(z)=A(z)-1 de donde:

    A(z)={1\over 1-B(z)}.

    1) Si miramos A({1\over 4}) con cariño vemos que es la cantidad esperada de veces que un camino pasa por el origen pues el n-esimo termino de la serie es la cantidad esperada de veces que un camino pasa por el origen en el paso n.

    2) Ahora, la probabilidad de volver al origen en el paso k (por primera vez) es {b_k\over 4^k} luego la probabilidad de volver al origen es B({1\over 4}).

    Juntando todo podemos concluir que:

    “El paseo aleatorio es recurrente (vuelve al origen con probabilidad 1) si y solo si la cantidad esperada de veces que pasamos por el origen es infinita. Mas aun, si la probabilidad de volver al origen es B y la cantidad esperada de veces que un camino aleatorio pasa por el origen es A entonces A={1\over 1-B}.”

    Es un lindo problema ver que a_{2k}={2k\choose k}^2 y a_{2k+1}=0. Calculos aburridos muestran que A({1\over 4}) diverge de donde B({1\over 4})=1 que es lo que queriamos.

  7. charlydif said

    1) Los calculos aburridos son: La formula de Stirling es que

    \lim {n!\over n^ne^{-n}\sqrt{4n\pi}}=1

    De donde existe n_0 tal que para todo n\geq n_0

    {2n\choose n}^2{1\over 4}^{2n}>{1\over 2}{1\over n\pi}

    De donde la serie diverge.

    2) Lo anterior parece dar un plan para calcular la probabilidad de volver al origen en dimension 3, sin embargo no logre calcular los a_k (correspondientes a dimension 3), lo unico que se es que a_k<{2n\choose n}^3 lo que ni siqueira me alcanza para probar que la serie en cuestion converge.

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

A %d blogueros les gusta esto: