Consider a classical symmetric random walk that starts at origin $x=0$ and lasts for $N$ steps. If $x=-1$ is reached, a walk is terminated. What is the expected value of this process?

I divided a walk into 2 parts.

  1. A path hits $x=-1$ at some step $n \le N$. Then, I can compute a part of a total expected value summing the probabilities with weight $-1$ as it was presented in https://math.stackexchange.com/a/182376
  2. However, I encounter a problem with a part giving rise from walking only in the nonnegative part of the axis. How should I proceed?
  • $\begingroup$ Are you familiar with martingales? $\endgroup$ – carmichael561 Mar 7 '16 at 20:55
  • $\begingroup$ How may it help? $\endgroup$ – qoqosz Mar 8 '16 at 6:41
  • $\begingroup$ You can use the optional stopping theorem $\endgroup$ – carmichael561 Mar 8 '16 at 6:42

Let $\{\xi_n\}_{n=1}^{\infty}$ be a sequence of i.i.d. random variables with $\mathbb{P}(\xi_i=1)=\mathbb{P}(\xi_i=-1)=\frac{1}{2}$, and let $X_0=0$, $X_n=\xi_1+\dots+\xi_n$ for $n\geq 1$. Then $\{X_n\}$ is a martingale with respect to the natural filtration $\mathcal{F}_n=\sigma(\xi_1,\dots,\xi_n)$.

Define a stopping time $T_{-1}=\min\{n\in\mathbb{N}:X_n=-1\}$, and let $T=\min\{T_{-1},N\}$. Then $T$ is a bounded stopping time, hence by the Optional Stopping Theorem, $$ \mathbb{E}(X_T)=\mathbb{E}(X_0)=0 $$


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.