Suppose we have a set of $N$ numbers. At any given trial we can randomly choose $N^{1-a}$ of the numbers where $a\in(0,1)$. We replace the numbers back.
How many trials does it take in average case to have chosen all numbers?
If we use only $m$ trials what is the probability that we will leave out only $N^{b}$ of the set not covered where $b\in(0,1)$ holds?
Let $Z(m)$ be the number of uncovered (= not chosen) sites after $m$ trials. First, we have $$\mathbb{E} Z(N^a(1+\epsilon)\ln N)=N\times(1-N^{-a})^{N^a(1+\epsilon)\ln N}\approx N^{-\epsilon},$$ so you can use Chebyshev inequality to bound $\mathbb{P}[Z(N^a(1+\epsilon)\ln N)\geq 1]$ from above.
Then, for the result in the other direction, use the Paley-Zigmund inequality, $\mathbb{P}[Z>0]\geq (\mathbb{E}Z)^2/(\mathbb{E}Z^2)$. Clearly, $\mathbb{E} Z(N^a(1-\epsilon)\ln N)\approx N^{\epsilon}$, and you write $Z(N^a(1-\epsilon)\ln N)$ as a sum of indicators, square it etc., to prove that $\mathbb{E} [Z(N^a(1-\epsilon)\ln N)]^2$ is $N^{2\epsilon}+$terms of smaller order.
So, this way you can obtain that $N^a(1+\epsilon)\ln N$ trials will be enough (to choose everybody at least once) with probability at least $1-O(N^{-\epsilon})$, and $N^a(1-\epsilon)\ln N$ trials will be not enough also with probability at least $1-O(N^{-\epsilon})$.
