# Optional Sampling Theorem Application on a Martingale

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?

-

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.

-
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