0

SecureRandom が指定された範囲内のすべての数値を生成するために必要な反復回数。たとえば、0 ～ 9 (両方を含む) の乱数を生成しています。次に、何回繰り返した後、すべての数字 (0、1、2、...、9) が少なくとも 1 回出現します。

4

3 に答える 3

3

前述のように、10 個の値を生成するのにかかる時間についての保証はありません。ただし、確率の法則により、1,000,000 回よりも 10 回近く反復する可能性が高くなります。

私は実際の確率を計算するほど賢くありません。ただし、問題を何度も繰り返し実行して空間をサンプリングするプログラムを作成し、毎回反復回数をカウントすることは可能です。その後、たとえば、50% の確率で反復回数が n 回未満になると判断できます。 .

楽しみのために、問題を 1,000,000 回実行して結果を集計することで、これを試してみるための何かを書きました。3回実行した後、結果は次のことを示しています。

  • 50% の確率で、27 回 (これを含む) 未満の反復 (3 回の実行すべて) しかかかりません。
  • 90% の確率で、反復回数は 44 回 (これを含む) 未満です (3 回の実行すべて)。
  • 99% の確率で、66 回 (これを含む) 未満の反復 (3 回の実行すべて) しかかかりません。
  • 99.9% の確率で、88 回 (これを含む) 未満の反復 (3 回の実行すべて) しかかかりません。
  • それぞれのケースで最悪の実行は異なりましたが、3 つの値は反復 154 回、反復 156 回、および反復 170 回でした。

これが検査用の私のコードです。java.security.SecureRandom を使用しますが、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;
            }
        }
    }

}
于 2012-10-09T20:02:50.737 に答える
3

SecureRandom が完全にランダムであると仮定すると (その Secure 部分が目指すもの)、答えは、すべての数字が少なくとも 1 回表示されることを保証する特定の数字は存在しないということです。

于 2012-10-09T19:28:23.027 に答える
2

正解はCrazyCastaさんのおっしゃる通り、数字はありません。

Scott Adams の言葉を引用すると、これはランダム性の問題です。

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

于 2012-10-09T19:34:37.563 に答える