I understand the birthday problem from a basic level, but I'm curious how checking for a pair after every choice of N alters the probabilities. For example, assuming you want to choose N random numbers between 1 and 100,000,000. If N = 12,000, the probability of there being two duplicate numbers in the group is about 50%.
However, if you had 12,000 unduplicated numbers, and you wanted to choose the 12,001st number, is the probability of getting a match = 12,000/100,000,000 or 0.012%?
Yes, that is correct. The "birthday paradox" is created because with $n$ birthdays you have ${n \choose 2}=\frac 12n(n-1)$ pairs of birthdays, any one of which can match. When you rule out matches in the first batch of birthdays you only get as many chances to match as you already have birthdays and the "paradox" disappears.