一个数学期望问题，求学霸解答

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 3115 天前的主题，其中的信息可能已经有所发展或是发生改变。

简单描述一下，有个平均分布的随机数生成器，每秒生成 n 次，每次生成（ 1 ， 2 ， 3 ， 4...， m ）中的一个数，恒定速率， n< m 。设事件 A:某个数字生成后的一秒内没有再次生成。假如运行了 k 秒，事件 A 发生次数的数学期望是多少？
概率论学过 1 年，已经被艾宾浩斯了╮（╯＿╰）╭

生成

论学

数学

生成器

14 条回复 • 2016-06-02 21:09:30 +08:00

innoink

2016-06-02 11:13:15 +08:00 via Android

不自己续个命，都沉的没影了

SoloCompany

2016-06-02 13:33:50 +08:00

如果 m>n 那么概率是 0
如果 m=n 那么只有一种排列（全排列）能满足要求
概率是很低的 n! / ((n-1)/n)^(n*k)
题目设定 m<n 和全排列是类似的
只不过是用 m * (m-1) * (m-2) … (m-n+1) * (m-n+1) … (m-n+1) 代替 n!
所以答案应该是
P(m,n) * (m-n+1) ^ (n*k - m) / ((n-1)/n)^(n*k)

吧？

SoloCompany

2016-06-02 13:36:53 +08:00

更正一下
所有的 ((n-1)/n)^(n*k)
应该是 m ^ (n * k)
表示在 k 秒时间长度内，生成的数字序列的可能数量

innoink

2016-06-02 14:38:31 +08:00 via Android

推导过程真的不会╯▂╰我写了个模拟实验程序验证一下答案，当 m,n,k 分别是 7,4,10 的时候
P(7,4)*(7-4+1)^(4*10-7)/7^(4*10)
=7*6*5*4*4^33/7^40
=30*4^34/7^39
这个几乎为 0 啊，实际模拟出来的大概是 19.5

innoink

2016-06-02 14:38:45 +08:00 via Android

@SoloCompany

SoloCompany

2016-06-02 15:11:13 +08:00

首先前面有个数字是错的，结果应该是
7 * 6 * 5 * 4 * 4^36 / (7 ^ 40)

其次，我的答案应该也有问题，我的答案忽略了一个最大的前提条件，随机数是平均分布的
我计算的概率是忽略了平均分布这个前提条件

fcicq

2016-06-02 15:26:03 +08:00

好难啊, 需要分解事件.
首先"某个数字生成后的一秒内没有再次生成", 这一秒内掷的 n 个筛子有多少个无重复结果?
没有再次生成就是这些结果都不等于 n 次前的筛子点数.
运行了 k 秒就是以上过程重复 k * n 次, 但是有一个查看区间小于 n 的 intro 和最后的 outro.

水平不足, 算不到最后了.

fcicq

2016-06-02 15:31:44 +08:00

感觉上用动态规划的话应该不算特别难解. 用 nCr nPr 的简单公式可能是没有的.

SoloCompany

2016-06-02 15:39:00 +08:00

@fcicq 事件数量不难计算啊，简单的排列组合就可以。困难的地方在于，怎么定义平均分布？如果有平均分布的概率，那么用之前计算的结果概率直接除一下平均分布的概率，应该就是楼主需要的概率了。书包已经丢掉了，不清楚平均分布的概率用什么公式得出

fcicq

2016-06-02 15:54:32 +08:00

@SoloCompany hmm... 这样一说可能有希望了. 不过还是没有出全力的意愿.
设 f(x) = P(m-1, x) / P(m, x)
难道是 f(1) + f(2) + f(3) ... + f(n) * A + f(n-1) + f(n-2) ... + f(1)
也就是 2 * sum(map(f, range(n)) + f(n) * A

A 应该是 k * n - 2 * (n-1)?

fcicq

2016-06-02 15:56:27 +08:00

range(n) 在 py 里从 0 开始, 无视细节吧 h

innoink

2016-06-02 17:58:25 +08:00 via Android

感谢楼上两位大神，这其实是我现在搞的一个实验的一部分，没想到这么复杂，我觉得有必要重新设计这个实验。
@SoloCompany @fcicq 谢谢！

SoloCompany

2016-06-02 20:36:35 +08:00

@innoink
@fcicq
我刚才再 review 了一下，好像前面的解法应该没什么错吧
应该没有什么平均分布的概念，只有平均数出现的几率一致吧
这应该是一个很简单的排列组合问题吧

P(n ,m) * (n - m + 1) ^ (K - m) / n ^ K （为了方便看，把 n*k 用 K 代替了）

你检查一下看看是不是弄错了什么
如果用 n=7, m=4, K=10 代入，结果是 0.012
砸 10 次骰子，任意连续的 4 次不出现重复数字的概率大概 1.2%

如果用你的例子，用 n=7, m=4, K=40 代入的话，概率自然很小了 < 1e-7

innoink

2016-06-02 21:09:30 +08:00 via Android

@SoloCompany 问题是需要事件 A 的次数，不是概率啊
不过还是谢谢你