Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm struggling to figure out how to apply the optional sampling theorem to this problem. Here's the problem verbatim (it's problem 5.7 out of Lawler's Introduction to Stochastic Properties):

Consider a biased random walk on the integers with probability $p < \frac{1}{2}$ of moving to the right and probability $1 - p$ of moving to the left. Let $S_n$ be the value at time $n$ and assume that $S_0 = a$, where $0 < a < N$.

a) Show that $M_n = [(1-p)/p]^{S_n}$ is a martingale.
b) Let $T$ be the first time that the random walk reaches $0$ or $N$, i.e., $$T = min\{n : S_n = 0\ or\ N\}$$ Use optional sampling on the martingale $M_n$ to compute $P\{S(T) = 0\}$.

I'm nearly positive I did part $a)$ correctly. Here's my work for that:

I need to show that $E(M_{n+1}|F_n) = M_n.$

$$E(M_{n+1}|F_n) = E((\frac{1-p}{p})^{S_{n+1}}|F_n)=p(\frac{1-p}{p})^{S_n+1} + (1-p)(\frac{1-p}{p})^{S_n-1}$$ $$=p(\frac{1-p}{p})^{S_n}(\frac{1-p}{p}) + (1-p)(\frac{1-p}{p})^{S_n}(\frac{p}{1-p})$$ $$=(\frac{1-p}{p})^{S_n}(p + (1-p)) = (\frac{1-p}{p})^{S_n} = M_n$$

Since $E(M_{n+1}|F_n) = M_n$, I have shown that it is a martingale.

Part $b)$ is where I get tripped up. The martingale is bounded and $P\{T < \infty\} = 0$, so I know that I can use the optional sampling theorem and $E(M_T) = E(M_0)$. I just don't know what exactly I can do. Any advice for a novice?

share|cite|improve this question
up vote 2 down vote accepted

You have either $S(T)=0$ or $S(T)=N$. Thus you have

$$\Bbb{P}(S(T)=0) + \Bbb{P}(S(T)=N) = 1.$$

On the other hand, the application of optional sampling theorem gives

$$\begin{align*} \left(\frac{1-p}{p}\right)^{a} &= \Bbb{E}M_0 = \Bbb{E}M_{T} \\ &= \left(\frac{1-p}{p}\right)^{0}\Bbb{P}(S(T)=0) + \left(\frac{1-p}{p}\right)^{N}\Bbb{P}(S(T)=N). \end{align*}$$

Now we have a system of linear equations with respect to $\Bbb{P}(S(T)=0)$ and $\Bbb{P}(S(T)=N)$, thus we obtain the answer by solving this system.

share|cite|improve this answer
Thanks for your response. I actually made a typo in my original post. $M_n = [(1-p)/p]^{S_n}$, not $[(1-p)p]^{S_n}$. This, however, shouldn't change your answer (aside from changing your $p(1-p)$ terms to $(1-p)/p$). Either way, this makes perfect sense. Thank you! – jrad Nov 12 '12 at 3:59
@JackRadcliffe You're welcome. I also fixed it. – Sangchul Lee Nov 12 '12 at 14:14

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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