Bounded in probability ($o_{P}$)

Question

In Larry Wasserman's lecture notes on $o_{P}$ and $O_{P}$, I am not able to follow the derivation of the following example in page 9.

Consider $m$ coins with probabilities $p_{1}, \ldots ,p_{m}$. Then \begin{align*} \mathbb{P}(\max_{j} | \hat p_j - p_{j}| > \epsilon) & \le \sum_{j=1}^{m} \mathbb{P}(\hat p_{j} - p_{j}) \quad \text{(Union bound)} \\ & \le \sum_{j=1}^{m} 2 e^{-2 n \epsilon^{2}} \quad \text{(Hoeffding's inequality)} \\ & = 2 m e^{-2 n \epsilon^{2}} \end{align*}

I thought of concluding as $n \rightarrow \infty$ we get $\mathbb{P}(\max_{j} | \hat p_{j} - p_{j}| > \epsilon) \rightarrow 0$ and thus

$$ \max_{j} | \hat p_{j} - p_{j}| = o_{P} (1) $$

But the author bounds $m$ in terms of $n$ as follows:

Suppose $m \le e^{n^{\gamma}}$ where $0 \le \gamma \le 1$. Then \begin{align*} \mathbb{P}(\max_{j} | \hat p_{j} - p_{j}| > \epsilon) & \le 2 m e^{-2 n \epsilon^{2}} \\ & = 2 \exp(-(2 n \epsilon^{2} - \log m)) \\ & \le 2 \exp(-(2 n \epsilon^{2} - n^{\gamma})) \rightarrow 0 \end{align*}

Then he concludes $$ \max_{j} | \hat p_{j} - p_{j}| = o_{P} (1) $$

• The necessity of bounding $m \le e^{n^{\gamma}}$ is to avoid the cases where $m$ is large. Is my understanding correct?
• What happens if the $m \le e^{n^{\gamma}}$ is not satisfied? Can we prove it is not convergent?

Answer 1

Adjusting the notation of Wasserman's notes a little bit, I presume that the problem may be restated like this.

You have $Y^{(i)}_1,\dots,Y^{(i)}_n$ independent and identically distributed $Ber(p^{(i)})$, for $i=1,\dots,m$.

Define the estimates $\hat{p}^{(i)}_n=(1/n)\sum_{j=1}^n Y^{(i)}_j$, for $i=1,\dots,m$.

Then, using subadditivity and Hoeffding's inequality, we have

$$ P\left(\max_{1\leq i\leq m} |\hat{p}^{(i)}_n - p^{(i)}| > \epsilon\right) \leq \sum_{i=1}^m P\left(|\hat{p}^{(i)}_n - p^{(i)}| > \epsilon\right) \leq \sum_{i=1}^m 2 e^{-2n\epsilon^2} = 2 m e^{-2n\epsilon^2} = (*) \, . $$

Now, if the number of coins $m$ is fixed, it is clear that $(*)\to 0$, as $n\to\infty$, and we have the desired result: $\max_{1\leq i\leq m} |\hat{p}^{(i)}_n - p^{(i)}|=o_P(1)$.

But Wasserman seems to do more and allows $m$ to grow with $n$. In this case, as long as $m\leq e^{n^\gamma}$, for $0\leq\gamma<1$, we have $(*) \leq 2\exp(-(2n\epsilon^2-n^\gamma)) \to 0$, as $n\to\infty$, and we have the same conclusion of the former case.