[研究记录]改变随机数的分布状态 [复制链接]

分整个研究的起源，大概是贴吧里那个三段棍子拼三角形的问题吧。
忽略掉一些无关的回忆，开始正题。现在大多数的随机算法应该都在努力保证计算结果分布比较均匀。比如GM里生成无数多次的random(1)，其中0.5以上和0.5以下的结果都会很接近50%，0.8以下的数字大约占总数的80%。如果我们需要一些“不均匀”的分布情况，就只好自己手动解决了。
研究第一天：让随机数变得不均匀的算法
研究结果大概可以用下边的分布图来表示，布图是在宽度600的容器里进行随机打点的结果，当任意点累计到200个时停止累计。用于观察不同随机数处理的分布结果：
[attachment=83656]
下面说明的伪代码里有一个范围校正()，作用是将输入数字从现有范围线性变更到指定范围，如random(60)的范围是0-60，如果需要的实际范围是0-600，则需要将结果X10。将mini-maxi范围的i变更到mino-maxo范围输出o，计算式为o=i*(maxo-mino)/(maxi-mini)+maxo。大多数情况下这个算式可以化简，最终是o=a*i+b的样子。
第一个蓝色的图，表示的是最基础的随机。不经过任何处理直接累计结果，可以看到整体分布比较均匀，局部范围存在跳动。
第二个绿色的图，表示1-2平方分布。伪代码是 范围校正(平方(random(1)+1)) ，可以看到分布有向左偏移的趋势。
第二个天蓝的图，表示1-9平方分布。伪代码是 范围校正(平方(random(8)+1)) ，可以看到分布有更加明显向左偏移的趋势。
第四个红色的图，表示平方根的分布。伪代码是 范围校正(平方根(random(x))) ，可以看到分布有向右偏移的趋势，且分布目测比较均匀。尝试更换x的值，在完成范围校正后图形没发现显著区别。
第五个粉色的图，表示0-π范围取正弦的分布。伪代码是 范围校正(sin(random(pi)))，图形在最大值附近堆积严重。
第六个黄色的图，表示0-（π/2-0.1）范围取正弦的分布。伪代码是 范围校正(sin(random(pi/2-0.1)))，缓解了图形在右侧堆积的情况，左侧范围的分布量有所增加。
第七个白色的图，表示（0.1-π/2）-（π/2-0.1）范围取正弦的分布。伪代码是 范围校正(sin(random(pi-0.2-pi/2+0.1))，差不多是6号图对称了一下，变成了两侧分布。
反正，类似的代码大家能想到的应该比我多吧，像是“生成数量500的弹幕，要上方密集下方疏松的结构”这样也能做到了。
最后再补充一句，如果是生成圆形弹幕，角度和半径都均匀随机的结果就是内圈比外圈弹幕密集，详细的结果等下次咯。

图片:随机.png

咦，图片不能显示了嘛……

研究第二天：圆形区域分布
如果角度和半径都均匀随机，点分布会显得中间比较集中……想想也是啊，分布在半径1的小圆里和分布在半径99-100的圆环里的概率相等，前者的面积明显小于后者。
由于是二维分布，测试点的方式已经改成了在纯黑色的背景上打逐渐变白的像素点，直到有一个像素达到白色（255）为止。

图片:圆形0.png

前两个图是角度/半径都均匀分布的结果，其中半径排除了距离圆心较近的区域。可以看到测试结果和之前的预估一致。
第三个图是将随机结果进行了开平方处理，结果表明分布情况比较接近于均匀分布。
第四个图比较有意思，是尝试“球形表面均匀分布”的结果。

图片:qiu_zhu.png

首先把球放在一个对应圆柱里，圆柱的圆半径和球半径一致，高和球直径一致。据可靠消息，球面上任意两纬度之间的面积和对应圆柱位置的面积相等，这样球面上的点过“地轴”做垂线和对应圆柱相交的点就可以认为是“配对点”。结果就是球面上的分布问题就完全转移到了圆柱面上，而圆柱面展开以后又是简单的长方形。反正按长方形的样子均布一下，再通过一定算法对应到球面上就是啦。当然，这次的分布图只有X和Y，Z轴被忽略掉了。

图片:圆形0.png

奇怪，是不是不能用黑色背景啊……

三段棍子拼三角形，这是啥？随机这个好像在哪本书也看过，等会儿翻翻去，看起来好像挺有趣的样子

同意注册:三段棍子拼三角形，这是啥？随机这个好像在哪本书也看过，等会儿翻翻去，看起来好像挺有趣的样子 (2013-10-29 13:17) 

“一个棍子，随机切成三段，能拼成三角形的概率”问题，有人提出了无线随机看接近情况的……正常的解法应该大概是
{
x=random(1);
y=random(1);
z=1-x-y;
if(z>0)
{
  //三角形判断并记录
}
}
但当时有人为了避免Z是负数，提出了
{
x=random(1);
y=ramdom(1-x);
...
}
这样的算法，从一定程度上让X和Y有了区别，同时也直接导致了结果不是25%

好吧，回到棍子随便切成三段拼三角形的问题上，拼成三角形的条件应该是
X<Y+Z;Y<X+Z;Z<X+Y
而X+Y+Z=1，所以X<Y+Z可以变形为
X+X<X+Y+Z
X+X<1
X<0.5
同理
Y<0.5
Z<0.5
而Z<0.5等同于X+Y>0.5于是三个条件可以写成
①X<0.5；②Y<0.5；③X+Y>0.5
如图：

图片:xy.png

图中的有颜色区域表示合理的XY切割范围，超出此范围的切割结果无效
蓝色、红色、绿色区域分别表示①②③式不成立的范围，即拼成三角形的合理方式在黄色区域内，占总切割可能的1/4（25%）
当使用随机数进行重复验证时，用X=RANDOM(1);Y=RANDOM(1)生成的结果会有X+Y>1（即Z<0）的情况，处理手段有两种
简单方法是将这一次的结果进行忽略，不计入总数。当然有大约50%的计算结果会被忽略掉。
复杂一点的是用X=1-X;Y=1-Y将结果对应到可计算的范围里，计算过程会比较繁琐。
两种方法重复一段时间以后结果都会接近25%。
现在要说一说Y=RANDOM(1-X)。粗略想象一下就是X在所有结果里会均匀分布，即X>0.5导致结果“不是三角形”的概率要占到啊50%。
如下边的四个图：

图片:1_x.png

第一个图是原始的分布情况，结果在X接近1，Y接近0的点附近堆积严重，其他位置几乎没有分布；
第二个图是样本数量>=1的点的分布情况，可以看到所有点都在X>0,Y>0,X+Y<1的“可能的切割情况”范围内；
第三个图是样本数量>=2的点的分布情况，已经可以看出点已经有明显向右下集中的趋势；
第四个图是把原图样本输0-6的部分更明显的显示出来了。

一个棍子分三段我想的方法是随机得到截断点的值，通过截断点之间的距离判断是否成立，按这个思路得到的区域跟6L类似，结果是四分之一。
其实5楼的第二种解法并没有问题，得到的结果不是25%估计是分母没弄对，这个是条件概率而不是全概率了，如果按条件概率来算的话貌似又涉及到积分，个人感觉是一种比较麻烦的解法，还是线性规划来得快。

翔輪:一个棍子分三段我想的方法是随机得到截断点的值，通过截断点之间的距离判断是否成立，按这个思路得到的区域跟6L类似，结果是四分之一。
其实5楼的第二种解法并没有问题，得到的结果不是25%估计是分母没弄对，这个是条件概率而不是全概率了，如果按条件概率来算的话貌似又涉及到积 .. (2013-12-02 22:47) 

说第二种算法没问题……你确定嘛
http://tieba.baidu.com/p/826595520
有人尝试用类似y=random(1-x)的算法，结果拼成三角形的概率接近19.333%。如果你不能找到合理的分母算法解释这个情况，我只好继续认为我的“随机分布变化”推断是正确的。

天使的糖豆:说第二种算法没问题……你确定嘛
http://tieba.baidu.com/p/826595520
有人尝试用类似y=random(1-x)的算法，结果拼成三角形的概率接近19.333%。如果你不能找到合理的分母算法解释这个情况，我只好继续认为我的“随机分布变化”推断是正确的。 (2013-12-04 22:20) 

仔细想了一下，发现我说的确实有漏洞，本来想说的是：
第二种解法这种思路是没问题的，但后面错了，这种思路在得到第一点（称为A点）之后再得到第二点（称为B点），也就是说B点的出现频率是在A点确定了之后的前提下算的，random(1-x)得到的B点频率转化成在长度为1的数轴上就是Δb/(1-x)，而题目的B点出现频率是Δb/1。问题在于A、B点频率不同的情况下该如何将B点转化成跟A点同等的条件，这个我还没想到。我相信每一种思路都是可以解决问题的所以就说没错了，要纠正还得花一段时间哈【喂那不是摆坑的节奏么
PS：个人感觉条件概率大概跟你说的类似吧。

多年后想起这贴，补个中间趋势的正态分布。

matlab代码
iteration = 3;
total = 0;
imax = 1000;
out3=[];
for i = 1:imax
    total = 0;
    for j = 0:iteration-1
        total = total + rand() * imax;
    end
    out3(i) = floor(total/iteration);
end

histogram(out3, 20);