Suppose we have a 1D symmetric random walk $S_n$. How do I calculate $\mathbb{P}(|S_n|\geq n\lambda)$ for some $\lambda\in(0,1)$?
I clearly need $|\{i:X_i=1\}|\geq n\lambda+|\{i:X_i=-1\}|$ or $|\{i:X_i=-1\}|\geq n\lambda+|\{i:X_i=1\}|$ if $S_n=\sum_{i=1}^nX_i$, but I don't know how to calculate these values. An upper bound on the probability is enough for my problem.
Hoeffding's inequality tells you that for independent symmetric Bernoulli random variables $X_1, X_2, \dots, X_n$ (i.e. $P(X_i=\pm 1)=0.5$) and $a=(a_1,\dots,a_n)\in \mathbb{R}^n$ the following inequality holds for all $t>0$:
$$\mathbb{P}\left(\left|\sum_{i=1}^n a_iX_i\right| \geq t\right) \leq 2\exp\left(-\frac{t^2}{2\|a\|_2^2}\right)$$
In your case, by taking $a=(1,1,\dots,1)$ we get:
$$\mathbb{P}(|S_n|\geq n\lambda)\leq 2\exp\left(-\frac{n\lambda^2}{2}\right)$$