一个随机过程问题 - 辕门射虎 - 轩辕春秋文化论坛 20周年


	muzhi (木之)


	谏议大夫 ★

组别	翰林学士
级别	前将军
功绩	684
帖子	1733
编号	151018
注册	2007-5-3

#1

发表于 2010-4-30 01:08 资料文集短消息只看该作者

一个随机过程问题

问题：设随机序列x(n),n=0,1,...独立同分布，其中x(k)以概率p取1，否则取0。
对给定的正整数l和m，如何求随机变量 MAX( x(k)+x(k+1)+...+x(k+m-1), k=1,2,...,l ) 的分布。
补一个直观说明:求连续有限多个部分和中最大值的分布，困难在于这连续的多个部分和的求和元素的互相重叠。

这是在试图分析英杰传S/L效果时遇到的一个问题。
主要用来估计通过调整行动顺序能让烧火的伤害降低多少，或用来估计通过调整刘备的行动能让反击率提高多少。
想了一段时间没找到思路，不知道版上有谁有兴趣没有。

[ 本帖最后由 muzhi 于 2010-4-30 12:03 编辑 ]

[广告] 《精忠报国岳飞传完整版》火热发布


	周瑜


	栎阳侯谏议大夫 ★

组别	翰林学士
级别	征西将军
好贴	10
功绩	943
帖子	4716
编号	1808
注册	2003-11-3
家族	瓦岗寨

#2

发表于 2010-4-30 06:46 资料主页文集短消息只看该作者

这个MAX(SUM)似乎一定是m，而SUM的分布可以用二项式定理很容易的求出来。

[广告] 《精忠报国岳飞传完整版》火热发布


	阿尔法孝直 (雀力日进)


	闽国公遂安军节度使 ★★★★★★

组别	节度使
级别	卫将军
好贴	2
功绩	1796
帖子	6034
编号	19070
注册	2004-10-16
家族	轩辕雀党

#3

发表于 2010-4-30 07:02 资料个人空间短消息只看该作者

是的，我看的时候也觉得题目有问题，既然MAX了，那么概率就是定值p^m了，就不存在什么分布问题了。

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	颖颖 (司徒家的颖颖)


	★★

组别	限制发言用户
级别	大将军
好贴	3
功绩	95
帖子	11332
编号	90594
注册	2006-11-9
来自	系统复制中心

#4

发表于 2010-4-30 07:29 资料短消息只看该作者

楼上，关键它是 max(sum(...)) 而不是一个单纯的 max。

随机变量相加，它们的概率密度函数 convolute，
f_X1+X2 (y) = int_R f(x) f(y-x) dx

密度函数的傅立叶转换相乘。
M_X1+X2(t) = M_x1(t) M_x2(t), M_X(t) = E(exp(itX))

所以一般做随机连加的话，都会用到 Fourier 或其它积分变换的。不过本科一般考 Laplace 变换的多一些。

分布函数：F_max (x1, ... , xn) = F(x)^n
密度函数：f_max (x1,...xn) = nF(x)^(n-1)f(x)

[ 本帖最后由颖颖于 2010-4-30 07:45 编辑 ]

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	阿尔法孝直 (雀力日进)


	闽国公遂安军节度使 ★★★★★★

组别	节度使
级别	卫将军
好贴	2
功绩	1796
帖子	6034
编号	19070
注册	2004-10-16
家族	轩辕雀党

#5

发表于 2010-4-30 09:03 资料个人空间短消息只看该作者

回复 #4 颖颖的帖子

QUOTE:

原帖由周瑜于 2010-4-30 06:46 发表
这个MAX(SUM)似乎一定是m。

当时觉得题目很奇怪，怀疑MAX(SUM)是个定值，没去回复，但是之后看到了周大回了这句，于是才回帖跟上的。

[广告] 真诚支持说岳，携手共创辉煌


	土狼


	白衣伯爵太常丞 ★★

组别	白衣卿相
级别	平南将军
功绩	299
帖子	2117
编号	199840
注册	2007-8-10

#6

发表于 2010-4-30 11:04 资料个人空间短消息只看该作者

周大的结论应该没问题，
问题时英杰传是伪随机，连续烧几个敌军时，几个随机事件是相关的，只能在某一大段中选一小段连续的，而不可能每个独立选

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	muzhi (木之)


	谏议大夫 ★

组别	翰林学士
级别	前将军
功绩	684
帖子	1733
编号	151018
注册	2007-5-3

#7

发表于 2010-4-30 11:18 资料文集短消息只看该作者

这个max值本身是一个随机变量啊！
这个问题就是想要解决土狼兄说的取用的随机数总在一个确定的序列里的问题。
只是这里没讨论伪随机数的产生方式，只讨论了取用方式。

我直观解释一下来源:

比如我方有10个人,其中一个烧花五,那么有5个随机数被用来判断是否成功。
假设其他9个人都是激励/援助/假情报等，总之就是在烧火者行动用掉一个随机数。
如果烧火的第1个动，则用来判断的5个随机数就是今后的第2,4,6,8,10个。
如果烧火的第4个动，则用来判断的5个随机数就是今后的第5,7,9,11,13个。
(这里还假设了敌人被烧到后士气不会低于30而产生混乱判断用掉一个随机数)
S/L要做的就是从烧火的10种可能次序中，选出一种使得命中的个数最少的。

