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

Question

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?

Answer 1

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

Answer 2

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.