Symmetric random walk on the integers I found an exercise in a paper by Anupam Gupta, Sahil Singla that i couldn't solve, sadly my knowledge in Markov processes is pretty limited. The exercise is the following:
Suppose we have a symmetric random walk of length n on $\mathbb{Z}$ starting at point 0 conditioned on ending at the origin. Define $I_t$ as the position on $\mathbb{Z}$ after $t$ steps. Use a Chernoff-Hoeffding bound to show that $\max_t I_t-\min_t I_t$ is at most $O(\log n)$ with probability $1-\frac{1}{\text{poly}(n)}$.
I really do not know how to approach this, i would appreciate some help.
 A: Hint $1$: Hoeffding's bound is usually used on sums of independent random variables (usually Bernoulli or Rademacher). What could be the sums here? What are the independent random variables?
Hint $2$: Introduce some variable for the starting position and then try to figure out how $I_t$ can be expressed such that this starting position does not appear in the formula.
Hint $3$: Bound the probability that $|I_t|$ is large using Hoeffding.
Hint $4$: Recall the Union Bound.
Solution:
Let $X_i$ be the random variable which denotes the direction of the $i$-th step i.e. it is $-1$ with probability $1/2$ and $1$ with probability $1/2$. Let $s$ denote our starting point. As given in the exercise, we condition on the fact that $s + \sum_{i = 1}^n X_i = 0$. Hence $I_t$ is given by $I_t = s + \sum_{i = 1}^t X_i = \sum_{i = t + 1}^n X_i$ and has mean $0$. In particular, by the Hoeffding bound we have that
$$\text{P}(|I_t| \geq c \log n) \leq 2 \exp \left ( - \frac{(n - t)^2c^2\log^2n}{4(n - t)}\right) \leq 2 \exp \left ( - \frac{c^2\log^2n}{4}\right).$$
Using the Union-Bound we hence get
$$\text{P}(\max_t I_t - \min_t I_t \geq 2c \log n) \leq 2n \exp \left ( - \frac{c^2\log^2n}{4}\right) = \frac{2n}{n^{\frac{c^2\log n}{4}}}.$$
We conclude that we get $\max_t I_t - \min_t I_t = \mathcal{O}(\log n)$ with probability at least $1 - \frac{1}{\text{poly}(n)}$.
