如何从该数字的总和和范围内的随机样本中恢复一个数字？

Question

假设我有一些号码 n==4。假设我从 [0, 10] 范围内统一随机抽取一些 m。设 p 是一个长的（比如 1024 个条目）总和列表，定义为 (n+m):

from __future__ import division
import random


myRand = random.SystemRandom()
n = 4
p = []
guess = []
guess_sum = 0 

for i in range(1024):
    m = myRand.randint(0, 10)
    p.append(n + m)
    guess.append(p[i] - 5)
    guess_sum += guess[i]

如果猜测者知道 m 的取值范围，那么他们可以减去这个范围的平均值，因为平均值是均匀随机分布的中心。在我们的示例中，这对应于行：

guess.append(p[i] - 5)

我们可以通过取 guess[]:

中数字的平均值来验证此方法对隐藏数字 n 产生了良好的估计

print("average of entries in guess[] is: ")
print(guess_sum/1024)

例如，我得到如下结果：3.9365234375, 3.9619140625, 4.177734375, 3.763671875, 4.0439453125。按照预期，随着样本数量的增加超过 1024，我们预计结果的范围会收紧在 4.

附近

我的问题 - 如果猜测者不知道 m 的范围，她如何恢复隐藏的数字 n？假设 m 是从每个实验的相同范围中抽取的，并且 n 永远不会改变。

我知道肯定有人回答了这个问题，但我对如何继续前进感到很困惑。谢谢！

Answer 1

发布这个问题后我想到了一个方法，但它只有在我们事先知道 m_min 或 m_max 的值时才有效。对于此解决方案，我们需要 m_min = 0.

假设所有变量名都按照我原来问题中的定义。

猜测者只知道列表p中的一串值。随着猜测者向列表 p 添加更多数字，他们可以记录两项：recorded_min 和 recorded_max，它们分别对应于看到的最小数字和看到的最大数字。

让我们将绘制 m 的范围的端点命名为 [m_min, m_max]。回想一下，猜测者想要从列表 p.

中的条目中恢复隐藏数字 n 的值

recorded_min~=n+m_min
recorded_max ~= n + m_max

其中 ~= 表示大约相等。

在列表 p 中输入足够长的一系列条目后，我们对 recorded_min 的值和 recorded_max 的值有了一些有信心的猜测。

请注意 recorded_max - recorded_min 为您提供 m_max - m_min，它为您提供 m 绘制范围的长度。

因为我们知道 m 是从这个范围内均匀随机抽取的，所以它的中心是 center = m_min + (recorded_max - recorded_min)/2，或者等价地 center = m_max - (recorded_max - recorded_min/2)。由于我们需要 m_min = 0，我们得到了随机分布的中心。

我们现在可以获取列表 p 中的样本，并从每个样本中减去 center，然后像以前一样进行平均以得出我们对 n.[=43 的猜测=]

# python 2.7.10

from __future__ import division
import random

myRand = random.SystemRandom()
n = 4
p = []
guess = []
guess_sum = 0
num_experiments = 1024 * 80

m_min = 0
m_max = 0

while (m_max <= m_min):
    m_max = myRand.randint(0, 10)

recorded_min = float('inf')
recorded_max = 0
center = 0

for i in range(num_experiments):
    m = myRand.randint(m_min, m_max)
    p.append(n + m)
    if p[i] < recorded_min:
        recorded_min = p[i]
    if p[i] > recorded_max:
        recorded_max = p[i]

center = (recorded_max - recorded_min)/2

for i in range(num_experiments):
    guess.append(p[i]-center)
    guess_sum += guess[i]

print("average of entries in guess[] is: ")
print(guess_sum/num_experiments)
print("true value of n is: ")
print(n)
print("true m_min, m_max are: ")
print(m_min, m_max)
print("guessed m_min, m_max are: ")
print(recorded_min - guess_sum/num_experiments, recorded_max - guess_sum/num_experiments)
print("true center is: ")
print((m_min + m_max) / 2)
print("guessed center is: ")
print(center)

returns:

average of entries in guess[] is: 
4.00238037109
true value of n is: 
4
true m_min, m_max are: 
(0, 2)
guessed m_min, m_max are: 
(-0.00238037109375, 1.99761962890625)
true center is: 
1.0
guessed center is: 
1.0

如何从该数字的总和和范围内的随机样本中恢复一个数字？

How can I recover a number from the sum of that number and a random sample from a range?

python

math

statistics

cryptography

probability