Interpreting a concentration inequality

Question

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:

1. 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$.
2. 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?

Answer 1

The definition of $\Omega_n(s)$ should be understood as $$\Omega_n(s)=\begin{cases} \{X\leq \frac{s \log^2 p}{n^{1/2}} \} &\text{if } \frac{s \log^2 p}{n^{1/2}} \leq \frac 12,\\ \emptyset &\text{if } \frac{s \log^2 p}{n^{1/2}} > \frac 12. \end{cases}$$

$p$ is best seen as an implicit sequence indexed by $n$ (so that you can consider limits on $n$ only).
By the regime assumption, for fixed $s$, $\frac{s \log^2 p}{n^{1/2}}\xrightarrow[n\to \infty]{} 0$, thus for $n$ large enough we have eventually $\Omega_n(s) = \{X\leq \frac{s \log^2 p}{n^{1/2}} \}$.

Fix some $M>0$. By their lemma, there exists $\rho_1$ such that $$P(X\leq \frac{\rho_1 \log^2 p}{n^{1/2}})\geq 1-O(p^{-M}).$$ For $n$ large enough, we have $\Omega_n(\rho_1) = \{X\leq \frac{\rho_1 \log^2 p}{n^{1/2}} \}$, thus for $n$ large enough, $$P(\Omega_n(\rho_1)) \geq 1-O(p^{-M}).$$