[Math] 1D Random Walk, with different step sizes in each direction.

probabilitystochastic-processes

A walker starts at a defined position greater than $0$, say $A$, and then makes a "decision" to walk either "$b$ steps to the right" or walk "$c$ steps to the left." He will choose the first option with probability $p$, and the second option with probability $1-p$. If the walker gets to position $0$ he stops.

I wish to calculate:

  • the expectation value of the walker's position after a total of n decisions.
  • what happens as n approaches infinite?

Is there an existing formula/theory that can be used to get an analytic solution to this problem?

Best Answer

This is a classic stopping time problem where you can define a martingale on the process and use the optional sampling theorem 1 to calculate things like the expectation of the process at step n, the expected number of steps its going to reach 0, and so on.

To give you an idea, you can think of the process as $X_{n+1}=X_n+V_n$ where $X_n$ is the position in the real line at time n, and of course $X_0=A$. $X_n$ then depends on the previous position on the real line and a random component $V_n\in\{b,-c\}$, i.i.d with $P(V_n=b)=p$ and $P(v_n=-c)=1-p$. Then it is a matter of finding a suitable martingale and to show that $T=inf\{n\in\mathbb{N}:X_n=0\}$ is a bounded stopping time (here can be tricky because you have to be able to show that there's actually a finite way of achieving 0 from the initial position A by combining b and -c. For example, if A=1, b=2 and c=-2, there is no way you will ever reach 0). If you cannot show that T is not bounded or at least that has finite expectation (or any other condition that makes Dominated Convergence Theorem/Monotone Convergence Theorem work), you might not be able to easily calculate the expectation for example of the number of steps needed to reach 0 using the OST1.

I hope this helps.