# General question on approach to showing sample size required is $\Omega(\cdot)$

I was not able to find a similar question in the archives, so pardon this relatively elementary question if it has been asked before.

Let $E_n$ be some event that depends on the sample size $n$ and suppose we are looking for an upper bound on $n$ that guarantees $Pr(E_n)\geq 1-\varepsilon$ for some $\varepsilon\in(0,1)$. For example, if we are flipping a biased coin that lands heads with probability $p>.5$ and we define the event $E_n = \{\text{# of heads}>\frac{n}{2}\}$ then we are looking for $n\in O(f(p))$ since the sample size will be a function of the parameter $p$. One way I have seen this approached is to upper bound the probability of $E_n$ NOT occurring and then set this upper bound to be at most $\varepsilon$ and then solving such that we get $n\geq\text{ something involving } p$. My interpretation of this is that it is sufficient to have $n$ this big to guarantee $Pr(E_n)\geq 1-\varepsilon$ which is why it is an upper bound.

My question then is this: if my interpretation above is correct, is there an analogous approach to showing a lower bound for $n$ i.e. $n\in\Omega(g(p))$?

There is a difference between the two questions. Let $p_n$ be the number of heads in $n$ trials divided by $n$. We know that for large $n$, $p_n$ is very close to $p$; qualitatively this is the law of large numbers, and quantitatively this is the central limit theorem. This phenomenon is known as concentration. This is what you use to give an upper bound on $n$. In contrast, to give a lower bound on $n$ you need to show anti-concentration: that for small $n$, $p_n$ has a reasonable probability of being somewhat far from $p$. The techniques for showing anti-concentration are often more delicate.
• A couple of things: I believe $p_n$ should be close to $p$, and not necessarily 1/2, right? Secondly, I am not so much concerned with which inequalities to use to get the bounds, although those are likely very helpful in achieving the desired result. My question is more the general approach in a fashion I outlined in the example i.e. we set the probability of $E_n$ not happening to be at most $\varepsilon$ and solved for $n$. – guest Feb 23 '16 at 22:15
• Thanks, corrected. In terms of the approach, you either need a very good approximation for $\Pr[E_n]$ such as the one you get from Berry–Esseen, or you need to use an anti-concentration result. These are somewhat more delicate than concentration results, which is what you used for the upper bound on $n$. If you want to know whether your particular approach works, there is only one way to tell – try it out. – Yuval Filmus Feb 23 '16 at 22:49
• So in general the argument would be something like this: if $n\leq\text{ something involving } p$ then the probability that $E_n$ occurs is at MOST $1-\varepsilon$? The upper bound on the probability $E_n$ occurs can be derived using one of the inequalities you suggested. The interpretation is that it is necessary to have $n$ at least that big to have a chance to exceed the $1-\varepsilon$ threshold, although exceeding it is not guaranteed. Am I interpreting this correctly? – guest Feb 23 '16 at 23:00
• Definitely, but this is just a restatement of what you're trying to show. Another option is to show that the probability of $\overline{E_n}$ is at least $\epsilon$. This is an anti-concentration statement since it says that even though we expect $p_n$ to be close to $p>1/2$, it also happens with reasonable probability (i.e., at least $\epsilon$) that $p_n \leq 1/2$. – Yuval Filmus Feb 23 '16 at 23:03