3
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ Why don't you just consider an algorithm that guarantees newly generated random values are not in the set? There are plenty of efficient ways to do this. For instance, since you're worried about the set filling, you have enough storage for all $n=10^5$ elements. Why not represent the set as an array of indexes $1$..$n$ along with the current set size $k$? The last $k$ entries in the array hold the set's indexes and the remaining entries hold their complement. To insert a new element, swap a randomly chosen element from the first $k$ with the entry in position $k$ and decrement $k$. $\endgroup$
    – whuber ♦
    Commented Sep 10, 2013 at 17:43
  • 1
    $\begingroup$ I reworded the problem because this is a legacy application with some limitations as to what can be done, unfortunately the approach to guarantee the uniqueness cannot be used here as the code cannot be changed. Instead I'm trying to get some statistical properties for it so that I can argue that it should be replaced. $\endgroup$
    – Lasse V. Karlsen
    Commented Sep 10, 2013 at 18:19
  • $\begingroup$ This is somewhat reminiscent of hash function homework questions. $\endgroup$
    – ely
    Commented Sep 10, 2013 at 18:42
  • $\begingroup$ The actual problem is a database application that for old reasons calculates a primary key range for a table, and randomizes the last part. Basically it calculates the number of days since a particular date, multiplies that with 100.000, and adds a random number, then attempts to insert a new row into the database. If it fails due to a duplicate key error, it retries with another random value, 250 times max. Main reason for this "approach" is legacy code and cross-database engine support. $\endgroup$
    – Lasse V. Karlsen
    Commented Sep 10, 2013 at 19:04
  • $\begingroup$ So unfortunately it isn't exactly a set, but each day the last 5 digits of that key slowly fills up the available space of keys, for that date, increasing the chance of a failure towards the end of the day. $\endgroup$
    – Lasse V. Karlsen
    Commented Sep 10, 2013 at 19:04

3 Answers 3

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
$\begingroup$

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}$.

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.