After how many iteration SecureRandom will generate all the number between given range?

Question

How many iteration required for SecureRandom to generate all the number between given range. E.g. I am generating random number between 0-9 (both inclusive). Then after how many iteration all the numbers (0, 1, 2,...,9) appear at least once.

Answer 1

Assuming SecureRandom is perfectly random (what the Secure part of it aspires to) the answer is, there is no given number that will guarantee all the numbers will appear at least once.

Answer 2

As stated earlier, there are no guarantees on how long it will take to produce the ten values. However, the laws of probability do make it much more likely that it will take closer to 10 iterations than 1,000,000.

I'm not smart enough to work out the actual probabilities. However, it is possible to write a program to sample the space by running the problem over and over, counting the number of iterations each time, then you can determine, for example, that it will take less than n iterations 50% of the time.

Just for fun, I wrote something to try this out by running the problem 1,000,000 times and aggregating the results. After 3 runs, my results show that:

• 50% of the time, it will take less than 27 (inclusive) iterations (all 3 runs).
• 90% of the time, it will take less than 44 (inclusive) iterations (all 3 runs).
• 99% of the time, it will take less than 66 (inclusive) iterations (all 3 runs).
• 99.9% of the time, it will take less than 88 (inclusive) iterations (all 3 runs).
• The worst run in each case differed, but the 3 values were 154 iterations, 156 iterations, and 170 iterations.

Here is my code for inspection. It uses java.security.SecureRandom, but also includes a way to use java.util.Random.

import java.security.SecureRandom;

import java.util.Map;
import java.util.Random;
import java.util.TreeMap;

public class HowLong {

    public static final int MAX_TO_GENERATE = 10;

    public static final int TOTAL_RUNS = 1000000;
    public static final int TP50 = (int)(TOTAL_RUNS * 0.50);
    public static final int TP90 = (int)(TOTAL_RUNS * 0.90);
    public static final int TP99 = (int)(TOTAL_RUNS * 0.99);
    public static final int TP99_9 = (int)(TOTAL_RUNS * 0.999);
    public static final int TP100 = (int)(TOTAL_RUNS * 1);

    public static final String[] TP_NAMES = {"TP50", "TP90", "TP99", "TP99.9", "TP100"};
    public static final int[] TPS = { TP50, TP90, TP99, TP99_9, TP100 };

    public interface RandomSource {
        int next();
    }

    public static class MathRandomSource implements RandomSource {
        private final Random rand;

        public MathRandomSource() {
            rand = new Random();
        }

        public int next() {
            return rand.nextInt(MAX_TO_GENERATE);
        }
    }

    public static class SecureRandomSource implements RandomSource {
        private final SecureRandom rand;

        public SecureRandomSource() {
            rand = new SecureRandom();
        }

        public int next() {
            return rand.nextInt(MAX_TO_GENERATE);
        }
    }

    public static int waitForTen() {

        final boolean[] found = new boolean[MAX_TO_GENERATE];
        int remaining = found.length;

        final RandomSource source = new SecureRandomSource();
        int iterations = 0;
        while (remaining > 0) {
            int next = source.next();
            if (!found[next]) {
                found[next] = true;
                remaining -= 1;
            }
            iterations += 1;
        }

        return iterations;
    }

    public static void main(String[] args) {
        System.out.println("Attempting to generate all numbers below: " + MAX_TO_GENERATE);
        System.out.println("Performing n iterations: " + TOTAL_RUNS);

        TreeMap<Integer, Integer> results = new TreeMap<Integer, Integer>();
        for (int i = 0; i < TOTAL_RUNS; i += 1) {
            Integer iterations = waitForTen();
            Integer currentCount = results.get(iterations);
            if (currentCount == null) {
                results.put(iterations, 1);
            } else {
                results.put(iterations, currentCount + 1);
            }
        }
        int currTP = 0;
        int count = 0;
        for (Map.Entry<Integer, Integer> entry: results.entrySet()) {
            count += entry.getValue();
            while (currTP < TPS.length && count >= TPS[currTP]) {
                System.out.println(TP_NAMES[currTP] + ": " + entry.getKey());
                currTP += 1;
            }
        }
    }

}

Answer 3

The correct answer is as CrazyCasta said - there is no given number.

To quote Scott Adams: that's the problem with randomness, you can never be sure :)

http://dilbert.com/fast/2001-10-25/