# Asymmetric Random Walk / Prove that $E[T:= \inf\{n: X_n = b\}] < \infty$

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?

• From where did you take this problem? – james42 Dec 6 '15 at 19:20
• @james42 previous exam in my university – BCLC Dec 6 '15 at 19:21

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).

• 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. – KT. Dec 7 '15 at 11:37
• Huh? If T is infinite, its expectation is infinite. Right? – BCLC Dec 7 '15 at 11:39
• 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. – KT. Dec 7 '15 at 11:44
• 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. – KT. Dec 7 '15 at 15:11
• 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. – KT. Dec 10 '15 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$$

• If you can provide more details, it will be more useful. – Gordon Dec 15 '15 at 20:15