Ramanujan Q-distribution:

$$\begin{aligned} \frac{N!}{(N-k)!N^k} &= \exp(\color{teal}{\ln N!} - \color{blue}{\ln(N-k)!} -k \ln N) \\ \end{aligned}$$

As we saw earlier, by Stirling's approximation,

$$\begin{aligned} \ln N! &= (N + \frac{1}{2}) \ln{N} - N + \ln{\sqrt{2\pi}} + O(\frac{1}{N}) \\ \end{aligned}$$

Therefore,

$$\begin{aligned} \frac{N!}{(N-k)!N^k} &= \exp\left( \color{teal}{(N + \frac{1}{2}) \ln{N} - N + \ln{\sqrt{2\pi}} + O(\frac{1}{N})} - \color{blue}{\left((N - k + \frac{1}{2}) \ln{(N-k)} - (N - k) + \ln{\sqrt{2\pi}} + O(\frac{1}{N-k})\right)} - k \ln N \right) \\ &= \exp\left( (N + \frac{1}{2}) \ln{N} - N + \ln{\sqrt{2\pi}} - (N - k + \frac{1}{2}) \ln{(N-k)} + N - k - \ln{\sqrt{2\pi}} - k \ln N + O(\frac{k}{N(N-k)}) \right) \\ &= \exp\left( (N + \frac{1}{2}) \ln{N} - (N - k + \frac{1}{2}) \ln{(N-k)} - k - k \ln N + O(\frac{k}{N}) \right) \\ &= \exp\left( (N + \frac{1}{2}) \ln{N} - (N - k + \frac{1}{2}) \ln{N(1-\frac{k}{N})} - k - k \ln N + O(\frac{k}{N}) \right) \\ &= \exp\left( (N + \frac{1}{2}) \ln{N} - (N - k + \frac{1}{2}) \ln{N} \color{blue}{- (N - k + \frac{1}{2}) \ln{(1-\frac{k}{N})} - k} - k \ln N + O(\frac{k}{N}) \right) \\ &= \exp\left(\color{blue}{ -\, (N - k + \frac{1}{2}) \ln{(1-\frac{k}{N})} - k} + O(\frac{k}{N}) \right) \\ \end{aligned}$$

Using Taylor expansion,

$$\begin{aligned} \ln{(1-\frac{k}{N})} &= -\frac{k}{N} - \frac{k^2}{2N^2} + O(\frac{k^3}{N^3}) \\ \end{aligned}$$

So,

$$\begin{aligned} \frac{N!}{(N-k)!N^k} &= \exp\left(-\, \left(N - k + \frac{1}{2}\right) \left( -\frac{k}{N} - \frac{k^2}{2N^2} + O(\frac{k^3}{N^3}) \right) - k + O(\frac{k}{N}) \right) \\ &= \exp\left(\left(N - k + \frac{1}{2}\right) \left( \frac{k}{N} + \frac{k^2}{2N^2} + O(\frac{k^3}{N^3}) \right) - k + O(\frac{k}{N}) \right) \\ &= \exp\left(k + \color{blue}{\frac{k^2}{2N}} + \color{orange}{O(\frac{k^3}{N^2})} - \color{blue}{\frac{k^2}{N}} -\color{orange}{\frac{k^3}{2N^2}} + \color{teal}{O(\frac{k^4}{N^3})} + \frac{k}{2N} + \color{orange}{\frac{k^2}{4N^2}} + \color{teal}{O(\frac{k^3}{N^3})} - k + O(\frac{k}{N}) \right) \\ &= \exp\left(\color{blue}{-\frac{k^2}{2N}} + O(\frac{k}{N}) + \color{orange}{O(\frac{k^3}{N^2})} \right) \\ \frac{N!}{(N-k)!N^k} & \thicksim e^{-\frac{k^2}{2N}} \\ \end{aligned}$$

Applying this to the Birthday problem, let

$$\begin{aligned} N &= \text{ number of possible unique values} \\ k &= \text{ number of (uniform) random selections (from } N \text{ values)} \\ P &= \text{ probability of collision (among the } k \text{ selections)} \\ \end{aligned}$$

$$\begin{aligned} P &= 1 - \frac{N!}{(N-k)! N^k } \\ \therefore P &\thicksim 1 - e^{-\frac{k^2}{2N}} \\ \end{aligned}$$

$\Box$

Source: Analysis of Algorithm

# posted by rot13(Unafba Pune) @ 4:20 PM