Problem
Let $X_1,X_2,\dots$ be independent each with $P(X_j=1)=P(X_j=-1)=1/2$. Let $S_n=X_1+X_2+\cdots +X_n$ and $N>1$ be an integer. Define the stopping time $$ T=\inf\{n: |S_n|=N\} $$ Show that there exists $c<\infty$, $0<\rho<1$ (depending on $N$) such that $$ P(T>n)\leq c\rho^n $$
Attempt I'd like to solve this using first principles and without invoking Markov chain theory. Now the event $\{T>n\}=\{|S_k|< N,k=1,\dots,n\}=\{\max_{1\leq k\leq n} |S_k|<N \}$. However, I'm unable to turn this into anything useful. Can someone give me a hint on how to proceed?
Note that for every $n\geq 0$, we have $P(T>n+N\;|\;T>n) \leq 1-2^{-N}$. This is because starting from any point $x \in \{-N+1,...,N-1\}$, there is probability at least $2^{-N}$ of escaping this interval after $N$ steps.
Hence we see that $P(T>2 N) =P(T>2 N\;|\;T> N)P(T> N) \leq (1-2^{-N})^2$. Continuing inductively, we get that $P(T>k N) \leq (1-2^{-N})^k$, for every $k>0$.
Therefore, the claim holds, with $\rho=\big(1-2^{-N}\big)^{1/ N}$.