Paseo aleatorio 1D-probabilidad de volver al origen

Question

Supongamos que hay un paseo aleatorio que comienza en el origen mientras que la probabilidad de moverse a la derecha es 1/3 y la probabilidad de moverse a la izquierda 2/3.¿Cuál es la probabilidad de volver al origen.

Gracias

Answer 1

Dejemos que $P_{i\ge 0}$ sea la probabilidad de alcanzar alguna vez la posición $x+i$ cuando se parte de la posición $x$ (esto es independiente de $x$ ya que las probabilidades de transición son). Es evidente que $P_0=1$ y $P_i\rightarrow 0$ como $i\rightarrow\infty$ siempre que la probabilidad de salto a la derecha $q < 1/2$ (en este caso $q = 1/3$ ). Por lo demás, $$ P_i = qP_{i-1} + (1-q)P_{i+1}, $$ Se puede adivinar que la solución es de la forma $P_i = \alpha^i$ para algunos $0 < \alpha < 1$ . Esto resulta satisfacer las condiciones si $$ \alpha = q + (1-q) \alpha^2, $$ que tiene la solución $\alpha = q/(1-q)$ en este caso.

Para el problema especificado, se quiere saber la probabilidad total de volver al origen después del primer paso. Si el primer paso es hacia la derecha (lo que ocurre con probabilidad $q$ ), entonces debe volver al origen; si es a la izquierda (con probabilidad $1-q$ ), entonces volverá al origen con probabilidad $P_1 = \alpha = q/(1-q)$ . Así que la solución es $$ P_{\text{return}} = q + (1-q)\alpha = q + (1-q)\frac{q}{1-q} = 2q $$ en general $q<1/2$ y $P_{\text{return}} = 2/3$ en este caso.

Answer 2

El problema al que te refieres es el estudio de la probabilidad de retorno de un paseo aleatorio sobre un entramado. En tu caso, el entramado es el entramado 1-D de números enteros. Este problema está muy bien estudiado en celosías generales. Un famoso teorema de Polya dice que mientras la probabilidad de retorno es $1$ para paseos aleatorios simétricos (es decir, todos los movimientos tienen la misma probabilidad, a diferencia de esta pregunta) en $1$ y $2$ de dimensión, es estrictamente menor que $1$ en todas las dimensiones superiores. Véase aquí para más detalles.

La solución publicada por mjqxxxx es muy inteligente y es perfectamente válida. Si te interesan otras soluciones, una forma muy sistemática de estudiar este problema es mediante el uso de funciones generadoras. Véase este Notas de la conferencia para más información (De hecho, estas notas tienen la solución al problema que has planteado).

Answer 3

Puede encontrar una respuesta detallada a su pregunta en WolframMathWorld .

Para dar una respuesta exacta, debes definir el número de pasos que te interesa para volver al origen. Por supuesto, el número de pasos debe ser par.

He hecho una pequeña "simulación" (más bien: prueba de funcionamiento) en R :

results <- NULL
for (i in 1:50) {
    N=i*2
    n1=N/2
    p=1/3
    q=1-p
    results <- c(results, ((factorial(N)/(factorial(n1)*factorial(N-n1)))*(p^n1)*(q^(N-n1))))
}

Y obtuve los siguientes resultados (perdón por la fea tabla):

  N| probability
---+--------------
  1 0.4444444444
  2 0.2962962963
  3 0.2194787380
  4 0.1707056851
  5 0.1365645481
  6 0.1112748170
  7 0.0918458807
  8 0.0765382339
  9 0.0642543198
 10 0.0542592034
 11 0.0460381120
 12 0.0392176509
 13 0.0335193598
 14 0.0287308798
 15 0.0246872745
 16 0.0212584864
 17 0.0183406549
 18 0.0158499487
 19 0.0137180842
 20 0.0118890063
 21 0.0103163865
 22 0.0089617094
 23 0.0077927908
 24 0.0067826142
 25 0.0059084106
 26 0.0051509221
 27 0.0044938086
 28 0.0039231662
 29 0.0034271337
 30 0.0029955687
 31 0.0026197805
 32 0.0022923080
 33 0.0020067342
 34 0.0017575319
 35 0.0015399328
 36 0.0013498176
 37 0.0011836238
 38 0.0010382665
 39 0.0009110715
 40 0.0007997183
 41 0.0007021917
 42 0.0006167398
 43 0.0005418386
 44 0.0004761612
 45 0.0004185515
 46 0.0003680018
 47 0.0003236328
 48 0.0002846770
 49 0.0002504641
 50 0.0002204084

Como puedes ver aquí, he calculado las probabilidades de volver al punto original para todos los pasos posibles (N), donde N<=100. Eso se hace calculando la probabilidad para todos los N pares, donde el número de pasos a la derecha es igual al número de pasos a la izquierda con la siguiente fórmula: $$P(n_{1}|N)=\frac{N!}{n_{1}!^2}p^{n_{1}}(1-p)^{n_{1}}$$

donde N es el número de pasos, $n_{1}=\frac{N}{2}$ y $p=\frac{1}{3}$ .

Nota: la suma de todo lo anterior es 1,998366. Es superior a 1, ya que la probabilidad de llegar de nuevo al punto original también podría incluir una probabilidad de N inferior.

Eso es todo lo que he podido hacer, me gusta jugar con las simulaciones, pero no se me dan bien las cadenas de Markov extrapoladas al infinito :)