Q18
Continuous Probability Distributions and Random Variables
Probability Inequality and Tail Bound Proof
View
We fix once and for all an integer $n$ which should be considered as being very large. For each pair $(x,y) \in \{0,1\}^n$ such that $x \neq y$, we fix an integer $j_n(x,y)$ whose existence is proved in question 17c. We say that $x$ is better than $y$ given $E^1, E^2, \ldots, E^T$ if $$\left|\frac{1}{T}\sum_{i=1}^T E^i_{j_n(x,y)} - \mathbb{E}\left[O_{j_n(x,y)}(x)\right]\right| < \left|\frac{1}{T}\sum_{i=1}^T E^i_{j_n(x,y)} - \mathbb{E}\left[O_{j_n(x,y)}(y)\right]\right|$$ We set $R_{n,T}(E^1, E^2, \ldots, E^T) = x$ if for all $y \neq x$, $x$ is better than $y$. If we cannot find such an $x$ we set $R_{n,T}(E^1, E^2, \ldots, E^T) = (0,0,\ldots,0)$.
Prove that if $T_n \geq e^{3\ln(n)n^{1/3}}$ then for all $x \in \{0,1\}^n$ and any sequence $$O^1(x), O^2(x), \ldots, O^{T_n}(x)$$ of $T_n$ random variables taking values in $\{0,1\}^n$ mutually independent with the same distribution as $O(x)$, we have $$\max_{x \in \{0,1\}^n} \mathbb{P}\left(R_{n,T_n}\left(O^1(x), O^2(x), \ldots, O^{T_n}(x)\right) \neq x\right) \leq u_n$$ where $(u_n)_{n \geq 1}$ is a sequence tending to 0 as $n$ tends to infinity.
Hint. One may start by writing, justifying it, that $$\mathbb{P}\left(R_{n,T}\left(O^1(x), O^2(x), \ldots, O^T(x)\right) \neq x\right) \leq \sum_{y \in \{0,1\}^n, y \neq x} \mathbb{P}\left(x \text{ is not better than } y \text{ given } O^1(x), O^2(x), \ldots, O^T(x)\right)$$