Convergence of the product $\prod_{i=0}^{b^\frac n2 -1} \left(\frac{b^n-i}{b^n}\right)$ Suppose we have a set of $b^n$ different numbers. Every time we randomly choose a number from this set and put it in a list of length  $b^\frac  n2$.
So we want to fill this list with unique numbers. However every time we choose a number we place it back to the set, giving it another chance to be selected. of course we would like numbers on our list be unique so I guess the probability to have a list of unique numbers is:
$\prod_{i=0}^{b^\frac n2 -1} \left(\frac{b^n-i}{b^n}\right)$
With sufficiently large $n$ and regardless of base $b$, computer analysis shows that it converges into 0.606 but I cannot fathom the reason. I wonder if someone can show me how this happens.
 A: This is known as the "birthday paradox," which you can look up. Your choice of wanting to choose $b^{n/2}$ unique numbers from $b^n$ numbers means that you want $\sqrt{N}$ chosen numbers from $N$ numbers to be unique, which puts you right on the boundary of where the birthday paradox takes over and the probability that you get a duplicate number goes to $1$ asymptotically very quickly as the count of selected numbers increases whereas the probability that you don't get a duplicate number goes to $0$ also asymptotically very quickly as you decrease the selected subset size. Your choice of right around $\sqrt{N}$ for your subset size should give you something right in the middle, walking a tight rope, a non-trivial probability (bounded away from $0$ and $1$) of having duplicates, and I believe it should converge as $N$ increases.
A: You can find the exact value by doing a series of transformations on your product.  Since you don't actually use $b^n$ for anything other than taking its square root, I'll instead denote $b^{\frac n2}$ by $m$; then your product becomes (up to a small factor that converges to $1$ as $m\to\infty$) $\displaystyle P_m=\prod_{i=0}^m\left(1-\dfrac{i}{m^2}\right)$.  Now, take the logarithm of this: $\displaystyle\ln P_m = \sum_{i=0}^m \ln\left(1-\dfrac i{m^2}\right)$.  We can use the Taylor expansion $\ln(1-x)=-x+O(x^2)$ to write this as $\displaystyle -\sum_{i=0}^m\left(\dfrac i{m^2}+O(\dfrac{i^2}{m^4})\right)$, and then (distributing) as $\displaystyle-\sum_{i=0}^m\dfrac i{m^2}+O(\sum_{i=0}^m\dfrac{i^2}{m^4})$.  Now we can factor out the $m$ terms from the sums (since they're constant), giving $\displaystyle-\frac1{m^2}\sum_{i=0}^mi+\frac1{m^4}\sum_{i=0}^mO(i^2)$.  And here the first sum is $\frac{m^2}{2}+O(m)$, and the second sum is $O(m^3)$, giving us $\ln P_m=-\frac12+O(m^{-1})$; in the limit, then, we get $\ln P_\infty=-\frac12$ and $P_\infty$, your limiting probability, as $P_\infty=e^{-1/2}\approx0.60653...$
