Approximating $f(n,k,c) = \prod_{i=0}^{k-1} \frac{n-ic}{n-i}.$

Question

Problem:

For integers $n>k$ and real $c\in [0,1]$, let $$f(n,k,c) = \prod_{i=0}^{k-1} \frac{n-ic}{n-i}.$$

How well can we approximate $f(n,k,c)$ for fixed $c$ and sufficiently large $n,k$? I'm particularly interested when $c=1/2$.

Motivation:

If we have $k$ i.i.d. random variables, $X_i$, which each uniformly the integers in $[1,n]$, then by a basic counting argument, we get that the probability they are all distinct is $n!/(n-k)! n^{-k}$.

Another way to see this is to note that, given $X_1, \dots X_i$ are all distinct from one another, the probability $X_{i+1}$ is also distinct from these first $i$ elements is $(n-i)/n$. Thus the probability they are exactly distinct is: $$ \prod_{i=0}^{k-1} \frac{n-i}n = n!/(n-k)! n^{-k}.$$

I had similar problem where instead I want to calculate: $$ \prod_{i=0}^{k-1} \frac{n-ic}n $$ for values $c \approx 1/2$.

Answer 1

It is easy to prove that $\ln \frac{1 - cx}{1-x} \ge (1-c)x$ for $0\le x < 1$. Thus, we have \begin{align} f(n,k,c) &= \mathrm{exp}\left(\sum_{i=0}^{k-1} \ln \frac{1 - c\frac{i}{n}}{1-\frac{i}{n}} \right)\\ &\ge \mathrm{exp}\left(\sum_{i=0}^{k-1} (1-c)\frac{i}{n} \right)\\ &= \mathrm{exp}\left( \frac{k(k-1)(1-c)}{2n}\right). \end{align} By using $\ln \frac{1 - cx}{1-x} \ge (1-c)x + \frac{1-c^2}{2}x^2$ for $0\le x < 1$, we can get a better lower bound. Omitted.

Update: When $\frac{k}{n}$ is near $1$, the previous lower bounds are not good. Here I give another lower bound.

We have \begin{align} &f(n, k, c)\\ =\ & \frac{n^k (n-k)!}{n!}\prod_{i=0}^{k-1} \left(1 - c\frac{i}{n}\right)\\ =\ & \frac{n^k (n-k)!}{n!}\mathrm{exp}\left(\sum_{i=0}^{k-1} \ln \left(1 - c\frac{i}{n}\right)\right)\\ \ge\ & \sqrt{2\pi} \left(1-\frac{k}{n}\right)^{n-k+\frac{1}{2}}\mathrm{e}^{k-1} \mathrm{exp}\left(\sum_{i=0}^{k-1} \left( -c\frac{i}{n} + (\ln (1-c) + c)\frac{i^2}{n^2} \right)\right)\\ =\ & \sqrt{2\pi} \left(1-\frac{k}{n}\right)^{n-k+\frac{1}{2}}\mathrm{e}^{k-1} \mathrm{exp}\left(\frac{k(k-1)[(2k-1)\ln(1-c) + (2k-3n-1)c]}{6n^2}\right) \end{align} where we have used: i) $\ln (1-cx) \ge -cx + (\ln (1-c) + c)x^2$ for $0\le x \le 1$; ii) Stirling's formula $\sqrt{2\pi} m^{m+\frac{1}{2}}\mathrm{e}^{-m} \le m! \le \mathrm{e} m^{m+\frac{1}{2}}\mathrm{e}^{-m}$.

Answer 2

Upper bound: recall for $x \ge 0$, $\ln(1+x)\le x$. Thus $$f(n,k,c) \le \exp \left( \sum_{i=0}^{k-1} \frac{(1-c)i}{n-i}\right)\le \exp\left( \frac{(1-c)k(k-1)}{2(n-k)}\right).$$ However, I am most interested in a lower bound.