Chance of collisions between random numbers when inserting into set I apologize if this is too basic or whatnot, if it is just flag the question away.
I have the following computer code situation:
We need to insert 1000 new random numbers into a set. The set won't tolerate collisions, and each time we execute this job we need to add exactly 1000 random numbers into the set. To avoid the job running for "a long time", every time we generate a number that already exists in the set, generate a new one, but only do this 250 times for each such number. Each random number is in the range 0 through 99.999, which means that as the set fills up towards 100.000 unique numbers, the chance of each such number generation fails and the chance of the whole job fails is increasing exponentially towards the end.
Procedural description:
DO 1000 TIMES:
    TRIES = 0
    LABEL START
    X = RANDOM 0 THROUGH 99.999
    IF X IN SET THEN
        INCREASE TRIES
        IF TRIES > 250, FAIL THE JOB
           ELSE, GO BACK TO START
    ADD X TO SET

What I need to calculate is the chance of the job failing, when we know the existing number of numbers already in the set, which is K.
Here's my take on this.
To calculate the chance of any single randomly generated number already existing in the set:
chance = K / N

This chance goes towards 1.0 when the set fills up (K closes in on N).
The chance of all 250 attempts for a single number failing:
chance = (K / N) ^ T

This starts out low, which is expected, and steeply rises towards the end, which is also expected. Basically, only when the set is close to filling up will the chance of 250 sequential collisions rise up, and when it starts rising, it goes up pretty fast.
The chance of any of the 1000 numbers individually failing:
chance = Y * (K / N) ^ T

This last bit is obviously wrong (and I'm not entirely sure about the previous ones) since after inserting the first number into the set, there is obviously less of a chance of the next one succeeding. That last formula above calculates (presumably, if it is "correct") the chance of finding 1000 such random numbers that could fit into the set and then don't insert any of them into the set, which is not what I want.
The last part of my problem is that I want to solve the final equation for chance, to find the fill-factor of the set. Meaning: Given a chance of failure for the whole job to be 90%, how full does the set have to be in order to give me that failure chance?
Unfortunately all of this is a bit above my old math head, so any help is appreciated.
 A: As you said the probability of failing on the $k_{th}$ try is ${(\frac{k}{N})}^T$. Therefore probability of the $k_{th}$ attempt being successful is $1-{(\frac{k}{N})}^T$. Therefore the probability of success of all of the first $k$ attempts is $\prod_{i=1}^k (1-{(\frac{i}{N})}^T)$. Therefore the probability of failure to get $k$ items is $1- \prod_{i=1}^k (1-{(\frac{i}{N})}^T)$. I do not know how to solve this in closed form to get value of $k$ for 0.9 . But using a for loop or binary search for $k$ should do it.
A: At $n$th iteration of the loop, you already have $n-1$ unique numbers. Probability of collusion is $q_n=\frac{n-1}{N}$ where $N=100000$.
Each # trials $T_n$ follows Geometric Distribution, $P(T_n=t)=q_n^{t-1}(1-q_n)=\left(\frac{n-1}{N}\right)^{t-1}\left(1-\frac{n-1}{N}\right)$.
Sum of trials required is $S_{1000}=\sum_{n=1}^{1000}T_n$ has a distribution which is convolution of 1000 Geometric Distributions.
I am not aware of a closed form solution, given that the parameter of the geometric distributions are different.

But this can be approximated upto an arbitrary precision using a computer.
$$P_{k,250}=P(S_k=250)=\sum_{t=0}^{250}P(S_{k-1}=250-t)P(T_k=t)=\sum_{t=0}^{250}P(S_{k-1}= 250-t)\left(\frac{k-1}{N}\right)^{t-1}\left(1-\frac{k-1}{N}\right)$$
You will need to build it up recursively, on both indices of $P_{k,l}$.
A: You might argue that on the $k$th turn there are already $k-1$ terms in the set, slightly affecting your expression for losing on the $k$th turn, though it might depend on whether you start counting at $0$ or $1$.  
The following R code will do your calculation
N <- 100000
k <- 1:N
T <- 250
prob_win_on_kth_turn  <- 1 - ((k - 1) / N) ^ T
prob_lose_by_kth_turn <- 1 - cumprod(prob_win_on_kth_turn)

giving the result that you need to aim for at least $97968$ numbers in the set for the probability of the job failing to exceed $0.9$:
> sum(prob_lose_by_kth_turn < 0.9)
[1] 97967
> prob_lose_by_kth_turn[97967]
[1] 0.8995897
> prob_lose_by_kth_turn[97968]
[1] 0.9001809

Similarly, to have a probability less than $0.1$ of the job failing, you need to aim for $96771$ or fewer numbers in the set.
