一个随机过程问题

问题：设随机序列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 ) 的分布。
[color=Red]补一个直观说明:求连续有限多个部分和中最大值的分布，困难在于这连续的多个部分和的求和元素的互相重叠。[/color]

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

[color=Silver][[i] 本帖最后由 muzhi 于 2010-4-30 12:03 编辑 [/i]][/color]

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

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

楼上，关键它是 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)

[color=Silver][[i] 本帖最后由 颖颖 于 2010-4-30 07:45 编辑 [/i]][/color]

回复 #4 颖颖 的帖子

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

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

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

这个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变换本来就可以相互转化。

[color=Silver][[i] 本帖最后由 muzhi 于 2010-4-30 11:41 编辑 [/i]][/color]

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

难道还有其他意思吗？

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

难道还有其他意思吗？ [/quote]

这就是看题不仔细...

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

[color=Silver][[i] 本帖最后由 muzhi 于 2010-4-30 11:25 编辑 [/i]][/color]

回复 #9 muzhi 的帖子

晕，这样我就看懂了。

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

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

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

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

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

回复 #11 muzhi 的帖子

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

m，梅花五就是取5了。

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

回复 #13 numdisp 的帖子

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

回复 #7 muzhi 的帖子

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

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

[color=Silver][[i] 本帖最后由 颖颖 于 2010-5-5 07:23 编辑 [/i]][/color]