论坛风格切换切换到宽版
  • 4152阅读
  • 10回复

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

上一主题 下一主题
 
发帖
42
樱饼
10
博丽神社的喝茶券(威望)
0
春度
4
交易币
0
只看楼主 倒序阅读 楼主  发表于: 2013-10-17

分整个研究的起源,大概是贴吧里那个三段棍子拼三角形的问题吧。
忽略掉一些无关的回忆,开始正题。现在大多数的随机算法应该都在努力保证计算结果分布比较均匀。比如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的弹幕,要上方密集下方疏松的结构”这样也能做到了。
最后再补充一句,如果是生成圆形弹幕,角度和半径都均匀随机的结果就是内圈比外圈弹幕密集,详细的结果等下次咯。
据说现在流行天然属性??
制作中的个人主页
发帖
42
樱饼
10
博丽神社的喝茶券(威望)
0
春度
4
交易币
0
只看该作者 1楼 发表于: 2013-10-20

咦,图片不能显示了嘛……
据说现在流行天然属性??
制作中的个人主页
发帖
42
樱饼
10
博丽神社的喝茶券(威望)
0
春度
4
交易币
0
只看该作者 2楼 发表于: 2013-10-20
研究第二天:圆形区域分布
如果角度和半径都均匀随机,点分布会显得中间比较集中……想想也是啊,分布在半径1的小圆里和分布在半径99-100的圆环里的概率相等,前者的面积明显小于后者。
由于是二维分布,测试点的方式已经改成了在纯黑色的背景上打逐渐变白的像素点,直到有一个像素达到白色(255)为止。

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

首先把球放在一个对应圆柱里,圆柱的圆半径和球半径一致,高和球直径一致。据可靠消息,球面上任意两纬度之间的面积和对应圆柱位置的面积相等,这样球面上的点过“地轴”做垂线和对应圆柱相交的点就可以认为是“配对点”。结果就是球面上的分布问题就完全转移到了圆柱面上,而圆柱面展开以后又是简单的长方形。反正按长方形的样子均布一下,再通过一定算法对应到球面上就是啦。当然,这次的分布图只有X和Y,Z轴被忽略掉了。
据说现在流行天然属性??
制作中的个人主页
发帖
42
樱饼
10
博丽神社的喝茶券(威望)
0
春度
4
交易币
0
只看该作者 3楼 发表于: 2013-10-20

奇怪,是不是不能用黑色背景啊……
据说现在流行天然属性??
制作中的个人主页
离线同意注册
发帖
1271
樱饼
0
博丽神社的喝茶券(威望)
0
春度
8
交易币
0
只看该作者 4楼 发表于: 2013-10-29
三段棍子拼三角形,这是啥?随机这个好像在哪本书也看过,等会儿翻翻去,看起来好像挺有趣的样子
发帖
42
樱饼
10
博丽神社的喝茶券(威望)
0
春度
4
交易币
0
只看该作者 5楼 发表于: 2013-10-29
回 同意注册 的帖子
同意注册:三段棍子拼三角形,这是啥?随机这个好像在哪本书也看过,等会儿翻翻去,看起来好像挺有趣的样子 (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%
据说现在流行天然属性??
制作中的个人主页
发帖
42
樱饼
10
博丽神社的喝茶券(威望)
0
春度
4
交易币
0
只看该作者 6楼 发表于: 2013-12-02

好吧,回到棍子随便切成三段拼三角形的问题上,拼成三角形的条件应该是
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切割范围,超出此范围的切割结果无效
蓝色、红色、绿色区域分别表示①②③式不成立的范围,即拼成三角形的合理方式在黄色区域内,占总切割可能的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%。
如下边的四个图:

第一个图是原始的分布情况,结果在X接近1,Y接近0的点附近堆积严重,其他位置几乎没有分布;
第二个图是样本数量>=1的点的分布情况,可以看到所有点都在X>0,Y>0,X+Y<1的“可能的切割情况”范围内;
第三个图是样本数量>=2的点的分布情况,已经可以看出点已经有明显向右下集中的趋势;
第四个图是把原图样本输0-6的部分更明显的显示出来了。
据说现在流行天然属性??
制作中的个人主页
离线翔輪
发帖
53
樱饼
7165
博丽神社的喝茶券(威望)
0
春度
0
交易币
0
只看该作者 7楼 发表于: 2013-12-02
一个棍子分三段我想的方法是随机得到截断点的值,通过截断点之间的距离判断是否成立,按这个思路得到的区域跟6L类似,结果是四分之一。
其实5楼的第二种解法并没有问题,得到的结果不是25%估计是分母没弄对,这个是条件概率而不是全概率了,如果按条件概率来算的话貌似又涉及到积分,个人感觉是一种比较麻烦的解法,还是线性规划来得快。
Men, like bullets, go farthest when they are smoothest.
发帖
42
樱饼
10
博丽神社的喝茶券(威望)
0
春度
4
交易币
0
只看该作者 8楼 发表于: 2013-12-04
回 翔輪 的帖子
翔輪:一个棍子分三段我想的方法是随机得到截断点的值,通过截断点之间的距离判断是否成立,按这个思路得到的区域跟6L类似,结果是四分之一。
其实5楼的第二种解法并没有问题,得到的结果不是25%估计是分母没弄对,这个是条件概率而不是全概率了,如果按条件概率来算的话貌似又涉及到积 .. (2013-12-02 22:47) 

说第二种算法没问题……你确定嘛
http://tieba.baidu.com/p/826595520
有人尝试用类似y=random(1-x)的算法,结果拼成三角形的概率接近19.333%。如果你不能找到合理的分母算法解释这个情况,我只好继续认为我的“随机分布变化”推断是正确的。
据说现在流行天然属性??
制作中的个人主页
离线翔輪
发帖
53
樱饼
7165
博丽神社的喝茶券(威望)
0
春度
0
交易币
0
只看该作者 9楼 发表于: 2013-12-05
回 天使的糖豆 的帖子
天使的糖豆:说第二种算法没问题……你确定嘛
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:个人感觉条件概率大概跟你说的类似吧。
Men, like bullets, go farthest when they are smoothest.
离线同意注册
发帖
1271
樱饼
0
博丽神社的喝茶券(威望)
0
春度
8
交易币
0
只看该作者 10楼 发表于: 2016-10-01
多年后想起这贴,补个中间趋势的正态分布。

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);



快速回复
限100 字节
 
上一个 下一个