0
$\begingroup$

We have a simple symmetric random walk $(X_n)_{n\geq 0}$ on the integers, starting at $X_0 = 0$. I've shown that it's irreducible, and null-recurrent. We define $T = \inf\{n\geq 1 : X_n = 0\}$, the first time the chain returns to the origin, and I'm asked to compute $\mathbb{E}[s^T]$ for $0<s<1$.

Attempt so far: Conditioning on the first step seems like a good start, giving \begin{equation}\mathbb{E}[s^T] = \frac{1}{2}\left(\mathbb{E}[s^T \mid X_1 = 1] + \mathbb{E}[s^T \mid X_1 = -1]\right).\end{equation} But continuing from here would give the first hitting time of 0 starting from plus or minus 1. Should I instead be looking at $T_i$, the hitting time of 0 starting from $i$? Or should I next condition on $X_2$ to give $T$ again?

$\endgroup$

1 Answer 1

1
$\begingroup$

Well, by symmetry we have $\mathbb E[s^T \mid X_1 = 1] = \mathbb E[s^T \mid X_1 = -1]$: it doesn't matter which way you go first, both directions are identical. So conditioning on the first step doesn't really tell you anything.

It's the second step where interesting things happen. Let $T_{ij}$ be the hitting time to first reach state $j$ from state $i$; then $\mathbb E[s^{T_{20}}] = \mathbb E[s^{T_{21}}] \cdot \mathbb E[s^{T_{10}}] = \mathbb E[s^{T_{10}}]^2$, the latter by translational symmetry.

Since from $1$, we go to either $2$ or $0$, we have $$\mathbb E[s^{T_{10}}] = \frac12 \left(s \cdot E[s^{T_{20}}] + s\right) = \frac12 \left(s \cdot \mathbb E[s^{T_{10}}]^2 + s\right),$$ and now we're getting somewhere: solving for $\mathbb E[s^{T_{10}}]$ yields $$\mathbb E[s^{T_{10}}] = \frac{1-\sqrt{1-s^2}}{s}$$ and therefore $\mathbb E[s^T] = s \cdot \mathbb E[s^{T_{10}}] = 1 - \sqrt{1-s^2}$.

$\endgroup$
1
  • $\begingroup$ Ah of course! Should really have tried conditioning on the second step. Thank you $\endgroup$
    – B. Mehta
    May 21, 2017 at 8:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.