1-d random walk probability bound calculation problem I'm recently reading the paper about digital fountain code "LT Codes" by M. Luby.
There is a statement seems simple with the author "The probability a random walk of length $k$ deviates form its mean by more than $\text{ln}(k/\delta)\sqrt{k}$ is at most
$\delta$".
Let me describe this in math formulation. Suppose $X_1, X_2, ..., X_k$ is mutually independent identically distributed, and 
$$\text{Pr}(X_i)=\begin{cases} \frac12,&X_i=\pm1\\0, &\text{else}\end{cases}$$
consider a sum of $X_i$,$S_k=\sum_{i=1}^k X_i$ .
Then there is a bound of probability:
$$\text{Pr}\{\max\limits_{1\le{i}\le{k}}|S_i|\gt \text{ln}(k/\delta)\sqrt{k}\}\le{\delta}$$
There's not much material about random walk i can obtain. Please someone show me the proof of the statement. Thanks very much!
 A: Kolmogorov's inequality yields more, namely, the upper bound $1/(\ln(k/\delta))^2$. 
This is less than $\delta$ for every $\delta$ in $(0,1)$, for every $k\geqslant\exp(1/\sqrt{\delta})$.
A: There are a lot maximal inequalities like this. 
You can see: Bernstein inequality
Once you have Bernstein you can proof the following:
There are $c_1, c_2 >0 $ such that
$$ \frac{c_1exp(-k_{n}^{2}/2)}{k_n} \le P(\max\limits_{1\le{i}\le{n}}|S_i|\ge \sqrt{n}k_n) \le \frac{c_2exp(-k_{n}^{2}/2)}{k_n}  $$
If $k_n = o(n^{\frac{1}{6}})$.
The proof, as I said, makes use of Bernstein and the Local Limit Theorem. First you proof a similar statement to $S_n$ and then use that $P(\max\limits_{1\le{i}\le{n}}|S_i|\ge a) \le 4P(S_n \ge a)$ and the fact that $ \{S_n \ge a\} \subset \{\max\limits_{1\le{i}\le{n}}|S_i|\ge a\}$ to get the result.
Note that $log(n/\delta) = o(n^{\frac{1}{6}})$ and you can use $\sqrt{log(n/\delta)}$ instead of $log(n/\delta)$ to get "exactly" what you want.
I can show you all the details if you want. But you can see this reference:
Limit Theorems of Probability Theory - Pál Révész
Hope this can help!
