1
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Moreoever, maybe you could tell me the textbook or some material of random walk, from which i can find a original proof. Thank you so much :D $\endgroup$ – robit Nov 13 '13 at 12:31
1
$\begingroup$

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!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.