In the following paper I am slightly confused about the way they use a concentration inequality derived in Lemma A1. In Lemma A1, under the assumption that $(n ,p)$ satisfies $\log p/n^{1/4} \to 0$ as $p \to \infty$, we have the following statement:
For any $M>0$, there exists some constant $\rho_1>0$ such that
$$ P \left (X \ge \rho_1 \frac{\log^2p}{n^{1/2}}\right ) = O(p^{-M}). $$
Here, I am not writing what $X$ is as it is irrelevant to my question. Now, in another lemma (Lemma A2), the authors say the following:
Define the event $\Omega_n(s) := \{ X \le s \frac{\log^2p}{n^{1/2}} \le \frac{1}{2}\}$. For any $M>0$ it follows from Lemma A1 that there exists some constant $\rho_1 >0$ such that $P(\Omega_n(\rho_1)) \ge 1 - O(p^{-M})$.
Questions:
- Why is this true? It seems weird to me to be able to say that $\rho_1 \frac{\log^2p}{n^{1/2}} \le \frac{1}{2}$ without further assumptions. If I am understanding correctly, one first chooses $M$ and then we are guaranteed the existence of a constant $\rho_1$. So we have no control over $\rho_1$.
- Suppose that we have another concentration statement, e.g. Bernstein's inequality tells us that for $X_1,\dots, X_n$ independent random variables with $a_i \le X \le b_i$ almost surely for all $i$, and $c_i \le C$ for all $i$, then for any $\gamma \ge 1$, it holds with probability at least $1-e^{-2\gamma}$ that $$ \frac{1}{n} \sum_{i=1}^n X_i - E[X_1] \le \frac{2C\gamma}{3n} + \sqrt{\frac{2\gamma}{N} \sum_{i\le n}\text{Var}(X_i) }. $$ Can I always pick the parameters to say that the RHS of this bound is smaller than 1/2?