2
$\begingroup$

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

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

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .