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}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.