我错过了使用 numpy 随机数生成器进行引导吗？

Question

我试图编写一些代码来创建一个 bootstrap 发行版，虽然它可以编译，但我不确定它是否正常工作。一些背景：我任教的学校的一名学生一直在系统地找到我们计算机实验室笔记本电脑锁的组合，以与我们的计算机老师（幸运的是，他不是我）搞砸。每个锁都有三个条目，编号为 0-9。我计算出每个锁有 10^3 种可能的组合。他保留了他已经为每把锁尝试过的组合的详细列表，因此每次连续的尝试都会在没有替换的情况下采样一个组合。我正在尝试对此进行模拟，以了解他为解锁所有这些计算机（实验室中有 12 台计算机）进行了多少次尝试，方法是找到解锁一台计算机所需次数的预期值。这对我来说听起来像是超几何分布。我写的代码是：

import numpy as np

def lock_hg(N):

    final_counts = []
    for i in range(N):
        count = 1
        combs = list(np.arange(1,1001,1))
        guess = np.random.randint(1,1000)
        for k in range(1000):
            a = np.random.choice(combs, 1)
            if a == guess:
                final_counts.append(count)
                break
            else:
                count = count + 1
                combs.remove(a)

    return(final_counts)

调用 lock_hg(1000) 时的直方图 plt.hist(final_counts) 看起来相当均匀，40 或 50 次尝试与 900 或 950 次一样常见。我认为看起来更像是以 500 为中心的正态分布。我不确定代码是否有问题，或者我只是误解了数学。这段代码适合解决这个问题吗？如果没有，我该如何解决？如果有效，是否有更有效的方法来执行此操作？如果有效，它是什么？

Answer 1

期望均匀分布，是的。代码没问题。

一种可能的优化方法是在删除所选键之前将其与列表中的最后一个键交换。这样可以避免触及中间的所有对象。

Answer 2

您可以进行两项改进：

Python 有一个内置的随机数生成器。 https://docs.python.org/2/library/random.html

import random

for i in range(5):
    print(random.randint(0, 100))

10
38
53
83
23

如果您试图遍历所有可能的组合以进入某物（如锁），最好增加一个而不是使用随机数生成器。我可能有点误解这个问题，因为我不确定你是否想弄清楚他是怎么做到的。

Answer 3

想象生成一个组合网格，每一行代表一个锁和每个列值是该锁的可能组合。例如，假设有 10 把锁，并且每个锁只有 5 种可能的组合。您可以随机生成它们顺序如下：

In [42]: np.random.seed(2018) # to make the example reproducible
In [43]: grid = np.random.random((10,5)).argsort(axis=1); grid
Out[43]: 
array([[1, 3, 4, 0, 2],
       [4, 0, 2, 3, 1],
       [3, 4, 2, 0, 1],
       [2, 1, 3, 4, 0],
       [1, 3, 0, 4, 2],
       [1, 0, 4, 3, 2],
       [2, 0, 1, 3, 4],
       [2, 0, 3, 4, 1],
       [2, 3, 1, 0, 4],
       [2, 4, 0, 3, 1]])

接下来，让我们为这 10 把锁各选一个随机组合：

In [48]: combo = np.random.choice(5, size=10, replace=True); combo
Out[48]: array([3, 2, 3, 3, 4, 4, 4, 3, 2, 3])

我们可以把grid看成是表示对每把锁尝试组合的顺序。而我们可以取combo作为每把锁的实际组合。

我们还可以使用以下方法可视化火柴的位置：

plt.imshow((grid == combo[:, None])[::-1], origin='upper')

我们可以使用 argmax:

在我们的网格中找到每个成功匹配的位置

In [73]: (grid == combo[:, None]).argmax(axis=1)
Out[73]: array([1, 2, 0, 2, 3, 2, 4, 2, 0, 3])

argmax returns 每行匹配项的索引（位置）。这些索引号还表示找到每个匹配项所需的尝试次数。嗯，差不多。由于 Python 是基于 0 索引的，如果匹配在第一次尝试时发生，argmax 将 return 0。所以我们需要在(grid == combo[:, None]).argmax(axis=1)上加1才能得到真正的尝试次数

因此，我们正在寻找 (grid == combo[:, None]).argmax(axis=1) + 1 的分布。现在我们已经计算出 10 锁和 5 个组合，很容易增加到，比如说，10000 个锁和 1000 种组合：

import numpy as np
import matplotlib.pyplot as plt
np.random.seed(2018)

num_locks = 10000
num_combos = 1000

grid = np.random.random((num_locks, num_combos)).argsort(axis=1)
combo = np.random.choice(num_combos, size=num_locks, replace=True)
attempts = (grid == combo[:, None]).argmax(axis=1) + 1

plt.hist(attempts, density=True)
plt.show()

这种在网格中随机选择位置的方法清楚地表明分布应该是均匀的——正确的组合出现的可能性是一样的在开头、结尾或两者之间的任何位置。

我错过了使用 numpy 随机数生成器进行引导吗？

Am i miss-using numpy random number generator for bootstrapping?

python

numpy

random

probability-distribution