Showing $P\left(\sup_n S_n\ge k\right)\le\left(\frac{p}{1-p}\right)^k$

Question

Asymmetric Random Walk:

If $p<1/2$ and $\{X_i\}_i$ are iid with $P(X_i=1)=p$ and $P(X_i=-1)=1-p$, let denote $S_n=\sum_{i=1}^nX_i$, then show that $$P\left(\sup_n S_n\ge k\right)\le\left(\frac{p}{1-p}\right)^k.$$

Is is possible to solve that without Markov chains? (We didn't cover it yet). Can one make use of the fact that $Y_n:=\left(\frac{1-p}{p}\right)^{S_n}$ is a martingale?

$$P\left(\sup_n S_n\ge k\right)=P\left(\bigcup_n\{S_n\ge k\}\right)=P\left(\bigcup_n\left\{Y_n\ge \left(\frac{1-p}{p}\right)^k \right\}\right)=\dots$$

Then somehow use conditional probability?

Answer 1

Theorem.Doob's inequality. Let $X_n$ be a submartingale, $\lambda>0$, then $$\lambda P(\max_{m\leq n} X_m^+\geq \lambda)\leq EX_n^+.$$

This is theorem 4.4.2 in Durrett's PTE five, you can find the proof here in page 235.

By Doob's inequality, $$\left(\frac{1-p}{p}\right)^kP\left(\max_{n\leq m} Y_n\geq \left(\frac{1-p}{p}\right)^k\right)\leq EY_m=EY_1=1$$ so $$P\left(\max_{n\leq m} Y_n\geq \left(\frac{1-p}{p}\right)^k\right)\leq \left(\frac{p}{1-p}\right)^k.$$ Letting $m\to\infty$ gives the desired result.