Here is a small particle on an axis and resides at the origin $0$.
The particle movement
We suppose that when this particle resides at the origin, it moves to $-1$ or $1$ with probability $\frac{1-p}{2}$ and stays still at origin with probability $p$. Whenever it is at a place other than $0$, if it is in position $n > 0$ or $n < 0$, it moves to $n - 1$ or $n + 1$ with probability $p(p > \frac{1}{2})$, and with probability $1-p$ it will move to $n + 1$ or $n - 1$.
Prove that there exist constants $w,C,D$, s.t.
$$(\forall{}m)\lim_{T\rightarrow{}\infty}\sup\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{Pr}\{|n(t)>D+m|\}\leq{}Ce^{-wm}$$
Hint: Use an exponential Lyapunov function of the form
Obviously this 'random walk' can be easily viewed as a queue system where queue length $Q(t)=|n(t)|$ and arrival $A(t)=A$ is a random variable.
$$Q(t+1)=[Q(t)-(1-A)]^++A$$
But I wonder how to create something like $e^{-m}$ or $e^m$ in Lyapunov drift (maybe use $T$-slot form?).
Can someone give some ideas about this question? Thanks a lot!
Greetings.