dimanche 29 avril 2018

Random integer generating

I've faced with the curious question. Maybe someone could guide me to relevant literature.

So, in Python, I've created this method, which appends random integers to set until repeated value occurs. When a generated integer is not unique for particularly set, method brakes:

import random

def count_no_repeat(i,j):
    random_set = set()
    while True:
        new_number = random.randint(i,j)
        if new_number in random_set:
            break
        random_set.add(new_number)
    return len(random_set) + 1

Then, I've repeated this method thousand times to count: how much steps it needs to generate non-been-before value

stats = []
for _ in range(1000):
    stats.append(count_no_repeat(1,n))

n - there is upper bound for integer generator.

And got such results: for n = 100: distplot for n equals 100

for n = 1000: distplot for n equals 1000

for n = 10000: distplot for n equals 10000

for n = 100000: distplot for n equals 100000

So, for this experiment median:

  • grows relatively slow;
  • stays on the place on the plot (that also true for a 10'000-times experiment);

Who can help, and say, why this is so? Thanks!




Aucun commentaire:

Enregistrer un commentaire