Rule of thumb (useful for cryptography, among other things):
If you draw randomly (with replacement) from N numbers, you'll need to draw approximately sqrt(N) times until the probability of a collision (drawing the same number again) rises to 1/2.
For example, if you generate random keys with 128 bits, then after generating 2^64 keys you have a good (50%) chance that you've reused a key.