Tail bound for maximum of asymmetric random walk with varying transition probability

34 Views Asked by At

Suppose we are considering an asymmetric random walk $X_t$ beginning at $X_0 = 1$, with varying probability on $\mathbb{Z}_{\ge 0}$ : $$P(X_{t+1}=n+1 | X_t = n) = p(n) \quad P(X_{t+1}=n-1 | X_t = n) = q(n) \quad P(X_{t+1}=n | X_t=n) = 1-p(n)-q(n)$$ The state $0$ is an absorbing state, i.e., $$P(X_{t+1}=0 | X_t=0) = 1$$ If we know the chain always tends to move towards state $0$, i.e., we know for all $n > 0$, it holds that $$\frac{q(n)}{p(n)} \ge c$$ for some constant $c > 1$.

Intuitively, as the chain is more likely to move towards $0$ at each state $n$, I conjecture that with high probability the chain would not move too far before hitting $0$. So I want to get a tail bound of $Y := \max_{t \ge 0} X_t$, i.e., $$P(Y \ge y) \le f(y).$$ How can I derive some tail bound for this $Y$?

Some numerical experiments I did indicates that $f(y)$ could be exponentially decaying in $y$. Additionally, if we consider the special case of the same transition probability where $\frac{q(n)}{p(n)} = \frac{q}{p} = c$, the problem is equivalent to the classic Gambler's ruin problem. By considering the martingale $M_t = (q/p)^{X_t}$, we can show that $P(Y \ge y) \le \frac{c-1}{c^y-1}$, which is an exponential tail.