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

Question

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?

Answer 1

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

Answer 2

$\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$$