to 4楼：
Fourier变换提醒了我，多重卷积变多重乘法，值得一试，可惜5年没用过忘得差不多了...
另Laplace变换和Fourier变换本来就可以相互转化。

[ 本帖最后由 muzhi 于 2010-4-30 11:41 编辑 ]

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	阿尔法孝直 (雀力日进)


	闽国公遂安军节度使 ★★★★★★

组别	节度使
级别	卫将军
好贴	2
功绩	1796
帖子	6034
编号	19070
注册	2004-10-16
家族	轩辕雀党

#8

发表于 2010-4-30 11:20 资料个人空间短消息只看该作者

总觉得这个MAX的意思就是 x(k)+x(k+1)+...+x(k+m-1)的最大值，都取1时的值m。

难道还有其他意思吗？

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	muzhi (木之)


	谏议大夫 ★

组别	翰林学士
级别	前将军
功绩	684
帖子	1733
编号	151018
注册	2007-5-3

#9

发表于 2010-4-30 11:22 资料文集短消息只看该作者

QUOTE:

原帖由 阿尔法孝直 于 2010-4-30 11:20 发表
总觉得这个MAX的意思就是 x(k)+x(k+1)+...+x(k+m-1)的最大值，都取1时的值m。

难道还有其他意思吗？

这就是看题不仔细...

是前l个这样的和中的最大值（用GB4做S/L时只能设法用掉随机数序列中有限多个），不是所有的这样的和中的最大值
后者当然以概率1取m

[ 本帖最后由 muzhi 于 2010-4-30 11:25 编辑 ]

[广告] 真诚支持说岳，携手共创辉煌


	阿尔法孝直 (雀力日进)


	闽国公遂安军节度使 ★★★★★★

组别	节度使
级别	卫将军
好贴	2
功绩	1796
帖子	6034
编号	19070
注册	2004-10-16
家族	轩辕雀党

#10

发表于 2010-4-30 11:28 资料个人空间短消息只看该作者

回复 #9 muzhi 的帖子

晕，这样我就看懂了。

那么这样的话，p就是关于l的函数。

现在问题是我们不知道这个随机序列的算法。

[广告] 真诚支持说岳，携手共创辉煌


	muzhi (木之)


	谏议大夫 ★

组别	翰林学士
级别	前将军
功绩	684
帖子	1733
编号	151018
注册	2007-5-3

#11

发表于 2010-4-30 11:36 资料文集短消息只看该作者

回复 #10 阿尔法孝直的帖子

1. p是事先给定的，跟l无关，怎么会是l的函数呢
  要求的分布由p,m,l决定

2. 随机数的产生和取用的影响是两个问题
  你换一种产生的算法，只要产生的过程仍然是确定的，S/L仍然受到取用方式的制约，需要研究本问题
  这个问题说白了就是“能用的随机数总在那个序列里”的问题
  （另外印象中周大给出过随机数的产生方式？）

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	阿尔法孝直 (雀力日进)


	闽国公遂安军节度使 ★★★★★★

组别	节度使
级别	卫将军
好贴	2
功绩	1796
帖子	6034
编号	19070
注册	2004-10-16
家族	轩辕雀党

#12

发表于 2010-4-30 11:45 资料个人空间短消息只看该作者

回复 #11 muzhi 的帖子

不好意思说错了，是MAX的概率p{MAX}与l的关系

m，梅花五就是取5了。

[广告] 《精忠报国岳飞传完整版》火热发布


	numdisp (数值频散)

组别	百姓
级别	在野武将
功绩	1
帖子	44
编号	362758
注册	2010-2-26

#13

发表于 2010-5-1 02:55 资料短消息只看该作者

叹为观止了，这年头研究游戏都用上随机变量和时间序列分析的知识了。
要是为了游戏，我看还是不要搞这么复杂了。
要是为了纯学习，我倒是不反对。不过楼主上面说的Fourier变换和Laplace变换，你要真搞，我先提醒一下：注意离散的F/L变换和连续F/L变换的区别。

[广告] 《精忠报国岳飞传完整版》火热发布


	muzhi (木之)


	谏议大夫 ★

组别	翰林学士
级别	前将军
功绩	684
帖子	1733
编号	151018
注册	2007-5-3

#14

发表于 2010-5-1 10:16 资料文集短消息只看该作者

回复 #13 numdisp 的帖子

为了游戏的话有个大致的经验分布或者期望估计足够了
只是觉得有趣才提出这个问题
用惯的信号处理的书不在手头，相关的复习有点麻烦，暂时不想动手了- -b

[广告] 真诚支持说岳，携手共创辉煌


	颖颖 (司徒家的颖颖)


	★★

组别	限制发言用户
级别	大将军
好贴	3
功绩	95
帖子	11332
编号	90594
注册	2006-11-9
来自	系统复制中心

#15

发表于 2010-5-5 07:17 资料短消息只看该作者

回复 #7 muzhi 的帖子

如果你告诉我 x(k),x(k+1),...,(l+m-1) 本身的 probability density/mass function 的话，我可以帮你算。

P.S. 本科生考 Laplace 多关键是因为考题里的逆变换，很多时候都是可以看出来的。但实际生活中，你想逆 Laplace 变换就需要求一个 complex contour integral，比对傅立叶求逆的计算时间慢多了。

[ 本帖最后由颖颖于 2010-5-5 07:23 编辑 ]

[广告] 《精忠报国岳飞传完整版》火热发布