Hoeffding inequality for independent bounded sums

Set ${\mathcal{F}}_0=\{\mathrm{\varnothing },\mathrm{\Omega }\}$, ${\mathcal{F}}_i=\sigma (X_1,\dots ,X_i)$, $D_i=X_i-\mathbb{E}{X}_i$, and $c_i=b_i-a_i$. By [F13], $D_i$ is ${\mathcal{F}}_i$-measurable. By [F1] and [F2], $X_i$ is independent of ${\mathcal{F}}_{i-1}$; [F3] gives $\mathbb{E}[X_i\mid {\mathcal{F}}_{i-1}]=\mathbb{E}{X}_i$, and conditional linearity and preservation of constants in [F6] therefore give $\mathbb{E}[D_i\mid {\mathcal{F}}_{i-1}]=0$ almost surely.

By [F4], $a_i\le \mathbb{E}{X}_i\le b_i$. Therefore $D_i$ lies almost surely in the finite interval $[a_i-\mathbb{E}{X}_i,b_i-\mathbb{E}{X}_i]$, whose endpoints are ${\mathcal{F}}_{i-1}$-measurable, contain $0$, and have width $c_i$; in particular $\mathrm{\mid }{D}_i\mathrm{\mid }\le c_i$.

Apply [F5] to each $D_i$ and the filtration ${\mathcal{F}}_{i-1}$ from step 1.1. For every real $\lambda$, $\mathbb{E}[e^{\lambda D_i}\mid {\mathcal{F}}_{i-1}]\le e^{{\lambda }^2{c}_i^2\mathrm{/}8}$ almost surely.

Let $S_k={\sum }_{i=1}^k{D}_i$ and $S_0=0$. Step 1.2 gives $\mathrm{\mid }{D}_i\mathrm{\mid }\le c_i$, hence $S_{k-1}\in [-C,C]$ for $C:={\sum }_{i<k}{c}_i$. This closed bounded interval is compact by [F11], and $x\mapsto e^{\lambda x}$ is continuous by [F10] and continuity of scalar multiplication, so [F12] makes $e^{\lambda S_{k-1}}$ bounded. Also $x\mapsto e^{\lambda x}$ is Borel: its open-set preimages are open, and the class of Borel sets whose preimages are Borel is a sigma-algebra containing the opens, hence contains the Borel sigma-algebra (The Borel sigma-algebra of a topological space). For each Borel $B$, the preimage of $B$ under $e^{\lambda S_{k-1}}$ is $S_{k-1}^{-1}((x\mapsto e^{\lambda x}{)}^{-1}(B))$, so this bounded factor is ${\mathcal{F}}_{k-1}$-measurable. By the addition formula in [F10], $e^{\lambda S_k}=e^{\lambda S_{k-1}}{e}^{\lambda D_k}$; conditional expectation preservation [F6], taking out the known factor [F7], and step 2.1 give $\mathbb{E}{e}^{\lambda S_k}\le e^{{\lambda }^2{c}_k^2\mathrm{/}8}\mathbb{E}{e}^{\lambda S_{k-1}}$. Finite induction gives $\mathbb{E}{e}^{\lambda S_n}\le e^{{\lambda }^{2}V\mathrm{/}8}$.

If $V=0$, every $c_i=0$, so each $X_i=a_i=b_i$ almost surely and $S=0$ almost surely. If $V>0$ and $\lambda >0$, then $e^{\lambda S}$ is nonnegative and $S\ge t$ implies $e^{\lambda S}\ge e^{\lambda t}>0$ by [F10]. Markov [F8] and step 3.1 give $\mathbb{P}(S\ge t)\le e^{{\lambda }^{2}V\mathrm{/}8}\mathrm{/}{e}^{\lambda t}=\exp (-\lambda t+{\lambda }^{2}V\mathrm{/}8)$, using the reciprocal and addition formulas in [F10]. Choosing $\lambda =4t\mathrm{/}V$ gives $\mathbb{P}(S\ge t)\le e^{-2t^2\mathrm{/}V}$.

If $V>0$, substitute $-\lambda$ in the all-real MGF bound from step 3.1. Since $e^{-\lambda S}$ is nonnegative and $S\le -t$ implies $e^{-\lambda S}\ge e^{\lambda t}>0$ by [F10], Markov [F8] gives $\mathbb{P}(S\le -t)\le e^{{\lambda }^{2}V\mathrm{/}8}\mathrm{/}{e}^{\lambda t}$; choosing $\lambda =4t\mathrm{/}V$ yields $e^{-2t^2\mathrm{/}V}$. The finite union bound [F9] combines the two tails; step 4.1 already handles $V=0$. This lower-tail argument uses the same original variables and does not assert independence of their negatives.