创建一个使用另一个随机函数作为种子生成随机数的函数

Question

您有一个函数 f1()，它以相等的概率生成 0 或 1。编写一个函数 f200()，使用 f1() 生成 1 到 200（包括两者）范围内的数字。

有人建议采用以下方法：掷硬币，根据结果判断数字是多于一半还是少于一半。对每一半递归地执行此操作。选择一半是用 2 的幂完成的。

之所以选择2的幂是因为我们可以实现所有的数字吗？

import random as rd 

def prob200(half):
    if half >= 200:
        return 0    
    #f1 can be replaced by this rd.randint(0, 1)
    toss_value = f1() 
    # check if toss falls in this current half and then change the half for next recursion. 
    # we change half from 1, 2, 4, 8, 16, 36, 64, 128
    result = toss_value*half + prob200(half<<1)
    if result > 200:
        return prob200(1)
    else:
        return result

for i in range(0, 10):
    print(prob200(1))

Answer 1

非常简短的回答

选择 2 的幂以均匀分布生成的随机数。

更长的答案

首先要明确一点，一个数是不是2的幂并不重要。我们总能"achieve all numbers".

每当你有一个数字的 2 个一半时，你选择任何一半的概率都是相同的（因为 f1() 以相等的概率生成 0 或 1）。这显然意味着我们不会从 2 个中只选择 1 个一半，因此 我们总是可以实现所有数字。

现在的问题是为什么我要选择 2 的幂？
我的回答是 如果您不选择 2 的幂，那么您将得到随机数，但概率不等 。

这个案例的一个简短例子应该很清楚，我开始了：
假设您必须生成 1 到 3 范围内的数字。现在当您将其减半时，您要么将其切成 1 2 | 3 或 1 | 2 3. 比方说你做的像 1 | 2 3.
所以选择 1 的概率将变为 1/2 = 0.5，选择 2 或 3 的概率将变为 1/2 * 1/2 = 0.25

这里问题的根源在于，当有一个大小范围不等于 2 的幂时，您将该范围（1 到 3 分为 1 | 2 3）分为 2 组。你得到 2 组大小不等（在上述情况下，第 1 组的大小为 1，第 2 组的大小为 2）。组大小的这种变化将导致选择这些组中数字的概率发生变化。

但如果是 2 的幂数，则保证您将始终获得相同大小的组。所以，它总是会以相同的概率给你随机数。

Q.E.D.

Answer 2

以下是我的做法。给定 f(0,1)，您可以为任意 x 生成随机数 f(0, 2^x - 1)。对于 n =200，生成一个函数 f(0, 255)。然后 r = f(0,255)，如果 r < 200 return r。否则，重新运行算法，例如重新生成 r 直到 r 小于 200。

Answer 3

您使用随机位生成器创建了一个 n 位的数字 x（例如，n=32 或更高，如果需要更高的精度 = 更均匀的分布），您将其转换为您想要的范围 r（例如 r=200）如下：result=floor(x / 2^n * r)+1

例如，如果您使用 n=8，您将使用随机位生成器（函数 f1）生成一个 8 位数字，该数字在 0-255 范围内（含 0-255）。然后你将它除以 2^8=256，所以我们将得到一个介于 0 和 255/256 之间的数字。然后我们乘以 200，所以我们将得到 0 到 199.2 之间的结果。最后，我们将它四舍五入并加 1 得到 1 到 200 之间的数字。

但是由于我们只使用了 8 个随机位 (n=8)，所以一致性不是很好。我们有效地生成了一个 0-255（源范围）的数字，并将其转换为 1-200（目标范围）的数字。目标范围内的大多数数字在源范围内都有一个对应的数字，但其他数字（例如数字 1）有两个对应的源数字（0 和 1）。所以有些数字有1/256的概率出现，而有些数字有2/256的概率。

为了改善这一点，我们可以使用n=16，那么概率差异最多为1/2^16。

这是一个程序，它首先尝试使用 8 位生成随机数，但如果它溢出 4 次，它就会使用我描述的方法生成一个 32 位数字并将其转换为输出范围：

import math
import random

def f1():
  return random.randint(0,1)

def rand_by_bits(n):
  v=0
  for i in range(n):
    v=(v<<1)+f1()
  return v

def rand_by_range(r):
  n=0
  t=r
  while t>0:
    t>>=1
    n+=1

  for i in range(4):
    v=rand_by_bits(n)
    if v<r:
      break

  if v>=r:
    n=32
    v=math.floor(float(rand_by_bits(n))/(1<<n)*r)

  return v+1

def main():
  random.seed()
  print(rand_by_range(200))

创建一个使用另一个随机函数作为种子生成随机数的函数

Create a function that generates a random number using another random function as seed

algorithm

probability

非常简短的回答

更长的答案