Birthday paradox, huge numbers Pick x random "birthdays", say $10^9$. What are the chance of a collision, given $2^{160}$ possible "days"? 
I'm trying to estimate the collision rate of sha1 hashes, but the calculation is too big for wolfram alpha.
 A: If you have $N$ possible 'dates' and $k$ people, here's one way to get a good estimate for the probability of a collision, especially if $N$ is much larger than $k$:
There are $\begin{pmatrix} k\\2 \end{pmatrix}=\frac{k^2-k}{2}$ pairs of people.  The probability that any given pair of people has different birthdays is $\frac{N-1}{N}$.  Thus the probability of no matches is about $\left(\frac{N-1}{N}\right)^{(k^2-k)/2}$.
For instance in the traditional birthday problem with $N=365$ and $k=23$, the above gives $P(\text{no match })\approx \left(\frac{364}{365}\right)^{253}\approx .4995$.
Caveat: We don't have exact independence of events, and if $k$ gets close to $N$, the independence approximation becomes worse.
A: Let $D$ denote the number of possible days. The probability of a collision for $x$ birthdays is $$1-\prod_{k=1}^{x-1}\left(1-\frac{k}D\right)$$ If $x^2\ll D$, this is roughly $$\frac{x^2}{2D}.$$ For $x=10^9$ and $D=2^{160}\approx10^{48}$, the condition holds and one gets approximately $$10^{-30}$$
A: Well for those exact numbers you would need to use a computer program. You might wanna try asking the question to a programming stack exchange.
Mathematically we use the same probability.
For the usual birthday problem $P(n) = \prod _ {i=1}^{n-1} (1-\frac{i}{365})$.
Basically for your extended birthday problem you would want to replace $n$ with $10^9$ and replace $365$ with $2^{160}$.
