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 '12 at 2:38
  • $\begingroup$ @Macro $\hat{p}$ is the estimate of $p$ $\endgroup$ – Anand Jan 31 '12 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 '12 at 2:50
  • $\begingroup$ @cardinal No problem. $\endgroup$ – Anand Jan 31 '12 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 '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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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