Concentration

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.

Let $v_i=\mathbb{E}[X_i^2]$. If $v=0$, then every $v_i=0$ because $v_i\ge 0$. By [F6], $X_i^2=0$ almost surely for every $i$, so the finite sum is $0$ almost surely and the stated tail probability is $0$.

Suppose $v>0$. If $b=0$, every $X_i=0$ almost surely and $v=0$, a contradiction; hence $b>0$. For each fixed real $\theta$, $g_{\theta }(x)=e^{\theta x}$ is continuous: when $\theta \mathrm{\ne }0$, continuity of $x\mapsto \theta x$ follows from $\mathrm{\mid }\theta x-\theta y\mathrm{\mid }=\mathrm{\mid }\theta \mathrm{\mid }\mathrm{\mid }x-y\mathrm{\mid }$, and continuity of its composition with $e^x$ follows from [F10]; when $\theta =0$ it is constant. Thus $g_{\theta }$ is Borel: the Borel sets whose inverse images under $g_{\theta }$ are Borel form a sigma-algebra containing every open set, hence contain the sigma-algebra generated by opens (The Borel sigma-algebra of a topological space). For each Borel $B$, $\{g_{\theta }(X_i)\in B\}=X_i^{-1}(g_{\theta }^{-1}(B))$ is measurable. Now fix $i$ and $\lambda$ with $0<\mathrm{\mid }\lambda \mathrm{\mid }<3\mathrm{/}b$. For $N\ge 2$, the exponential series tail on $[-b,b]$ is uniformly bounded by $r_N={\sum }_{k>N}(\mathrm{\mid }\lambda \mathrm{\mid }b{)}^k\mathrm{/}k!\to 0$. Each partial sum at $X_i$ is integrable; the uniform bound and [F9] give $\mathrm{\mid }\mathbb{E}[e^{\lambda X_i}]-\mathbb{E}[{\sum }_{k=0}^N(\lambda X_i{)}^k\mathrm{/}k!]\mathrm{\mid }\le r_N$, so expectation passes to the series limit. Centering removes the linear term, and for every $k\ge 2$, $\mathrm{\mid }\mathbb{E}[X_i^k]\mathrm{\mid }\le b^{k-2}{v}_i$ by [F1] and monotonicity. Also $k!\ge 2\cdot 3^{k-2}$ for $k\ge 2$: equality holds at $k=2,3$, and each subsequent factorial factor is at least $3$. Hence the geometric-series bound and $1+x\le e^x$ from [F5] give $\mathbb{E}{e}^{\lambda X_i}\le 1+{\lambda }^2{v}_i\mathrm{/}[2(1-\mathrm{\mid }\lambda \mathrm{\mid }b\mathrm{/}3)]\le \exp ({\lambda }^2{v}_i\mathrm{/}[2(1-\mathrm{\mid }\lambda \mathrm{\mid }b\mathrm{/}3)])$.

Let $S={\sum }_{i=1}^n{X}_i$, a measurable real random variable by [F11]. By the addition formula [F10], $e^{\lambda S}={\prod }_i{e}^{\lambda X_i}$; independence [F8] and factorization [F2], applied to the nonnegative Borel functions established in step 1.2, give $\mathbb{E}{e}^{\lambda S}\le \exp ({\lambda }^{2}v\mathrm{/}[2(1-\lambda b\mathrm{/}3)])$ for $0<\lambda <3\mathrm{/}b$. Since $e^x$ is positive and increasing [F10], $S\ge t$ implies $e^{\lambda S}\ge e^{\lambda t}>0$, so [F3] and the reciprocal and addition formulas in [F10] give $\mathbb{P}(S\ge t)\le \exp (-\lambda t+{\lambda }^{2}v\mathrm{/}[2(1-\lambda b\mathrm{/}3)])$. Choose $\lambda =t\mathrm{/}(v+bt\mathrm{/}3)$; then $\lambda b\mathrm{/}3<1$ and direct simplification gives $\mathbb{P}(S\ge t)\le \exp (-t^2\mathrm{/}[2(v+bt\mathrm{/}3)])$.

