生成排序的随机整数而没有排序？上)

Question

刚看了一个关于生成100个随机整数的排序列表的代码高尔夫问题.然而,突然出现的是,您可以生成一个正增量列表,并将它们添加到运行总计中,这样:

deltas: 1 3 2  7  2
ints:   1 4 6 13 15

实际上,你会使用浮点数,然后标准化以适应某些上限,并且圆形,但效果是相同的.

虽然它不会产生更短的代码,但如果没有排序步骤肯定会更快.但我没有真正处理的事情是这样的:整数分布是否与从均匀分布的概率密度函数生成100个随机整数相同？

编辑:示例脚本:

import random,sys
running = 0
max = 1000
deltas = [random.random() for i in range(0,11)]
floats = []
for d in deltas:
    running += d
    floats.append(running)
upper = floats.pop()
ints = [int(round(f/upper*max)) for f in floats]
print(ints)

谁的输出(公平骰子滚动)是:

[24, 71, 133, 261, 308, 347, 499, 543, 722, 852]

更新: Alok的回答和Dan Dyer的评论指出,使用指数分布进行增量可以得到均匀的整数分布.

Answer 1

所以你要问的是,以这种方式生成的数字是否会均匀分布.

你正在生成一个系列:

y _j =Σi _{= 0} ^j(x _i/A)

A所有x _i的总和在哪里.x _i是(正)增量的列表.

如果f x _i指数分布(具有任何固定均值),则可以这样做.因此,如果x _i均匀分布,则得到的y _j将不会均匀分布.

话虽如此,生成指数x _i值相当容易.

一个例子是:

sum := 0
for I = 1 to N do:
    X[I] = sum = sum - ln(RAND)
sum = sum - ln(RAND)
for I = 1 to N do:
    X[I] = X[I]/sum

并且您将在范围内排序随机数[0, 1).

参考:生成随机数的排序列表.该论文还有其他(更快)的算法.

当然,这会产生浮点数.对于整数的均匀分布,您可以在最后一步中替换sum上面的内容sum/RANGE(即,RHS变为X[I]*RANGE/sum,然后将数字四舍五入为最接近的整数).

Answer 2

甲均匀分布具有上和下限.如果您使用您提出的方法,并且您的增量恰好被选择得足够大,以至于在生成所有数字之前遇到上限,那么您的算法接下来会做什么？

话虽如此,您可能想要研究泊松分布,它是在给定平均频率下发生的随机事件之间的间隔时间的分布.