3
$\begingroup$

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.

  • 0
    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$`.)2012-08-18
  • 0
    I changed $k< to $k\ll n$.2012-08-18
  • 0
    @did, The two sampling processes are independent of each other.2012-08-19
  • 0
    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)$.2012-08-19
  • 0
    @did, Yes. Any ideas for how to do this?2012-08-19

1 Answers 1