随机整数生成

Question

我遇到了一个奇怪的问题。也许有人可以指导我阅读相关文献。

所以，在 Python 中，我创建了这个方法，它附加随机整数来设置，直到出现重复值。当生成的整数对于特定集合不是唯一的时，方法制动：

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

然后，我把这个方法重复了一千遍算了：需要多少步才能生成non-before值

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

n - there is upper bound for integer generator.

得到这样的结果：对于 n = 100：

对于 n = 1000：

对于 n = 10000：

对于 n = 100000：

所以，对于这个实验中位数：

增长相对缓慢；
留在图上的位置（对于 10'000 次实验也是如此）；

谁能帮帮忙，说说，为什么会这样？谢谢！

Answer 1

您正在计算广义生日问题的 PDF。 https://en.wikipedia.org/wiki/Birthday_problem基本上都在这里了。唯一的问题是 Wiki 页面正在谈论问题的 CDF（请参见此处的第一张图），您正在采样 PDF，p(n, k) - p(n, k-1) 的值。这是您的采样图（蓝色）与 PDF（橙色），如果您需要代码，请告诉我

更新

无论如何，最好把代码放在这里，这样它就不会丢失。所有阶乘都计算为 Gamma 函数，pbar/p 的表达式通过对数完成，避免溢出，因此调用了 Gamma 函数 lgamma 的对数。

import matplotlib.pyplot as plt
import numpy as np
import math
import random

def pbar(k, n): # as in wiki article, computed via log/exp
    l = 0
    try:
        l = math.lgamma(n + 1)  - math.lgamma(n - k + 1) - k*math.log(n)
    except ValueError:
        l = -50
    return math.exp(l)

def p(k, n):
    return 1.0 - pbar(k, n)

def count_no_repeat(i, j): # original sampling code
    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

# 100 of numbers, 1mln of samples
n = 100
N = 1000000
stats = np.zeros(n+2, dtype = np.float32)
meds  = []

for _ in range(0, N):
    q = count_no_repeat(1, n)
    stats[q] += 1
    meds.append(q)

print(np.median(meds))

stats /= float(N)
x = np.linspace(0, n+1, n+2)

# computing PDF
z = []
for k in x:
    if k == 0:
        z.append(0)
    else:
        z.append(p(k, n) - p(k-1, n))

plt.plot(x, stats, 'o')
plt.plot(x, z)
plt.show()

随机整数生成

Random integer generating

python

random

statistics

distribution