QII.3
Discrete Random Variables
Probability Bounds and Inequalities for Discrete Variables
View
Let $$\gamma_0 = \frac{1}{4}$$ The purpose of the end of this part II is the proof by induction on the dimension $N$ of the property: for every convex set $A \subset Q^N$, $$\mathbb{P}(X \in A)\mathbb{E}\left[\exp\left(\gamma_0\, q(X,A)^2\right)\right] \leq 1,$$ for $\gamma = \gamma_0$. For $N$ a positive integer, we introduce the following induction hypothesis $H_N$: ``Let $(\Omega, \mathcal{A}, \mathbb{P})$ be a probability space. Let $N$ random variables $X_1, \ldots, X_N$ taking values in a finite set, independent and identically distributed, satisfying $\mathbb{P}(|X_n| \leq K) = 1$, and let $X = (X_i)_{1 \leq i \leq N}$ be the random vector with components $X_1, \ldots, X_N$. Then (53) is verified for $\gamma = \gamma_0 = \frac{1}{4}$''.
II.3.a) We consider the case $N = 1$. Prove that (53) is satisfied when $\gamma \leq \ln(2)$, and thus for $\gamma = \gamma_0$.
We now assume $N > 1$, and we fix $A \subset Q^N$ convex. We adopt the following notations: we decompose $$x = (\bar{x}, x_N) \quad \text{with} \quad \bar{x} = (x_i)_{1 \leq i \leq N-1} \in \mathbb{R}^{N-1}.$$ If $A \subset \mathbb{R}^N$ and $\theta \in \mathbb{R}$, we denote $$A_\theta := \left\{b \in \mathbb{R}^{N-1}; (b, \theta) \in A\right\}$$ the section of $A$ at level $\theta$. We also denote $$\bar{A} := \left\{\bar{a} \in \mathbb{R}^{N-1}; \exists \theta \in \mathbb{R}, (\bar{a}, \theta) \in A\right\}$$ the projection of $A$ onto $\mathbb{R}^{N-1}$.
II.3.b) Let $x \in Q^N$. Let $A \subset Q^N$ such that $A_{x_N}$ is non-empty. Let $\bar{z} \in P^{N-1}$. Prove that $$\bar{z} \in P_{A_{x_N}}(\bar{x}) \Longrightarrow (\bar{z}, 0) \in P_A(x)$$ and $$\bar{z} \in P_{\bar{A}}(\bar{x}) \Longrightarrow (\bar{z}, 1) \in P_A(x)$$
II.3.c) Prove that, for all $\lambda \in [0,1]$, we have $$q(x, A)^2 \leq (1-\lambda)^2 + \lambda\, q(\bar{x}, A_{x_N})^2 + (1-\lambda)\, q(\bar{x}, \bar{A})^2.$$
We fix $x_N \in \mathbb{R}$ such that $\mathbb{P}(X_N = x_N) > 0$ and we consider the probability $$\overline{\mathbb{P}}(B) := \mathbb{P}(B \mid X_N = x_N) = \frac{\mathbb{P}(B \cap \{X_N = x_N\})}{\mathbb{P}(X_N = x_N)} \quad \text{for } B \in \mathcal{A},$$ as well as the associated expectation $$\overline{\mathbb{E}}[Z] := \frac{1}{\mathbb{P}(X_N = x_N)} \mathbb{E}\left[Z\, \mathbf{1}_{\{X_N = x_N\}}\right]$$ for any random variable $Z$.
II.3.d) Assuming the induction hypothesis $H_{N-1}$, prove $$\overline{\mathbb{P}}(\bar{X} \in \bar{A})\, \overline{\mathbb{E}}\left[\exp\left(\gamma_0\, q(X,A)^2\right)\right] \leq e^{\gamma_0}$$ and justify that, for all $\lambda \in [0,1]$, we have $$\overline{\mathbb{P}}(\bar{X} \in A_{x_N})^\lambda\, \overline{\mathbb{P}}(\bar{X} \in \bar{A})^{1-\lambda}\, \overline{\mathbb{E}}\left[\exp\left(\gamma_0\, q(X,A)^2\right)\right] \leq e^{\gamma_0(1-\lambda)^2}.$$
Hint: you may assume H\"older's inequality: $$\overline{\mathbb{E}}\left[e^{\lambda Y} e^{(1-\lambda)Z}\right] \leq \left\{\overline{\mathbb{E}}\left[e^Y\right]\right\}^\lambda \left\{\overline{\mathbb{E}}\left[e^Z\right]\right\}^{(1-\lambda)}$$ for $\lambda \in [0,1]$ and $Y, Z$ random variables.
II.3.e) We assume $$\overline{\mathbb{P}}(\bar{X} \in \bar{A}) > 0,$$ and we define $$r = \frac{\overline{\mathbb{P}}(\bar{X} \in A_{x_N})}{\overline{\mathbb{P}}(\bar{X} \in \bar{A})}$$ Prove that $$r^\lambda e^{-\gamma_0(1-\lambda)^2}\, \overline{\mathbb{P}}(\bar{X} \in \bar{A})\, \overline{\mathbb{E}}\left[\exp\left(\gamma_0\, q(X,A)^2\right)\right] \leq 1.$$
II.3.f) We provisionally admit the following inequality: for all $\gamma \in [0, \gamma_0]$, for all $r \in ]0,1]$, $$\frac{1}{2-r} \leq \sup_{\lambda \in [0,1]} r^\lambda e^{-\gamma(1-\lambda)^2}$$ Justify that $$\overline{\mathbb{P}}(\bar{X} \in \bar{A})\, \overline{\mathbb{E}}\left[\exp\left(\gamma_0\, q(X,A)^2\right)\right] \leq (2 - r).$$ We shall distinguish the cases $\overline{\mathbb{P}}(\bar{X} \in A_{x_N}) > 0$ and $\overline{\mathbb{P}}(\bar{X} \in A_{x_N}) = 0$.
II.3.g) Prove that $$\mathbb{P}(X \in A)\, \mathbb{E}\left[\exp\left(\gamma_0\, q(X,A)^2\right) \mathbf{1}_{\{X_N = x_N\}}\right] \leq R(2-r)\, \mathbb{P}(X_N = x_N),$$ where $$R = \frac{\mathbb{P}(X \in A)}{\mathbb{P}(\bar{X} \in \bar{A})}$$
II.3.h) Prove that $$\mathbb{P}(X \in A)\, \mathbb{E}\left[\exp\left(\gamma_0\, q(X,A)^2\right)\right] \leq R(2-R),$$ where $R$ is defined in (72), then prove (53) and conclude the induction $H_{N-1} \Rightarrow H_N$. You should take care to account for the case where (66) is not verified.
II.3.i) Justify (69): for all $\gamma \in [0, \gamma_0]$, for all $r \in ]0,1]$, $$\frac{1}{2-r} \leq \sup_{\lambda \in [0,1]} r^\lambda e^{-\gamma(1-\lambda)^2}$$