Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 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?

share|cite|improve this question
I don't think $E[M_{n+1}]=((1-p)/p)^{E[{S_{n+1}}]}$ – deinst Dec 8 '11 at 1:48
up vote 3 down vote accepted

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*} $$

share|cite|improve this answer
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
@Srivatsan I took the liberty and added a missing power. Feel free to roll back if it was not a typo. – Sasha Dec 8 '11 at 2:31
Thanks, @Sasha. That was indeed a typo. – Srivatsan Dec 8 '11 at 2:31

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.