I'm reading the course notes of a probability course about martingales currently and I'm trying to solve some of the exercises, however I'm very much stuck with the following exercise:

Let $\left\{ X_{n}\right\} _{n=1}^{\infty}$ be a simple random walk on $\mathbb{Z}$ started at $X_{0}=a$ . Given $b\in\mathbb{Z}$ denote by $T_{b}$ the first hitting time of $b$ , show that $\mathbb{E}_{a}\left[T_{b}|\, T_{b}<T_{0}\right]=\frac{b^{2}-a^{2}}{3}$ .

Hint: Show that $M_{n}:=X_{n}^{3}-3nX_{n}$ is a martingale and use the fact that $\left|M_{\min\left(T_{b},n\right)}\right|\leq b^{3}+3bT_{b}$

I've shown that indeed that is a martingale but I have no idea how to proceed, help would be appreciated.


  • $\begingroup$ Which uses have martingales, in general? $\endgroup$ – Did Jul 1 '14 at 19:12
  • $\begingroup$ The only intuition I got is that Martingales are supposed to represent a "fair game/gamble", beyond that I'm not very comfortable with the concept or its uses... It would be nice if people that down voted would at least explain the reasoning behind their down vote. Obviously I'm having difficulty or I wouldn't have asked the question. $\endgroup$ – LlamaMan Jul 1 '14 at 19:15
  • $\begingroup$ Honestly, what is a bit surprising is that you do not seem to be even aware of the mammoth result in this field, called the stopping time theorem. $\endgroup$ – Did Jul 1 '14 at 19:18
  • $\begingroup$ @Did I've looked up the theorem and I see it's indeed a very powerful result. But I'm not sure the condition here meets the criteria of the theorem, the third condition requires that $\left|M_{\min\left(T_{b},n\right)}\right|\leq c$ a.s for every $n$, but the bound I have depends on $T_{b}$. I apologize if the question seems banal to some but I've been glaring at this for some time now and I'm not making much progress myself, I would really appreciate it if you could help me. $\endgroup$ – LlamaMan Jul 1 '14 at 19:48
  • $\begingroup$ can you show that $T_b$ is integrable?, i.e. $\mathbb{E}_aT_b<\infty$. If so, then option sampling theorem applies, because your martingale is bounded by a random variable which is integrable. $|M_{\min(T_b,n)}|\leq c$ is sufficient but not necessarily (effectively, you need to apply the dominated convergent theorem, bounded by an $L^1$ R.V. is sufficient) $\endgroup$ – Lost1 Jul 1 '14 at 20:40

Optional samping theorem holds for every bounded stopping time.

Consider the stopping time $\min(T_0,T_b,n)$ where $T_0$ is the first time the Markov Chain hits $0$, then

$|M_{\min(T_0,T_b,n)}|\leq b^3+3b\min(T_0,T_b)$, the right handside is integrable.

Optional Sampling theorem says

$\mathbb{E}_a M_{\min(T_0,T_b,n)} = \mathbb{E}_a M_0$

since the right hand side is bounded by an integrable random varaible, we take $n$ to infinity and get

$\mathbb{E}_a M_{\min(T_0,T_b) }=a^3$

so the left handside equals to

$\mathbb{P}_a(T_b<T_0)(b^3 - 3b \mathbb{E}_aT_b1_{\{T_b<T_0\}}) + \mathbb{P}_a(T_0<T_b)(0) = a^3$

Note that $X$ is also a martingale, so $\mathbb{P}_a(T_b<T_0)=a/b$ (apply OTS to $X$). This means

$$\frac{b^2-a^2}{3} = \mathbb{E}_aT_b1_{\{T_b<T_0\}}$$

  • $\begingroup$ this only gives $ET_b$, need a bit more than this. I am editting. $\endgroup$ – Lost1 Jul 1 '14 at 21:08
  • $\begingroup$ Doesn't $\min\left(T_{b},n\right)$ need to be bounded by a constant that doesn't depend on $n$ in order to use the OST in that fashion? $\endgroup$ – LlamaMan Jul 1 '14 at 21:09
  • $\begingroup$ @NewGuy $min(T_b,n)$ is bounded by $n$, for each $n$, then you take the limit because the RANDOM VARIABLES are bounded. Optional Sampling theorem only tells you $EX_T=EX_0$ when $T$ is a bounded stopping time for 1 bounded stopping time... very rarely are stopping times you are interested in are actually bounded... $\endgroup$ – Lost1 Jul 1 '14 at 21:10
  • $\begingroup$ @NewGuy something is wrong here, because $ET_b$ should be infinite for a random walk... also please check your question again and confirm that it is correct $\endgroup$ – Lost1 Jul 1 '14 at 21:13
  • 1
    $\begingroup$ @NewGuy btw, Could have use the optional stopping theorem version (2) on wiki en.wikipedia.org/wiki/Optional_stopping_theorem the increment is bounded by 1. Also in this question $T_b$ and $T_0$ both appear so it was the right to consider their min. Morever $E\min(T_0,T_b)$ is finite, whereas $ET_b$ is not. $\endgroup$ – Lost1 Jul 1 '14 at 21:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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