We have a set of $n^2$ bins, partitioned into two subsets: $A\neq\emptyset$ and $B\neq\emptyset$. Assume $n$ goes to infinity.


We continue to throw balls independently and uniformly at random into the $n^2$ bins, until $\log(n)$ balls are placed in bins belonging to subset $A$, then we stop. Let $m$ be the total number of balls we have thrown.


**Questions**: What is the minimum cardinality of $A$ such that  

$$\frac{m}{\log n}=\Theta\left(\frac{n^2}{|A|}\right)$$ holds w.h.p.?



Minimum number of balls to obtain accurate information about a bipartition of the bin set
This is a form of law of large numbers, and Chernoff's bound seems to work.


Denote $n\_A/n^2=p$, $\log n=k$, then we deal with Bernoulli i.i.d. $\xi\_1,\xi\_2,\dots$, $\xi\_i\in \{0,1\}$, $\mathbb{E} \xi\_i=p$, and $m$ is the minimal number for which $\xi\_1+\dots+\xi\_m\geqslant k$. 


Then the event $\{m\geqslant cp^{-1}k\}$ is just the event $\{\sum\_{j\leqslant cp^{-1}k} \xi\_j< k\}$. You ask when this is event has small probability for large enough constant $c$. I claim that it is so for any $p>0$.


The probability of this event equals the sum of coefficients of $x^j,j>k$, in the polynomial $F(x)=(px+(1-p))^{[cp^{-1}k]}$. The sum of such coefficients does not exceed $x^{-k}F(x)$ for any $x<1$. Take $x=(1-p)/(c-p)$ (this value is suggested by equating the derivative to 0.) We get $$(px+1-p)^{c/p}x^{-1}=(cx)^{c/p}x^{-1}=c\left(1-\frac{p(c-1)}{c-p}\right)^{c/p-1}\sim ce^{1-c}:=\rho<1$$
for fixed $c>1$. Thus $x^{-k}F(x)<\rho^k$ tends to 0.


