Symmetric random walk on the integers

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