# Growth of number of distinct elements

Let $A_k$ be a random variable which represents the number of distinct integers seen after sampling $k$ independently and uniformly at random from the range $1, \dots, n$. Let $B_k$ be a random variable which represents the number of distinct integers seen after sampling $k$ independently and uniformly at random from the range $1, \dots, n^2$.

We know that $E(A_k) = n(1-(1-1/n)^k)$ and $E(B_k) = n^2(1-(1-1/n^2)^k)$. We also know that for $k \ll n$ both grow almost linearly and hence almost identically in $k$ but for $k \geq n$ they behave completely differently.

What is the asymptotic growth of the expected value of the ratio of $A_k$ and $B_k$? That is I am looking for an asymptotic expression for $E(B_k/A_k)$ assuming $n$ is large and especially a formula that captures the difference between the small and large $k$ phenomena.

My intuition is that $E(B_k/A_k)$ looks like $E(k/A_k)$ when $k < n\log{n}$ and like $E(B_k/n)$ otherwise. For large $n$ we also have that $E(A_k) \sim n(1-e^{-k/n})$ and $E(B_k) \sim n^2(1-e^{-k/n^2})$ it seems.

-
The answer depends on the joint distribution of $(A_k,B_k)$, hence you might want to describe it. (Unrelated: please use $k\ll n$.) –  Did Aug 18 '12 at 20:48
I changed $k<<n$ to $k\ll n$. –  Michael Hardy Aug 18 '12 at 21:10
@did, The two sampling processes are independent of each other. –  Lipoff Aug 19 '12 at 7:32
Then $E(B_k/A_k)=E(B_k)E(1/A_k)$ and one knows $E(B_k)$ hence the problem is to compute/estimate $E(1/A_k)$. –  Did Aug 19 '12 at 9:32
@did, Yes. Any ideas for how to do this? –  Lipoff Aug 19 '12 at 19:07