Probability of hitting a number Consider a set $S$ of $N$ numbers. Fix a collection $T$ of $N^{\frac{1}{2}}$ numbers. With every trial, we have the freedom to choose $N^{\frac{2}{3}}$ of them at a time without overlapping. My questions are the following.
What is the probability that a given trial will pick atleast one number from the subset $T$?
In general, how many trials should one expect to make before we choose a number from the subset $T$ of $N^{\frac{1}{2}}$ numbers? 
 A: The expected size of the intersection is $N^{1/2} \cdot N^{2/3} / N = N^{1/6}$, and this suggests that it is very likely that you will pick at least one number from the subset $T$. The probability that you will not pick any number from the subset $T$ is exactly
$$\frac{\binom{N-N^{1/2}}{N^{2/3}}}{\binom{N}{N^{2/3}}}, $$
which you can estimate to your heart's content using Stirling's approximation:
$$
\begin{align*}
\log \frac{\binom{N-N^{1/2}}{N^{2/3}}}{\binom{N}{N^{2/3}}} &= 
(N-N^{1/2}) \log (N-N^{1/2}) - (N-N^{1/2}-N^{2/3}) \log (N-N^{1/2}-N^{2/3})
\\ &- N\log N + (N-N^{2/3}) \log (N-N^{2/3}) \pm O(\log N) \\ &=
N(1-N^{-1/2}) \log N (1 - N^{-1/2} - O(N^{-1})) \\ &-
N(1-N^{-1/2}-N^{-1/3}) \log N (1-N^{-1/2}-N^{-1/3}-\tfrac{1}{2}N^{-2/3}-N^{-5/6}-O(N^{-1})) \\ &-
N\log N + N(1-N^{-1/3}) \log N (1-N^{-1/3}-\tfrac{1}{2}N^{-2/3}-O(N^{-1})) \pm O(\log N) \\ &=
N\log N (-\tfrac{1}{2} N^{-2/3} - N^{-5/6}) \pm O(\log N) \\ &=
(-\tfrac{1}{2} N^{1/3} - N^{1/6} \pm O(1)) \log N.
\end{align*}
$$
We conclude that the probability is
$$
N^{-(1/2)N^{1/3}-N^{1/6} \pm O(1)},
$$
which is very small. With more effort (using more terms in Stirling's approximation and in the Taylor expansions) we could determine the constant in the exponent, or even get subconstant terms there. A decent CAS should be able to do this calculation automatically, but unfortunately I couldn't figure out how to convince Wolfram alpha to help here.
Alternatively, you can use Chernoff's bound for negatively dependent random variables. The idea is to have $X_i$ be an indicator for the event that the $i$th member of the subset lies in $T$. While the sequence $X_1,\ldots,X_{N^{2/3}}$ is perhaps not negatively dependent (I'm not sure), the linked article shows that if you sample $N^{2/3}$ points with replacement, then the sequence $Y_{i,j}$ is negatively dependent, where $Y_{i,j}$ is the indicator for the event that the $i$th samples point equals the $j$th point in $T$. Sampling with replacement only makes it easier to avoid $T$ (this can be argued formally using coupling, for example: whenever you sample the same point twice, in the coupled copy sample a new point; this only increases your chance to hit $T$).
One version of Chernoff's bound that is easy to state is:
$$ \Pr[\sum_{ij} Y_{ij} \leq (1-\delta) \mu] \leq e^{-\delta^2 \mu/2}, $$
where $\mu$ is the expected value of the sum, in our case $N^{1/6}$. Taking $\delta = 1$, we deduce that the probability that we miss $T$ is at most $e^{-N^{1/3}/2}$, which is very small. This bound is almost as good as the one we computed explicitly: the difference is only a $\log N$ factor in the exponent.
If the success probability is $p$, then the expected number of trials is $1/p$, since this is a geometric random variable. Since $p \approx 1$, also $1/p \approx 1$.
