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?
Best Answer
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.