4
$\begingroup$

Working on the generalized birthday problem, where you draw with replacement from $\{1,2,3, \ldots,d\}$ and look for the number of draws $n$ for which you have greater than $1/2$ chance of a match I said

$\frac{d!}{d^d(d-n)!} \lt \frac{1}{2}$

Using Stirling's approximation

$\frac{d^d \exp (d-n)} {\exp(d) d^n (d-n)^{(d-n)}} \lt \frac{1}{2}$
$\frac{1}{\exp(n)}(1+\frac{n}{d-n})^{(d-n)}\lt \frac{1}{2}$

Taking logs and using the Taylor expansion

$(d-n) \ln(1+\frac{n}{d-n})-n \lt -\ln (2)$
$(d-n) (\frac{n}{d-n}-\frac{n^2}{2(d-n)^2})\lt -\ln(2)$
$n^2>2 \ln(2) (d-n)$

Ignoring the n in comparison with d in the last term, because if we wanted it we should keep the next term in the expansion of ln, we get

$n>\sqrt{2 \ln (2) d}$ which agrees with the published result


This is fine, but like much math writing it obscures the difficulties of finding the solution. Before taking logs I wanted to say $(1+\frac{n}{d-n})^{(d-n)} \rightarrow \exp(n)$ but that left me with the unhelpful $1 \lt \frac{1}{2}$. Seeing what happened after taking logs, I need the next term in the expansion as the first one cancels. I know how to expand a Taylor series as far as I want, but I don't know what the next term in this one is.

2 Answers 2

5

$$\left(1+\frac{x}{n}\right)^{n}=e^x\left(1-\frac{x^2}{2n}+\frac{x^3(8+3x)}{24n^2}+\cdots\right).$$

This note might be helpful.

  • 0
    Thanks. Using the first two terms gets me close, but doesn't turn the 1/2 to ln(2).2010-11-03
  • 0
    Hi @AndreyRekalo , broken link :(2018-06-30
4

$$\rm\quad \bigg(1+\frac{a}n\bigg)^{\:n}\ =\ e^{n\log(1+a/n)}\ =\ e^a\ e^{n\log(1+a/n)-a}\ $$

$$\rm n\:\log \bigg(1+\frac{a}n\bigg)-a\ =\ \frac{a^2}{2\:n} + \frac{a^3}{3\:n^2} +\: \cdots $$

$$\rm e^{n\log(1+a/n)-a}\ =\ 1 - \frac{a^2}{2\:n} + \frac{3a^4 + 8a^3}{24\: n^2} +\: \cdots $$