For $0<\lambda <3\mathrm{/}b$, the bound in step 1.2 also holds at parameter $-\lambda$. By [F10], $e^{-\lambda S}={\prod }_i{e}^{-\lambda X_i}$; the original variables remain independent by [F8], and [F2] factors these nonnegative Borel functions, giving $\mathbb{E}{e}^{-\lambda S}\le \exp ({\lambda }^{2}v\mathrm{/}[2(1-\lambda b\mathrm{/}3)])$. Since $S\le -t$ implies $e^{-\lambda S}\ge e^{\lambda t}>0$, Markov [F3] and the same optimizing choice as in step 2.1 yield $\mathbb{P}(S\le -t)\le \exp (-t^2\mathrm{/}[2(v+bt\mathrm{/}3)])$. By [F7], the two one-sided bounds imply the displayed two-sided bound without asserting independence of the transformed variables $-X_i$.

Put $V_d=\mathrm{cont}({\bar{B}}_2(0,1))$. This number is finite by [F3] and positive by induction on $d$: $V_1=2$, and for $d\ge 2$ set $\alpha =(d-1)\mathrm{/}2>0$. On $[-1\mathrm{/}2,1\mathrm{/}2]$, $1-t^2\ge 3\mathrm{/}4$, so [F10] gives $(1-t^2{)}^{\alpha }\ge (3\mathrm{/}4{)}^{\alpha }>0$; on all of $[-1,1]$ this integrand is nonnegative. By [F11], splitting the integral at $-1\mathrm{/}2$ and $1\mathrm{/}2$ and comparing the middle part with the constant $(3\mathrm{/}4{)}^{\alpha }$ shows ${\int }_{-1}^1(1-t^2{)}^{\alpha }dt\ge (3\mathrm{/}4{)}^{\alpha }>0$. The volume recursion [F3] then gives $V_d>0$ from $V_{d-1}>0$.

Let $E=\{x_1,\dots ,x_N\}\subseteq S^{d-1}$ have pairwise distances greater than $ϵ$, and put $r=ϵ\mathrm{/}2$. The closed balls ${\bar{B}}_2(x_j,r)$ are pairwise disjoint: a point in two of them would, by the triangle inequality [F2], put the corresponding centers at distance at most $2r=ϵ$, contrary to the separation. Each small ball lies in ${\bar{B}}_2(0,1+r)$, since $\mathrm{\parallel }{x}_j{\mathrm{\parallel }}_2=1$ and [F2] gives $\mathrm{\parallel }y{\mathrm{\parallel }}_2\le \mathrm{\parallel }y-x_j{\mathrm{\parallel }}_2+\mathrm{\parallel }{x}_j{\mathrm{\parallel }}_2\le r+1$.

By scaling and translation invariance [F4, F5], every small ball in step 1.2 has content $r^d{V}_d$ and the large ball has content $(1+r{)}^d{V}_d$. Finite additivity [F6] and monotonicity of outer content from [F7] give $N{r}^d{V}_d\le (1+r{)}^d{V}_d$. Step 1.1 gives $V_d>0$, so cancellation and $r=ϵ\mathrm{/}2$ yield $N\le ((1+r)\mathrm{/}r{)}^d=(1+2\mathrm{/}ϵ{)}^d$. This also holds when $E$ is empty, for which $N=0$.

Choose an integer $M>(1+2\mathrm{/}ϵ{)}^d$ using [F8]. Let $K$ be the set of cardinalities of finite subsets of $S^{d-1}$ whose distinct points are more than $ϵ$ apart. The first coordinate unit vector shows $K$ is nonempty, and step 2.1 shows every member of $K$ is at most $(1+2\mathrm{/}ϵ{)}^d<M$. Thus $K$ is a nonempty subset of $\{0,1,\dots ,M\}$; [F9] gives a largest member $k\in K$, attained by a finite set $\mathcal{N}$ by the definition of $K$.

If some $u\in S^{d-1}$ were farther than $ϵ$ from every point of $\mathcal{N}$, adjoining $u$ would produce a finite set with pairwise distances greater than $ϵ$ and cardinality $k+1$, contradicting maximality in step 3.1. Thus $\mathcal{N}$ is an $ϵ$-net; step 2.1 gives its stated cardinality bound. This construction uses only a maximum in a finite set of possible cardinalities, not an axiom of choice.

By [F1] and [F2], the joint law of $(Z_1,\dots ,Z_n)$ is $\mu$. For $1\le i<n$, repeated application of [F4] gives a measurable version $H_i$ of the integral over the unrevealed coordinates; clause 3 of [F4] makes each such section-integral function integrable after assigning $0$ on its exceptional set. Set $H_0=\int fd\mu$ and $H_n=f$, which are integrable by the hypothesis. Let $M_i=H_i(Z_1,\dots ,Z_i)$. Then $M_i$ is integrable and ${\mathcal{F}}_i$-measurable by [F3], [F5], and the product-integral construction; [F6] identifies the expectation of each integrable $M_i$ with its Lebesgue integral.

