# Showing a function of random walk is a martingale

I would like a hint for the following problem:

Consider a biased random walk on the integers with probability $p<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$. Show that $M_n=[(1-p)/p]^{S_{n}}$ is a martingale.

I need to show that $\mathbb{E}[M_{n+1}|S_{0}, \dots S_{n}] = M_{n}$. However \begin{align} \mathbb{E}[M_{n+1}|S_{0}, \dots, S_{n}] &= \mathbb{E}[[(1-p)/p]^{S_{n+1}}|S_{0}, \dots, S_{n}] \\ &= \mathbb{E}[[(1-p)/p]^{S_{n+1}}|S_{n}] &&\text{(By Markovity.)} \\ &= [(1-p)/p]^{p(S_{n}+1) + (1-p)(S_{n}-1)} \\ &= [(1-p)/p]^{S_{n}+2p-1}, \end{align} which is not what I need. So it seems that either I'm making a mistake or the problem is wrong.

Am I making a mistake?

Is $M_n$ a martingale?

-
I don't think $E[M_{n+1}]=((1-p)/p)^{E[{S_{n+1}}]}$ –  deinst Dec 8 '11 at 1:48

Your mistake is that $\newcommand{\E}{\mathbf{E}} \E(\exp(S_{n+1}))$ is not the same as $\exp(\E(S_{n+1}))$. Here's the corrected work: \begin{align*} \mathbf{E}[M_{n+1} \mid S_0, \ldots, S_n] &= \mathbf{E} \left[ \left. \left( \frac{1-p}{p} \right)^{S_{n+1}} \right| \ S_0, \ldots, S_n \right] \\ &= p \cdot \left( \frac{1-p}{p} \right)^{S_n + 1} + (1-p) \cdot \left( \frac{1-p}{p} \right)^{S_n - 1} \\ &= p \cdot \frac{1-p}{p} \cdot M_n + (1-p) \cdot \left(\frac{1-p}{p}\right)^{-1} \cdot M_n \\ &= (p + (1-p)) \cdot M_n \\ &= M_n. \end{align*}
Thanks. I think $(1-p)\cdot \frac{1-p}{p}$ should be $(1-p)\cdot \frac{p}{1-p}$. –  Quinn Culver Dec 8 '11 at 2:29