关于一阶泰勒级数推导边界的精度提升及广义生日问题中位数证明严谨化的技术问询

Hey everyone,

I just ran across a "proof" stating that the median for the generalized birthday problem is $C\sqrt{n}$. While the probability angle here is neat, my focus right now is on refining the calculus and asymptotic parts of the argument—this is less about probability itself and more about making the derivation rigorous. I have a rough proof outline, and I’m looking to tighten up the details.

Context #

Let’s start with the definition we’re working with:
$$p_r = (n)_r/n^r$$
Here, $(n)_r = n!/(n-r)!$, and this represents the probability that if we pick $r$ random people in a world with $n$ days (where $n \geq 365$), no two people share a birthday. We can also express $p_r$ as a product:
$$p_r = \left(1-\frac{1}{n}\right) \cdot \left(1-\frac{2}{n}\right) \cdot \dots \cdot \left(1-\frac{r-1}{n}\right)$$

My goal is to find the smallest $r$ such that $p_r > \frac{1}{2}$—this $r$ is the median time we’d expect to wait before a birthday collision occurs.

The "Proof" Outline (Based on Feller’s An Introduction to Probability Theory, Chapter 2, Section 2, near Formula 7.4) #

The argument starts with setting:
$$\frac{1}{2} = p_r$$
Then we take the negative logarithm of both sides...

Right now, the steps after taking the log feel a bit loose. I want to use first-order Taylor series approximations (or more precise asymptotic bounds) to make the inequalities and limits here rigorous. Does anyone have advice on how to refine this derivation to avoid hand-wavy approximations?

备注：内容来源于stack exchange，提问作者josinalvo