Fix $i$. Fubini applied to $\mathrm{\mid }f\mathrm{\mid }$ gives a measurable full-measure set of prefixes $p=(x_1,\dots ,x_{i-1})$ for which the integral of $\mathrm{\mid }f(p,x_i,y)\mathrm{\mid }$ over ${\mu }_i\otimes {\mu }_{i+1:n}$ is finite. For such a prefix there is a coordinate value $x_i^0$ whose future-section integral is finite. The coordinate oscillation assumption gives $\mathrm{\mid }f(p,x_i,y)\mathrm{\mid }\le \mathrm{\mid }f(p,x_i^0,y)\mathrm{\mid }+c_i$ for every $x_i,y$, so every future section is integrable and $g_p(x_i):=\int f(p,x_i,y)d{\mu }_{i+1:n}(y)$ is finite. Integrating the same pointwise oscillation bound shows $\mathrm{\mid }{g}_p(x_i)-g_p(x_i^{\mathrm{\prime }})\mathrm{\mid }\le c_i$ for all $x_i,x_i^{\mathrm{\prime }}$.

If $A\in {\mathcal{F}}_{i-1}$, the definition of the sigma-algebra generated by the prefix writes $A=\{(Z_1,\dots ,Z_{i-1})\in C\}$ for a product-measurable $C$. By [F2], [F3], and [F4], integrating $H_i$ first over coordinate $i$ gives the same integral over $A$ as integrating $H_{i-1}$. Hence ${\int }_A(M_i-M_{i-1})d\mathbb{P}=0$.

On the full-measure prefix set from step 1.2, define $u_i(p):=\inf \{r\in \mathbb{R}:{\mu }_i(g_p>r)=0\}$ and ${\mathrm{\ell }}_i(p):=\sup \{r\in \mathbb{R}:{\mu }_i(g_p<r)=0\}$. They are finite because $g_p$ has finite range diameter at most $c_i$. The definitions and [F7] imply $g_p\le u_i(p)$ and $g_p\ge {\mathrm{\ell }}_i(p)$ almost everywhere: the set of almost-everywhere upper bounds is upward closed, so $u_i(p)+1\mathrm{/}m$ belongs to it for every integer $m\ge 1$ by the defining infimum; similarly ${\mathrm{\ell }}_i(p)-1\mathrm{/}m$ is an almost-everywhere lower bound. Thus the explicitly defined sets $\{g_p>u_i(p)+1\mathrm{/}m\}$ and $\{g_p<{\mathrm{\ell }}_i(p)-1\mathrm{/}m\}$ are null. Their countable union is null by [F7], and outside it letting $m\to \mathrm{\infty }$ gives both endpoint inequalities. These sequences and exceptional sets are specified by formulas, with no choice axiom. Also $u_i(p)-{\mathrm{\ell }}_i(p)\le c_i$: otherwise choose $\delta >0$ with $u_i(p)-{\mathrm{\ell }}_i(p)>c_i+2\delta$. The sets $\{g_p>u_i(p)-\delta \}$ and $\{g_p<{\mathrm{\ell }}_i(p)+\delta \}$ then both have positive ${\mu }_i$-measure by the definitions, so a point from each would violate the oscillation bound in step 1.2. For each $q\in \mathbb{R}$, $u_i(p)>q$ iff ${\mu }_i(g_p>q)>0$: if the latter holds, $\{g_p>q\}={\bigcup }_{m\ge 1}\{g_p>q+1\mathrm{/}m\}$ and [F7] give a positive-measure higher level, while $q<u_i(p)$ means $q$ is not an almost-everywhere upper bound. Similarly, ${\mathrm{\ell }}_i(p)<q$ iff ${\mu }_i(g_p<q)>0$, using $\{g_p<q\}={\bigcup }_{m\ge 1}\{g_p<q-1\mathrm{/}m\}$ and [F7]. Repeated Fubini in [F4] makes $(p,x_i)\mapsto g_p(x_i)$ measurable on this set; applying [F4] to the indicators of these level sets makes $p\mapsto {\mu }_i(g_p>q)$ and $p\mapsto {\mu }_i(g_p<q)$ measurable. Thus both endpoints are measurable.

