让我重新表述你的问题:
设random()
是一个在 上具有离散均匀分布的随机数生成器[0,1)
。让D
是 可能返回的值的数量random()
,每个都精确地1/D
大于前一个。创建一个rand(L, U)
具有离散均匀分布的随机数生成器,[L, U)
使得每个可能的值都精确地1/D
大于前一个。
--
几个快速笔记。
- 这种形式的问题,正如你所说的,它是无法解决的。也就是说,如果 N = 1,我们无能为力。
- 我不要求它
0.0
是 的可能值之一random()
。如果不是,那么下面的解决方案可能会在U - L < 1 / D
. 我不是特别担心那个案子。
- 我使用所有半开范围,因为它使分析更简单。使用封闭范围很简单,但很乏味。
最后,好东西。这里的关键见解是,可以通过独立选择结果的整体和小数部分来保持密度。
首先,请注意,鉴于random()
创建randomBit()
. 那是,
randomBit() { return random() >= 0.5; }
然后,如果我们想{0, 1, 2, ..., 2^N - 1}
均匀地随机选择一个,这很简单randomBit()
,只需生成每个位。打电话给这个random2(N)
。
使用random2()
我们可以选择以下之一{0, 1, 2, ..., N - 1}
:
randomInt(N) { while ((val = random2(ceil(log2(N)))) >= N); return val; }
现在,如果D
已知,那么问题是微不足道的,因为我们可以将其简化为简单floor((U - L) * D)
地随机选择一个值,我们可以用randomInt()
.
所以,让我们假设这D
是未知的。现在,让我们首先创建一个函数来生成[0, 2^N)
具有适当密度的范围内的随机值。这很简单。
rand2D(N) { return random2(N) + random(); }
rand2D()
是我们要求的连续可能值之间的差异random()
是精确的1/D
。如果不是,这里的可能值将不会具有均匀的密度。
接下来,我们需要一个函数来选择具有[0, V)
适当密度的范围内的值。这与randomInt()
上面类似。
randD(V) { while ((val = rand2D(ceil(log2(V)))) >= V); return val; }
最后...
rand(L, U) { return L + randD(U - L); }
L / D
如果不是整数,我们现在可能已经偏移了离散位置,但这并不重要。
--
最后一点,您可能已经注意到其中一些函数可能永远不会终止。这本质上是一个要求。例如,random()
可能只有一位随机性。如果我然后要求您从三个值之一中进行选择,则您不能使用保证终止的函数随机地统一执行此操作。