Expectation of constraint random walk

Question

Problem description

I am currently dealing with a practical problem that can be simplified to something like this:

• I start by setting a value to 0
• Every minute, I try to increase or decrease 1 or decrease this value by 1.
• My value cannot be negative, so if my value is 0 and I try to decrease it, nothing happens.

I believe this is called a constraint random walk, and hereby present my question:

I want to know what the expectation of my value is if I keep walking like this forever.

Any solution will do, but a simple intuitive approach would of course be preferred.

---

Progress so far

I have already established that the expectation of the value increases as time progresses by this logic: If your value at time t is Vt, then, at any time greater than t+Vt there is a positive chance that you hit the constraint. Without hitting the constraint the distribution is symetrical around Vt, and due to the chance of hitting it you increase the expectation.

However, I am aware that a series that keeps increasing may converge, so I am at a loss to prove or show whether the expecation goes to infinity if you just keep walking forever.

Answer 1

Consider the symmetric random walk $(S_n)$ on the integers, defined by $S_0=0$ and $S_n=X_1+\cdots+X_n$ for every $n\geqslant1$, where $(X_n)$ is i.i.d. with $P(X_n=1)=P(X_n=-1)=\frac12$. Introduce $M_n=\max\{S_0,S_1,\ldots,S_n\}$ and $Y_n=M_n-S_n$. Then:

The dynamics of the process $(Y_n)$ is the dynamics described in the question.$^*$

Now, $E(S_n)=0$ hence $E(Y_n)=E(M_n)$ and it is known that $E(M_n)\sim\sqrt{2n/\pi}$ hence $E(Y_n)\to\infty$.

$^*$ To see why, consider the dynamics of $(Y_n)$.

• If $Y_n\geqslant1$, then $M_n\geqslant S_n+1$ hence the fact that $S_{n+1}\leqslant S_n+1$ almost surely implies that $M_{n+1}=M_n$ almost surely, thus $Y_{n+1}=Y_n-X_{n+1}$, that is, $Y_{n+1}=Y_n+1$ or $Y_{n+1}=Y_n-1$ with equal probabilities.
• If $Y_n=0$, then $M_n=S_n$ hence $M_{n+1}=S_{n+1}$ if $X_{n+1}=+1$ while $M_{n+1}=M_n$ and $S_{n+1}=S_n-1$ if $X_{n+1}=-1$, that is, $Y_{n+1}=0$ or $Y_{n+1}=+1$ with equal probabilities.

These are the desired transition probabilities. To sum up, $$Y_{n+1}=\max(Y_n-X_{n+1},0).$$