Fubini gives $H_{i-1}(p)=\int g_p(x_i)d{\mu }_i(x_i)$ for almost every prefix, so ${\mathrm{\ell }}_i(p)\le H_{i-1}(p)\le u_i(p)$. Set $A_i(p)={\mathrm{\ell }}_i(p)-H_{i-1}(p)$ and $B_i(p)=u_i(p)-H_{i-1}(p)$ there, and set both to $0$ on the exceptional prefix set. These are finite measurable endpoints, contain $0$, and have width at most $c_i$. For ${\mu }_i$-almost every $x_i$, $g_p(x_i)-H_{i-1}(p)$ lies between them; by the product law this is $D_i$ almost surely. Together with step 2.1 this proves the asserted endpoint and event-integral properties for every $i$.

If $v=0$, then every ${\nu }_i^2=0$. Fix $i$ and choose ${\lambda }_i=1\mathrm{/}(2b_i)>0$. By [F1], both $\mathbb{E}{e}^{{\lambda }_i{X}_i}$ and $\mathbb{E}{e}^{-{\lambda }_i{X}_i}$ are at most $1$. The nonnegative random variable $Q_i=e^{{\lambda }_i{X}_i}+e^{-{\lambda }_i{X}_i}-2$ therefore has expectation at most $0$ by [F9]. By [F5], $Q_i=0$ only when $X_i=0$; [F6] gives $X_i=0$ almost surely. The finite sum $S$ is consequently $0$ almost surely by [F7].

Suppose $v>0$. By [F8], $b={\max }_i{b}_i$ exists and is positive. For each real $\theta$, the map $g_{\theta }(x)=e^{\theta x}$ is continuous: scalar multiplication is continuous since $\mathrm{\mid }\theta x-\theta y\mathrm{\mid }=\mathrm{\mid }\theta \mathrm{\mid }\mathrm{\mid }x-y\mathrm{\mid }$, and the exponential is continuous by [F5]. Its inverse images of open sets are open, so the collection of Borel sets with Borel preimage is a sigma-algebra containing the opens; hence $g_{\theta }$ is Borel by The Borel sigma-algebra of a topological space, For each Borel $B$, $\{g_{\theta }(X_i)\in B\}=X_i^{-1}(g_{\theta }^{-1}(B))$ is measurable. For $0\le \lambda \le 1\mathrm{/}b$, [F1] applies to every $X_i$. By [F5], $e^{\lambda S}={\prod }_i{e}^{\lambda X_i}$; independence [F2] and factorization [F3] give $\mathbb{E}{e}^{\lambda S}={\prod }_i\mathbb{E}{e}^{\lambda X_i}\le e^{{\lambda }^{2}v\mathrm{/}2}$.

For $t>0$ and $0<\lambda \le 1\mathrm{/}b$, [F10] makes $S$ a measurable real random variable, and $S\ge t$ implies $e^{\lambda S}\ge e^{\lambda t}>0$ by [F5]. Markov [F4], step 1.2, and the reciprocal and addition formulas in [F5] yield $\mathbb{P}(S\ge t)\le \exp (-\lambda t+{\lambda }^{2}v\mathrm{/}2)$. Choose $\lambda =\min \{t\mathrm{/}v,1\mathrm{/}b\}$. If $t\le v\mathrm{/}b$, the exponent is $-t^2\mathrm{/}(2v)$. If $t>v\mathrm{/}b$, it is $-t\mathrm{/}b+v\mathrm{/}(2b^2)\le -t\mathrm{/}(2b)$. Hence $\mathbb{P}(S\ge t)\le \exp [-\frac{1}{2}\min \{t^2\mathrm{/}v,t\mathrm{/}b\}]$.

For $0<\lambda \le 1\mathrm{/}b$, [F1] applies at parameter $-\lambda$ to every original $X_i$. By [F5], $e^{-\lambda S}={\prod }_i{e}^{-\lambda X_i}$; the original variables are independent by [F2], the functions $x\mapsto e^{-\lambda x}$ are nonnegative Borel by step 1.2, and factorization [F3] gives $\mathbb{E}{e}^{-\lambda S}\le e^{{\lambda }^{2}v\mathrm{/}2}$. Markov [F4] and the same optimizing choice as in step 2.1 yield the stated lower-tail bound. The finite union bound [F7] combines the tails; step 1.1 handles $v=0$. No independence assertion about the transformed variables is needed.