# Large deviation of random walk

1) Let $$\{X_i\}_{i=1}^n$$ be i.i.d. such that $$\Pr(X_i=1 )=1-\Pr(X_i=-1)=p$$. Define the random walk $$S_i = \sum_{j=1}^iX_j$$ for $$i=1,2,\ldots,n$$.

I am looking for "good" exponential upper bounds in $$n$$ on the probability $$\Pr\left(\max_{1\leq i\leq n} S_i>\max_{1\leq i\leq n}-S_i\right)$$ Observe that the probability in question can be lower and upper bounded as follows \begin{align} \max_{{1\leq i\leq n}}\Pr\left(S_i>\max_{1\leq i'\leq n}-S_{i'}\right)&\leq\Pr\left(\max_{1\leq i\leq n} S_i>\max_{1\leq i\leq n}-S_i\right)\\ &\leq n\max_{{1\leq i\leq n}}\Pr\left(S_i>\max_{1\leq i'\leq n}-S_{i'}\right) \end{align} and these lower and upper bounds are exponentially tight. The question is how the probability at the right hand side of the above inequality can be analyzed. One simple approach is to further upper bound the above as follows $$\Pr\left(\max_{1\leq i\leq n} S_i>\max_{1\leq i\leq n}-S_i\right)\leq n\max_{{1\leq i\leq n}}\min_{{1\leq i'\leq n}}\Pr\left(S_i>-S_{i'}\right)$$ and then Chernoff's bound can be used on the last probability term. However, it is not clear if the above bound gives the best exponential decay.

2) Let $$\{Y_i\}_{i=1}^n$$ be a sequence of independent random variables such that for a given $$k\geq1$$, $$\Pr(Y_i=1) = 1-\Pr(Y_i=-1) = \begin{cases} p,\ &1\leq i\leq k\\ 1-p\ &k+1\leq i\leq n \end{cases}$$ Define the reversed random walk $$S_i = \sum_{j=n-i+1}^nX_j$$ Again, is there any way to get an exponential upper bound in $$n$$ on the probability $$\Pr\left(\max_{1\leq i\leq n} S_i>\max_{1\leq i\leq n}-S_i\right)$$ when $$k$$ is assumed to be proportional to $$n$$.

• Can you confirm that $p<1/2$? Otherwise this probability does not decay. – Yuval Peres Jun 3 '19 at 2:28
• Are you still interested in an answer to this question? – Yuval Peres Jun 9 '19 at 0:19

Let's assume that $$p<1/2$$, Otherwise the probability in question does not decay exponentially. Then $$\max_{{1\leq i\leq n}}\Pr\left(S_i>\max_{1\leq i'\leq n}-S_{i'}\right)= \Pr\left(S_1>\max_{1\leq j\leq n}-S_{j}\right) \le \Pr\left(1>\ - S_{n}\right) ,$$ and this is bounded via the Chernoff bound, see https://en.wikipedia.org/wiki/Chernoff_bound
To see that this gives a tight exponent, note that given $$S_n>0$$, the probability that $$S_n$$ is minimal among $$S_1,\ldots,S_n$$ does not decay exponentially.