Encuentra el tiempo esperado para llegar a un punto en el eje x desde otro punto en el eje x

Question

Te encuentras en un punto del eje x y quieres llegar a otro punto del eje x. Puedes moverte a la izquierda o a la derecha de tu posición actual y este movimiento se elige uniformemente al azar. Sin embargo, cuando está en la posición más a la izquierda o más a la derecha del eje (más a la izquierda - 0, más a la derecha - dado en el problema), sólo tiene una opción para el movimiento. ¿Cuál es el tiempo esperado (número de pasos) para moverse desde el origen hasta el destino?

Encontré este problema en SPOJ.com http://www.spoj.com/problems/AVMG1/ y su solución aquí https://docs.google.com/document/d/1yNDa7tUO9OY-hIklX8apRDdWCovqbddlofeV2CQJdBA/edit?pref=2&pli=1

Si, dejamos que $E(x)$ para ser el número de pasos esperados para llegar desde $(x,0)$ a $(n,0)$

$E(n)= 0$ , puesto que ya hemos llegado al destino.
$E(0) = 1 + E(1)$ , ya que no podemos ir detrás $0$ .
Y para otros $x$ , $E(x) = 1+(½*(E(x-1)+E(x+1)))$ .

La solución enlazada aquí dice entonces,

Escribir las ecuaciones de todos los $x$ y simplificando, obtenemos $E(x) = (2b-x)*x$ .

Así que la respuesta es $(2b-a)*(a)$ .

No entiendo que hayan simplificado esas expresiones para conseguir $E(x) = (2b-x)*x$ . Así que por favor ayúdame a entenderlo. Gracias.

Answer 1

La solución vinculada se ve mal. Si introduces el cero obtienes $E(0)=0$ es decir, implica que si se comienza en la posición cero, entonces se necesitan cero pasos para llegar al destino $n$ .

Puedes resolver las ecuaciones adivinando una solución de la forma $$E(x)=A+Bx+Cx^2.$$ Introduciendo esta conjetura en las tres ecuaciones se obtienen tres ecuaciones para las incógnitas $A$ , $B$ , $C$ . Resuelve esto y obtén $$E(x)=n^2-x^2.$$

Otro enfoque es reescribir la ecuación final en la forma $$E(x)-E(x-1) = 2 + E(x+1) - E(x),\tag1$$ sumar esto sobre todo $x=1,\ldots y$ para obtener $$E(y) - E(0) = 2y + E(y+1) - E(1),\tag2$$ que se puede reordenar en la forma $$E(y+1)-E(y)= E(1) - E(0) - 2y= -(2y+1),\tag3$$ válido para todos $y=0,\ldots n-1$ . Suma (3) sobre todos los $y=0,\ldots z-1$ para obtener $$E(z)-E(0) = -z^2.$$ Enchufe $z=n$ para deducir $E(0)=n^2$ y llegar a la misma solución.

Aparte: La solución reclamada parece ser resolver el problema de la ruina del jugador* a partir de $x$ y asumiendo que ambos $0$ y $2b$ son estados absorbentes; en su problema, $n$ es un estado absorbente y $0$ es un estado reflectante.

(*) Wikipedia sobre el problema de la ruina del jugador: "...un jugador con una cantidad finita de dinero acabará perdiendo cuando juegue una partida justa contra un banco con una cantidad infinita de dinero. El dinero del jugador realizará un paseo aleatorio... Si $a$ y $b$ son enteros positivos, entonces el número esperado de pasos hasta un paseo aleatorio simple unidimensional que comienza en $0$ primeros éxitos $b$ o $−a$ es $ab$ ."