Find the number of terms of a product to make it 1/2

Question

How to find $k$ such that:

$$\prod_{j=1}^{k-1} \Big(1 - \frac jn \Big) = \frac 12$$

?

According to a book I'm reading, this should hold approximatively when $k \approx \sqrt{n}$ (no proof is given).

Indeed, it seems to work. The equation is equivalent to

$$\begin{align}\sum_{j=1}^{k-1} \log\Big(1 - \frac jn \Big) = - \log(2)\end{align}$$

i.e.

$$\begin{align}\sum_{j=1}^{k-1} \Big( \frac {-j}n + O\Big(\frac {k^2}{n^2}\Big) \Big) = - \log(2) \end{align}$$

or

$$\frac {1}{n}\begin{align}\sum_{j=1}^{k-1} j + O\Big(\frac {k^3}{n^2}\Big) = \log(2) \end{align}$$

Let's suppose $k^3 = o(n^2)$. Then

$$\frac 1 n \frac{k(k-1)}{2} + o(1) = \log(2)$$

and this proves that:

$$\frac{k^2}{n} + O\Big(\frac k n\Big) + o(1) = 2 \log(2)$$

This means that $k$ should be taken around $c \sqrt{n}$, with $c = \sqrt{2\log2}$.

This seems to work, but is there a cleaner proof that leads to a more precise result?

---

Application: If $k$ people choose a random number in $\{1, 2, \cdots, n \}$, then the probability of at least two people having chosen the same number (i.e. probability of a "collision") is $1/2$, when $k = c \sqrt{n}$.
See birthday problem.

Answer 1

Starting with $\sum_{j=1}^{k-1} -\log\Big(1 - \frac jn \Big) = \log(2) $ we can use, for $0< x < 1$, $-\log(1-x) =\sum_{m=1}^{\infty} \dfrac{x^m}{m} $.

Then, using the first $h$ terms, $-\log(1-x) \gt\sum_{m=1}^{h} \dfrac{x^m}{m} $.

Looking at the remaining terms, $\sum_{m=h+1}^{\infty} \dfrac{x^m}{m} \lt \sum_{m=h+1}^{\infty} \dfrac{x^m}{h+1} =\dfrac1{h+1} \sum_{m=h+1}^{\infty}x^m =\dfrac{x^{h+1}}{(h+1)(1-x)} $ so that $-\log(1-x) \lt\sum_{m=1}^{h} \dfrac{x^m}{m}+\dfrac{x^{h+1}}{(h+1)(1-x)} $.

Setting $h=1$, $x < -\log(1-x) \lt x+\dfrac{x^{2}}{2(1-x)} $.

Using the lower bound, if $n > k$, $\log(2) \gt \sum_{j=1}^{k-1} j/n =\dfrac{k(k-1)}{2n} $.

Using the upper bound, if $n > k$,

$\begin{array}\\ \log(2) &\lt \sum_{j=1}^{k-1} (j/n+\dfrac{j^2/n^2}{2(1-j/n)})\\ &<\dfrac{k(k-1)}{2n}+\sum_{j=1}^{k-1}\dfrac{j^2/n^2}{2(1-k/n)}\\ &=\dfrac{k(k-1)}{2n}+\dfrac{1}{2n(n-k)}\sum_{j=1}^{k-1}j^2\\ &=\dfrac{k(k-1)}{2n}+\dfrac{1}{2n(n-k)}\dfrac{(k-1)k(2k-1)}{6}\\ &<\dfrac{k(k-1)}{2n}+\dfrac{(k-1)k^2}{3n(n-k)}\\ &=\dfrac{k(k-1)}{2n}(1+\dfrac{2k}{3(n-k)})\\ \end{array} $

so that $1 \lt \dfrac{2n\log(2)}{k(k-1)} \lt 1+\dfrac{2k}{3(n-k)} $.

From the first, $n > \dfrac{k(k-1)}{2\log(2)} > \dfrac{k(k-1)}{2} $.

From the second, $\dfrac{k}{n-k} \lt \dfrac{k}{k(k-1)/2-k} = \dfrac{1}{(k-1)/2-1} = \dfrac{1}{(k-3)/2} = \dfrac{2}{k-3} $ so $ \dfrac{2n\log(2)}{k(k-1)} \lt 1+\dfrac23\dfrac{2}{k-3} = 1+\dfrac{4}{3(k-3)} $.

Therefore $\dfrac{k(k-1)}{2\log(2)} \lt n \lt \dfrac{k(k-1)}{2\log(2)}+\dfrac{2k(k-1)}{3\log(2)(k-3)} $.

In particular, $n =\dfrac{k^2}{2\log(2)}+O(k) $ or $k =\sqrt{2n\log(2)}+O(1) $.

Answer 2

In addition to @martycohen's accepted answer, I share (for future reference) my failing attempt to prove something valid for all $0 < \alpha < 1$, instead of $1/2$.

For each $0 < \alpha < 1$ fixed, we want to find $k=k(n)$ such that:

$$P(k,n):=\prod_{j=0}^{k−1}\Big(1−\frac jn\Big)=\alpha.$$

This is equivalent to $$\sum_{j=0}^{k−1}- \log\Big(1−\frac jn\Big)=\log(1/\alpha).$$

Since $x \leq -\log (1-x)$ on $[0,1]$ (easy to prove) , we have:

$$\frac 1 n \sum_{j=0}^{k-1} j \leq \log(1/\alpha)$$

i.e.

$$\frac {k(k-1)}{2n} \leq \log(1/\alpha)$$

A simple computation (root of polynomial in $k$ of degree $2$) shows that a necessary condition is that $k$ has to be chosen:

$$k \leq 1/2 + 1/2 \sqrt{1 + 8 \log(1/\alpha) n}.$$

If $\alpha$ is fixed, and $n$ is large enough, we can assume $k \leq n /2$, then the terms $j/n$ in the following sum will be: $j/n < k/n \leq 1/2$.

[Not very good here because we would like an estimate uniform for all $0 < \alpha < 1$, and $n \geq 1$, i.e. without requiring "$n$ large enough"]

Now we can use $-\log(1-x) \leq x + x^2$ which is true on $[0, 1/2]$ (*) (easy to prove).

Then:

$$\log(1/\alpha) = \sum_{j=0}^{k−1}- \log\Big(1−\frac jn\Big) \leq \frac 1 n \sum_{j=0}^{k-1} j + \frac 1 {n^2} \sum_{j=0}^{k-1} j^2$$

i.e.

$$\log(1/\alpha) \leq \frac {k(k-1)}{2 n} + \frac {k(k-1)(2k-1)}{6 n^2}$$

Here I cannot get a satisfying upper bound because $k$'s upper bound (see necessary condition before) involves $\sqrt{\log(1/\alpha)}$ which can be arbitrarily large if $\alpha$ is very close to $0$.

To be continued!

---

Note: (*) I used this on $[0, 1/2]$ because it's hopeless to get an upper bound on $[0,1]$ as a polynomial because the function $f(x):=-\log(1-x)$ tends to $+\infty$ when $x$ approaches $1$:

That's why @martycohen's upper bound $−\log(1−x)< x + x^2 / (2(1−x))$ is more appropriate because valid on $[0,1[$.