Bounded in probability ($o_{P}$)

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?
• What is $\hat{p}$? – Macro Jan 31 '12 at 2:38
• @Macro $\hat{p}$ is the estimate of $p$ – Anand Jan 31 '12 at 2:49
• Wow, sorry about that. I tried to make a few edits, but the $\LaTeX$ appeared to get seriously confused. I think the tweaks they've made to this recently has introduced some bugs. – cardinal Jan 31 '12 at 2:50
• @cardinal No problem. – Anand Jan 31 '12 at 2:55
• Your question (and the handout) misses the connection between $n$ and $m$. Is this the number of iid observations of the $m$ coins? Or the total number of observations? If $m$ is fixed, this shows that the max is a $o_P(1)$, not a $O_P(1)$. If $m$ is not fixed, we need $m$ to increase slowly enough to get $o_P(1)$. – Xi'an Jan 31 '12 at 12:16

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.