You are standing on a point on the x-axis and want to reach another point on the x-axis. You are allowed to move left or right from your current position and this move is chosen uniformly at random. However, when on the leftmost or rightmost position on the axis (leftmost - 0, rightmost - given in the problem), you only have one choice for the move. What is the expected time (number of steps) to move from source to destination?
I found this problem on SPOJ.com http://www.spoj.com/problems/AVMG1/ and it's solution here https://docs.google.com/document/d/1yNDa7tUO9OY-hIklX8apRDdWCovqbddlofeV2CQJdBA/edit?pref=2&pli=1
If, we let $E(x)$ to be the expected number of steps to reach from $(x,0)$ to $(n,0)$
$E(n)= 0$, since we already reached the destination.
$E(0) = 1 + E(1)$, since we can’t go behind $0$.
And for other $x$, $E(x) = 1+(½*(E(x-1)+E(x+1)))$.
The solution linked here then says,
Writing the equations for all $x$ and simplifying, we get $E(x) = (2b-x)*x$.
So the answer is $(2b-a)*(a)$.
I don't understand they simplified those expressions to get $E(x) = (2b-x)*x$. So please help me understand it. Thanks.
The linked solution looks wrong. If you plug in zero you get $E(0)=0$, i.e., it implies that if you start at position zero, then it takes zero steps to reach the destination $n$.
You can solve the equations by guessing a solution of the form $$E(x)=A+Bx+Cx^2.$$ By plugging this guess into the three equations you obtain three equations for the unknowns $A$, $B$, $C$. Solve these and get $$E(x)=n^2-x^2.$$
Another approach is to rewrite the final equation in the form $$E(x)-E(x-1) = 2 + E(x+1) - E(x),\tag1$$ sum this over all $x=1,\ldots y$ to obtain $$E(y) - E(0) = 2y + E(y+1) - E(1),\tag2$$ which you can rearrange into the form $$E(y+1)-E(y)= E(1) - E(0) - 2y= -(2y+1),\tag3$$ valid for all $y=0,\ldots n-1$. Sum (3) over all $y=0,\ldots z-1$ to obtain $$E(z)-E(0) = -z^2.$$ Plug $z=n$ to deduce $E(0)=n^2$, and arrive at the same solution.
Aside: The claimed solution seems to be solving the Gambler's ruin problem* starting at $x$ and assuming that both $0$ and $2b$ are absorbing states; in your problem, $n$ is an absorbing state and $0$ is a reflecting state.
(*) Wikipedia on the gambler's ruin problem: "..a gambler with a finite amount of money will eventually lose when playing a fair game against a bank with an infinite amount of money. The gambler's money will perform a random walk... If $a$ and $b$ are positive integers, then the expected number of steps until a one-dimensional simple random walk starting at $0$ first hits $b$ or $−a$ is $ab$."