1-d random walk probability bound calculation problem

Question

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!

Answer 1

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

Answer 2

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!