Given random variables $Y_1, Y_2, ... \stackrel{iid}{\sim} P(Y_i = 1) = p = 1 - q = 1 - P(Y_i = -1)$ where $p > q$ in a filtered probability space $(\Omega, \mathscr F, \{\mathscr F_n\}_{n \in \mathbb N}, \mathbb P)$ where $\mathscr F_n = \mathscr F_n^Y$,

define $X = (X_n)_{n \ge 0}$ where $X_0 = 0$ and $X_n = \sum_{i=1}^{n} Y_i$.

It can be shown that the stochastic process $M = (M_n)_{n \ge 0}$ where $M_n = X_n - n(p-q)$ is a $(\{\mathscr F_n\}_{n \in \mathbb N}, \mathbb P)$-martingale.

Let $b$ be a positive integer and $T:= \inf\{n: X_n = b\}$.

It can be shown that $T$ is a $\{\mathscr F_n\}_{n \in \mathbb N}$-stopping time.

Prove that $E[T] < \infty$.

One proposition to use is 'What always stands a reasonable chance of happening will (almost surely) happen - sooner rather than later' or here (proof here)

So let us show either that $\exists N \in \mathbb N, \epsilon > 0$ s.t. $\forall n \in \mathbb N$,

$$P(T \le n + N | \mathscr F_n) > \epsilon$$

or the weaker condition that $\exists N \in \mathbb N, \epsilon > 0$ s.t. $\forall n \in \mathbb N$,

$$P(T > kN) \le (1 - \epsilon)^k$$

I tried the first one:

$$P(T \le \infty | \mathscr F_n) = E(1_{T \le \infty} | \mathscr F_n) = \sum_{i=1}^{n} 1_{T=i} + \sum_{i=n+1}^{\infty} E[1_{T=i} | \mathscr F_n]$$

Hence, we must find and integer N and a positive number $\epsilon$ s.t.

$$P(T \le n + N | \mathscr F_n) = E(1_{T \le n + N} | \mathscr F_n) = \sum_{i=1}^{n} 1_{T=i} + \sum_{i=n+1}^{n+N} E[1_{T=i} | \mathscr F_n] > \epsilon$$

where $\forall i > n$,

$$E[1_{T=i} | \mathscr F_n] = P(T=i | \mathscr F_n)$$

$$= P(X_i = b, X_1 \ne b, X_2 \ne b, ..., X_n \ne b, ..., X_{i-1} \ne b | \mathscr F_n)$$

$$= \prod_{j=1}^{n} 1_{X_j \ne b} E[1_{X_i = b} \prod_{j=n+1}^{i-1} 1_{X_j \ne b} | \mathscr F_n]$$

That's all I got. How can I approach this problem?

  • $\begingroup$ From where did you take this problem? $\endgroup$
    – james42
    Commented Dec 6, 2015 at 19:20
  • $\begingroup$ @james42 previous exam in my university $\endgroup$
    – BCLC
    Commented Dec 6, 2015 at 19:21

2 Answers 2


Let $b=1$, $p=1/3$, $q=2/3$. It is not hard to show that in this case $T$ is finite with probability exactly $1/2$. Consequently, $E[T] = \infty$ and your claim does not hold in general.

The claim would hold if $p\geq q$ (in which case you could, for example, address it by first showing that it holds for $b=1$ and proceeding inductively from there on).

  • 1
    $\begingroup$ The induction would easily get you that P(T is finite) = 1. It immediately follows that E[T] is finite, although I could not point you to the relevant theorem off the top of my head right now. $\endgroup$
    – KT.
    Commented Dec 7, 2015 at 11:37
  • $\begingroup$ Huh? If T is infinite, its expectation is infinite. Right? $\endgroup$
    – BCLC
    Commented Dec 7, 2015 at 11:39
  • 1
    $\begingroup$ That proposition is something that may help you connect P(T is finite) = 1 to E[T] is finite. You would still need to show that P(T is finite) = 1. That one is easily shown by observing that with probability one T will move one step up (i.e. solve for b=1). From there it inductively follows that with probabilty one T will move any number of steps up. $\endgroup$
    – KT.
    Commented Dec 7, 2015 at 11:44
  • 1
    $\begingroup$ T is not always finite, it is only finite with probability 1. It is therefore not "immediately obvious" that it should follow that E[T] is finite. Theorems like the proposition you mentioned basically establish this or similar "obvious" properties. $\endgroup$
    – KT.
    Commented Dec 7, 2015 at 15:11
  • 1
    $\begingroup$ No. Induction is over b. Using the method shown in the link you can show that T will move one step up with probability 1 (i.e. T is finite for b=1). From there on it is easy to show that the same must hold for b=2,3,4,... the latter generalization is the "induction" part. $\endgroup$
    – KT.
    Commented Dec 10, 2015 at 0:47

$\because M_n$ is a martingale and $T \wedge k$ is bounded, by Doob's optional stopping theorem, we have

$$E[M_{T \wedge k}] = E[M_0] = 0$$

$$\to E[T \wedge k] = \frac{1}{p-q} E[X_{T \wedge k}]$$

By monotone convergence theorem, we have

$$E[T] = \lim_{k \to \infty} E[T \wedge k]$$

Finally, by definition of $T$, we have

$$X_{T \wedge k} \le \frac{b}{p-q}$$

$$\to E[T] \le \frac{b}{p-q} < \infty \ QED$$

  • 1
    $\begingroup$ If you can provide more details, it will be more useful. $\endgroup$
    – Gordon
    Commented Dec 15, 2015 at 20:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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