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?
  • $\begingroup$ What is $\hat{p}$? $\endgroup$
    – Macro
    Jan 31, 2012 at 2:38
  • $\begingroup$ @Macro $\hat{p}$ is the estimate of $p$ $\endgroup$
    – Anand
    Jan 31, 2012 at 2:49
  • $\begingroup$ 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. $\endgroup$
    – cardinal
    Jan 31, 2012 at 2:50
  • $\begingroup$ @cardinal No problem. $\endgroup$
    – Anand
    Jan 31, 2012 at 2:55
  • 1
    $\begingroup$ 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)$. $\endgroup$
    – Xi'an
    Jan 31, 2012 at 12:16

1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.