从给定的具有不同范围的随机数生成器方法创建随机数生成器方法

Question

我想使用给定的随机数生成器方法制作一个随机数生成器。

Given a function randK() that return a random number from 1 to k, create a function randN() that return a random number from 1 to n with equal probability.

其中 k 可以小于或大于 n (k<n or k>n).

我知道如果 (k > n) 我们可以继续调用 randK() 直到它 return (value <= n).

但是 equal probability 属性会被维护吗？
还有 (k<n) 的情况呢？

`

Answer 1

1) 是的，所有在1到k之间的数字出现的概率都是一样的，那个概率是1 / k（不是1 / n），所以它们都是同样可能的（另外，如果 k - n 很高，那么在 fn()[=56= 中调用 f() 的次数] 可能会增加）。

2) 创建一个 x-tuple 值 (f(), f(), ..., f())，其中 x 是满足以下条件的较小整数在等式中：k^x >= n

我们只关心 x 这样 k^x > n问题回到案例 1（其中 k > n）。如果生成的 x 元组在前 n 个元组之外，则重新开始。

示例： 给定 f() returns [1, 5] 中的一个数字（等概率），你想创建 fn() returns [1, 10] 中的一个数字（同样有可能）。

满足5^x>=10的第一个整数x为x = 2, (25 >= 10)。

那么你的x元组的形式是(f(), f())（只是一个元组），调用函数f()两次并应用案例1：

(1,1) = 1, (1,2) = 2, (1,3) = 3, (1,4) = 4, (1,5) = 5, (2,1) = 6, (2,2) = 7, (2,3) = 8, (2,4) = 9 and (2,5) = 10

如果你得到其他 15 个元组之一 [(3,1),(3,2),(3,3),(3,4),(3,5),(4,1) ,(4,2),(4,3),(4,4),(4,5),(5,1),(5,2),(5,3),(5,4),( 5,5)] 再次重复该算法，直到获得前 10 个元组中的一个。

这10个元组出现的概率相同，都是1/25。

Answer 2

这是针对 k > n 的情况。逻辑来自这个 link - http://www.geeksforgeeks.org/generate-integer-from-1-to-7-with-equal-probability/ 。考虑 randn 生成从 1 到 n 的数字，randk 生成从 1 到 k 的数字。

int i = randn*n + randn - n;
int j = n*n/k;
while ( i < j*k + 1){
   i = randn*n + randn - n; 
}
return i%k + 1;

这应该以相等的概率生成从 1 到 k 的数字。

从给定的具有不同范围的随机数生成器方法创建随机数生成器方法

Create a Random Number Generator method from A given Random number generator method with different range

random

algorithm

random-sample