Tenemos una caminata aleatoria que comienza en el estado . En cada paso, se lanza una moneda con probabilidad de cara: . Si obtenemos cara, pasamos al siguiente estado entero más alto y si sale cruz, pasamos al siguiente estado entero más bajo (entonces el estado iría a en cabezas y en las colas).
Ahora, quiero saber la probabilidad de que lleguemos al estado por primera vez después de exactamente lanzamientos de la moneda. Resultó ser sorprendentemente difícil para mí.
Aquí está mi intento:
yo defino como la probabilidad descrita anteriormente y como la probabilidad de que el paseo aleatorio esté en el estado en el lanzamiento (independientemente de si estaba allí en un lanzamiento anterior).
Está claro que necesitamos colas y cabezas Así que si ni siquiera es, las secuencias para aquellos se ha convertido .
Llegar , necesitamos identificar todas las secuencias en las que el número acumulado de cabezas sea inferior a + el número acumulativo de cruces en todos los lanzamientos previos a . Esto no es tan fácil de resolver.
Por otro lado, obtuve una expresión para y esperaba poder usarlo para obtener . Razoné que la probabilidad de que la caminata alcance por primera vez en lanzamiento es la probabilidad de que esté en el estado en lanzamiento restado por las probabilidades de que estaba en el estado en cualquier lanzamiento anterior. Entonces,
Pero esto no puede ser correcto ya que esta expresión se volverá negativa para muchos valores de .
Después de algunas investigaciones, parece ser el caso de que hay
Podemos probar nuestra fórmula para por inducción Para la respuesta es obviamente , que coincide con la fórmula dada. Para la respuesta es obviamente , que también coincide con la fórmula dada. Para y tenemos dos opciones para el primer movimiento: derecha o izquierda. Si vamos a la izquierda, hay opciones, y si vamos a la derecha hay opciones Por lo tanto, en total tenemos
Es cierto que, aunque esto resuelve el problema, no es una buena solución. Encontré la fórmula simplemente experimentando durante media hora, y la prueba es muy algebraica y no muy agradable de ver. Si a alguien se le ocurre una prueba combinatoria, ¡sería mucho mejor! Sin duda voy a pensar en ello ahora.
Una función generadora
Sea el número de formas de llegar a la posición por primera vez en el paso ser . El número de caminatas unilaterales de longitud es , con función generadora . Para llegar primero a la posición en paso , podemos contar el número de formas de llegar primero a la posición en pasos por el número de caminatas unilaterales de longitud y suma para todos . Eso es,
Una forma cerrada
Para derivar una forma cerrada de , primero consideramos la serie
Esta respuesta es una extensión de la de @SmileyCraft. Como dice en su respuesta, sería bueno tener una prueba combinatoria. Podría haber encontrado uno. El problema parece similar en espíritu al que tiene una cuadrícula cuadrada, comienza en la esquina inferior izquierda y necesita llegar a la esquina superior derecha y encontrar la cantidad de caminos donde no cruza la diagonal principal de la cuadrícula (está bien tocarlo). En ese caso, el número de dichos caminos son los números catalanes.
Ahora, siguiendo el ejemplo de esto, la fórmula que @SmileyCraft tiene arriba también se puede escribir como:
Ahora, el problema aquí es que la caminata aleatoria no cruza se puede convertir en un problema de rejilla. Básicamente tenemos (según la convención de @SmileyCraft) colas y cabezas y es necesario colocarlas de tal manera que nunca crucen el . Esto es completamente equivalente a decir que iremos a la derecha si sale cruz y subiremos si sale cara en una cuadrícula que tiene filas y columnas
Otra forma de ver esto es graficar en el eje x el número de lanzamiento y en el eje y la puntuación de la caminata aleatoria. Ahora, imagina cualquier camino que vaya desde a . Ahora, simplemente gire la imagen completa 45 grados y obtendrá la cuadrícula.
Así que la fórmula para anterior es simplemente el número de formas de ir desde la parte inferior izquierda a la parte superior derecha de una cuadrícula con filas y columnas de tal manera que el camino nunca cruce la línea .
Pero, ¿cómo demostramos que es equivalente a la ecuación (1) anterior? Hice trampa y usé el mismo razonamiento que la respuesta de @Marcus M aquí . Dice así:
Sabemos que las rutas totales en nuestra cuadrícula son . Los buenos caminos son los que nunca cruzan la línea . Entonces,
# buenos caminos = # caminos - # malos caminos
Ahora, cualquier mal camino cruza la línea . Entonces, debe tocar la línea. (la diagonal justo encima).
Divida cualquier ruta de este tipo en dos partes. La porción desde el origen hasta cuando toca el línea y la porción después de eso. La primera parte se puede reflexionar sobre el . Y esto lleva a una biyección a un camino desde a . Por lo tanto, los malos caminos se pueden asignar a caminos desde la parte inferior izquierda hasta la parte superior derecha de otra cuadrícula cuya altura es . Pero no cambiamos la longitud total de la ruta, por lo que la longitud total de las rutas incorrectas sigue siendo . Por lo tanto, el número de malos caminos es .
Poniendo todo esto junto, obtenemos la ecuación (1) anterior. La siguiente imagen muestra esto para y .
Supongo que puedo resolver este problema de una manera menos combinatoria.
Para facilitar la comprensión, solo daré un bosquejo de la demostración.
Algunas abreviaturas:
- SRW = Paseo aleatorio simple
- [L/R]HS = [izquierda/derecha] lado de la mano
- iid = independientes e idénticamente distribuidos
- # = número
Primero necesito presentar el Principio de reflexión para SRW .
Considere SRW: y . son variables aleatorias iid.
Denotar es la posición más lejana que podemos alcanzar en pasos (más formalmente, ). Entonces
Esto es intuitivo:
Entonces podemos resolver fácilmente este problema.
Como solo es posible cuando y tienen la misma rareza, y , podemos denotar .
Podemos usar 2 casos simples para probar este resultado:
Carátula Caratula de SmileyCraft
Rohit Pandey
Mike Earnest
Rohit Pandey
Mike Earnest