Consider a random walk $S_n=S_0+\sum^b_{i=1}X_i$ with i.i.d steps $X_i$ taking value $4$ and $-7$ with probabilities $\frac{7}{11}$ and $\frac{4}{11}$ respectively.

I would like to find a constant $\gamma$ such that $Y_n=S^2_n-\gamma n$ is a martingale, and hence to determine the expected duration of the walk until absorption at either boundary.

My attempt:

To impose the martingale condition on $Y_n$, one has to evaluate $$E[Y_{n+1}|\mathcal{F}_{n}]=E[(S_n+X_{n+1})^2-\gamma(n+1)|\mathcal{F}_n]=S^2_n+E[X^2]-\gamma(n+1)\Leftrightarrow \\E[X^2]-\gamma=0$$

We have that $$E[X^2]=16\left(\frac{7}{11}\right)+49\left(\frac{4}{11}\right)=10.18+17.81\approx28$$

So, $\gamma=28$

Is this correct?

How do I determine the expected duration of the walk until absorption at either boundary?

  • $\begingroup$ Did you suppose that $S_0=0$ ? $\endgroup$ Aug 12, 2021 at 14:18
  • 1
    $\begingroup$ Your calculation of $\gamma$ seems to be correct. What are the boundaries of the walk? $\endgroup$ Aug 12, 2021 at 22:30
  • $\begingroup$ This is very similar to your previous question today. It is not clear why you expect the answer to be exactly calculable. As in the previous question, you can use the stopping theorem to get upper and lower bounds, exact answers seem hard due to overshoot issues. $\endgroup$
    – Michael
    Aug 13, 2021 at 3:40

2 Answers 2


As mentioned in comments, your method for computing $\gamma$ is correct, but there is little hope of getting an exact value for $E[T]$ due to overshoot issues. The idea is to get bounds.

You have $Y_0=E[Y_T]= E[S_T^2] - \gamma E[T]$. Assuming $Y_0$ and $\gamma$ are known, you just need upper and lower bounds on $E[S_T^2]$, which are relatively easy to get in terms of the probability $p$ of first crossing the right threshold. You can get upper and lower bounds on $p$ from your previous question (which used $S_0=E[S_T]$). That question is here: Probability the walk terminates


You could alternatively define $z_k$ as the expected time to cross one of the boundaries, given you start at location $k \in \mathbb{Z}$, and then use linear recurrence: $$ z_k = 1 + (7/11)z_{k+4} + (4/11)z_{k-7}$$ with appropriate boundary conditions $z_k=0$ for $k$ values that are beyond the boundaries. This has particular solution $$z_k=(-1/28)k^2$$ https://www.wolframalpha.com/input/?i=%28-1%2F28%29k%5E2+%3D+1+%2B+%28-1%2F28%29%28%287%2F11%29%28k%2B4%29%5E2+%2B+%284%2F11%29%28k-7%29%5E2%29

and homogeneous solutions $h_k = Ax^k$ for any root of $$ x^7 = (7/11)x^{11} + (4/11)$$ which seems to have $x=1$ as a double root, another real-valued root $x \approx -1.15503$, and 8 complex-valued roots, but it seems intractable to find exact expressions for all roots. https://www.wolframalpha.com/input/?i=factor%28x%5E7+-+%287%2F11%29x%5E11+-+%284%2F11%29%29

The homogeneous solutions are $$ h_k=A_1 + A_2k + \sum_{i=3}^{11}A_i x_i^k$$ for any $A_1, ..., A_{11}$, where $x_i$ are the remaining roots (not equal to 1) of the homogeneous equation, then choose $A_1, ..., A_{11}$ to match boundary conditions for $$\boxed{z_k = (-1/28)k^2 + A_1 + A_2k + \sum_{i=3}^{11}A_i x_i^k}$$ with $z_k=0$ at the 11 boundary conditions. This gives a system of 11 equations and 11 unknowns $A_1, ..., A_{11}$. Of course it assumes you have accurate values for all roots $x_3, ..., x_{11}$.

Overall the upper and lower bound method that uses the stopping theorem is much simpler.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .