# inequality for random walk with bounded random variables

Let's consider the random variables $\xi_i$, independent and identically distributed. These variables take values on the finite set of integers $S=\{-s, -s+1, \, \ldots \, 0 \, ,\, \ldots \, s-1, \, \, s \}$ and are distributed according to a certain distribution $F$. Let's call $E \xi$ the expected value of each random variable.

Let's define the random variable $i(t) = \sum_{i=1}^t \xi_i$. I want to prove that, for every constant $\delta$ and for every $m$ s.t. $0<m<s/2$, there exists a constant $u<1$ such that the following inequality holds FOR EVERY $t \in [0, \infty]$,

$$i(t) - t \, \, E\xi \, \, \leq \, \, t \, \, \delta + m$$ with probability larger than $1 - u^m$.

General idea: for the law of large numbers (in the strong sense) the inequality will hold with probability 1 for all $t$ larger than a sufficiently big constant $T$, dependent on $\delta$. But how to prove that it will hold with probability larger than $1 - u^m$ for ALL times $0 \leq t \leq T$?

-
 This is a (basic) large deviations result. // How come your accept rate is 0%? – Did Jan 21 at 11:42