一个概率论问题(已用递推法解决)



4月19日编辑:我编程验证了一下,按89楼的方法递推可以直接解这道题。

4月18日编辑:基本已经可以认为这个问题是不可解的了,我把模拟实验用的代码放出来吧


有m个数,等概率在其中选择一个数,重复n次以后,有a个数从未被选中(a


网友评论:
有放回无放回?
1- (m-a/m)^n *(m choose  m-a)

肯定放回了鸭,不然四个数咋能选6次。。
前几天买mea徽章的时候我研究了一下,写了个程序
不过这个程序不是模拟的 而是计算的 因为公式有点复杂

有放回,不然4个数是不可能重复选6次的


3的6次方/4的5次方?
哦,不对,想少了两个到三个数没出现的情况



最后一行更正:抽x次 改为 抽n次
如需要a个不含则公式中的1改为a
既然lz可以编程那递归就好了,我也不清楚能不能化简

是这个意思吗?


看错了


算错了

没看懂,题目只有初始状态和结束状态的条件而没有给出每一步的变化情况,这样的话怎么能使用递归?初始状态:有m个数待选 结束状态:选过n次之后仍有a个数没被选过,至于这n次具体是怎么选的并没有任何信息,所以我也不知道怎么来递归写出这个状态转换


m个数拿n次,空间 = m^n,假设m个数各不相同,那么其中恰好a个数从未被抽出 = C(m,a) * (m-a)^n
则恰好a个 = C(m,a) * (m-a)^n / m^n
智障了,这个算的是>=a个的概率。



很显然不对,令a=m,这个表达式=1

你看下我的过程,我说的递归指计算F(x)的值,即由且仅由x个不同元素组成的可重复有序排列,每个排列都代表一种取法,也就是一个古典概型中的基本事件

是的,我竟然没注意到,如果a=m的时候结果是0才有可能是正确结果

13楼应该是对的



你这不仅不是恰好,也不是至少
因为你没排除重复
不信你试试a=m=n=3
太复杂了

不过古典概率会有无解的问题吗?是指无初等解吗?

这个用dp也好难,三个变量,根本想不出状态方程
嗯?以例子来说,“假如要在1,2,3,4这四个数中随机选一个数,重复选择6次,求选择过6次之后仍然有一个数从未被选中的概率。”

不是(3/4)^6 * 4=71%吗?


见我那楼,你还要去除其中有2个3个数没有出现的情况。
比如6次都是1,那就有3个数没出现过。

想了一下:
(3的六次方x4 - 2的六次方x6) /4的六次方 =0.618左右
这样?

楼主看得到我8楼的图吗,加载可能有点慢

喔喔!!有道理喔…………我再想想……

我还在想,为什么这个看起来应该用组合数解决的问题会转换成可重复排列数

—— 来自 samsung SM-C7010, Android 8.0.0上的 v2.1.2

比如你取一次,分别是a b b c d a
那就转换成abbcda
不是一一对应吗



有个地方不小心写错了,是yi的方程的非负整数解的个数
再次编辑,这个答案也有点问题,分母上是排列数,分子是不计顺序的。由于楼主并没有要求计不计顺序,分母改成从m个物体中有放回选n次的组合数就对了,计算方法和图里面一样

好像看懂一点了,就是说长度为n的排列数由(m-a)的n次方再减去所有长度小于n的排列数的和来得到?

—— 来自 samsung SM-C7010, Android 8.0.0上的 v2.1.2

所有长度都为n啊,是减去所包含的元素量更少的情况以排除多余

这个算出来的应该是至少有一个数未被选中的概率而不是恰好有一个数未被选中的概率

—— 来自 samsung SM-C7010, Android 8.0.0上的 v2.1.2


编辑

我懂了,包含的元素更少=未被选中的元素更多,所以要求出恰好a个未被选中的概率就要先减去恰好m-1个,m-2个……直到a+1个未被选中的概率,所以才要递归

—— 来自 samsung SM-C7010, Android 8.0.0上的 v2.1.2


wonderful, 不过你算错了


好像不对,下面是排列数,上面其实是组合数,我最开始也这么想的,分母部分改成从m个物体中选n次,没有最低出现次数的组合数就对了,楼主并没有要求有序还是无序

三个数,选三次,要三个数字都没有出现过


m=a的话概率肯定是0,但只要a<m且n>0这个概率就会小于1,所以这个概率只能在[0,1)中,如果这个概率能取到1就好了,这样就能同时用两个边界值直接过滤掉错误的思路了

—— 来自 samsung SM-C7010, Android 8.0.0上的 v2.1.2

嗯,发现了,分母改一下就行


编辑

想法不错,不过m=a,n=0的时候概率是1

分子也错了 c(m-a,m)*c(n-m+a,n-1)/c(m-1,n+m-1)

你再看一下?我第二个不是拿c表示的

嗯,我看错了
其实用概率dp也好写
dp[i][j] n个数字,当前取了i次,出现了j个不同的数字;
dp[i][j]=(n-j+1)/n * dp[i-1][j-1]+(j/n)*dp[i-1][j] ;
初始状态dp[0][0]=1,答案是dp[n][m-a];

扫一遍就好了。复杂度O(n*m)

是的,只要不选的话m必然等于a,只要选了一个的话a就必须小于m,感觉n=0时算是一种特殊的极端状况,所以我都是把n作为正整数来考虑的

—— 来自 samsung SM-C7010, Android 8.0.0上的 v2.1.2


编程实现的话大概就是我那个dp思路
数学的话不知道我那个式子对不对,可能会被hack(已经被自己hack了)

a=m概率必然为0,没错呀 3个数,抽3次,有3个数没被抽不就是0吗 我这个就是恰好a(C(m,a))个,剩下都从m-a个里面抽(m-a)^n。你再算算。重复已经计算了(^n),只要数字各不相同就行

问题不在这里,是有a个数字不出现,等于有m-a个数字必须要出现。
在n个位置里面要放上(m-a)种数字,每种数字都要出现的方案数不是(m-a)^n

啊对 智障了,稍微改一下,
先放m-a个数,如果a+n<==>(m-a)^ (n-m-a) * P(在n - (m-a)个位置间插 m-a个数的植树问题))
次题的问题在于恰好有a个  我记得在陈希儒的书里有一个类似的题目  不过这个a很小  所以用了便利的办法  ,现在看到这个我出现了一个思路  是否可以先为每一个被选中的数字分配一次 然后剩下的次数在排列组合呢?

—— 来自 Sony H8296, Android 9上的 v2.1.0-play

你可以搜一下 多重集合的排列,隔板法
类似x1+x2+x3+....+xn=N,要求xi都>=1
如果是xi>=0是很好做的,但是>=1就要先进行变换,然后再用组合数求解的。

具体看《组合数学》第二章第五小节的例子54


很久没写过动态规划了,试着写了一下结果不对,不知道是哪出错了




文字版:
int cal[10][10];
        cal[0][0] = 1;
        for (size_t i = 1; i < 10; i++)
        {
                cal[0] = 0;
        }
        for (int i = 1; i < 7; i++) {
                for (int j = 1; j <=i; j++) {
                        cal[j] = (6 - j + 1) / 6.*cal[i - 1][j - 1] + (j / 6.)*cal[i - 1][j];
                }
        }
        std::cout << cal[6][3];

反应过来了
用double....

  -

竟然从定义的时候就写错了,我还特意记得在常数后面加了小数点却把数组直接写成int了,不过我改完类型之后结果还是不对



现有m个数字。有a没有被选中。 也就是说 数字是从m-a个数中出。选定m-a个数有m choose m-a 种选法。

那么每次选择落在这m-a个数的的概率是m-a/m。选n次。


double dp[1000][1000];
double m, n, a;
while (cin >> m >> n >> a)
{
        memset(dp, 0, sizeof dp);
        dp[0][0] = 1.0;
        for (int i = 1; i <= n; i++)
                for (int j = 1; j <= i; j++)
                        dp[j] = (n - j + 1) / n * dp[i - 1][j - 1] + j / n * dp[i - 1][j];
        printf("%lf\n", dp[(int)n][(int)(m - a)]);
}

我用这个测的,过了我自己造的数据(吧)

给点样例吧

按这个写法用到dp[0][1]的时候就已经出错了,所以我才提前写了一个循环给dp[0][j]单独赋值,可是还是有问题,明天我再改改看一下效果

—— 来自 samsung SM-C7010, Android 8.0.0上的 v2.1.2

概率难道不是0?

概率是0,但我这边不手动赋值的话默认值是一个负数

—— 来自 samsung SM-C7010, Android 8.0.0上的 v2.1.2

你dp数组要初始化的啊


删去耻辱的错误答题



删去耻辱的错误答题

看了前4个字后我的大脑就跳过了1楼

  -


n=3,l=3,m=2的时候错了(好像)
答案是2/3

果然。检查了一下,第一行的递推公式写错了,于是后面跟着都错了

想错了,编辑

  -


这个问题好像确实是没有通用解的
楼上提醒就是隔板法,用隔板到 C(n-1,m-a-1)*C(m,m-a))/m^n,这里分母应该再乘上一个数,因为C(n-1,m-a-1)中隔板内取数是得分顺序的,但是我解不出来。

后来我发现其实分子就是S(n,m) 第二类斯特林数 无通用解

然后楼上有人提到DP[][],我了解了一下  Since the set of valid first-order formulas is recursively enumerable but not recursive, there exists no general algorithm to solve this problem.
这个也是没有通用解


删去耻辱的错误答题



最后结果的最后两项又把m写成n了。

验证了下,3个取3次取到2个,还是1/3。哎,不检查了先这么着吧

那大概就是没有通用解了
实际上根据隔板法求出来的方案数,还得根据每个方案做一遍有关多重集合的排列的方案数,但这样显然不可能通过简单的组合数进行求解。
模拟值和我的计算值在三个测试用例后就越差越大


删去耻辱的错误答题

首先此时有a个数字不被选中 方案数为C(m,a) 设这个结果为p
然后接下来用n次选剩下的m-a个数字的方案数,等于将n划分成m-a个正整数的方案数 这个可以用生成函数或者动态规划来求得 设这个结果为q
我们把p*q作为分子 那么分母呢?
分母应该是每个数字都能被选任意次的方案数,这个方案数等价于把n拆分成最多m个正整数的方案数这个方案数的求法同上。
所以求还是可以求的 但是怎么样能拥有更好的复杂度才是问题

这看上去是个通项公式,不过只要l和n稍微大一点n^l就超过INT_MAX了,所以要验证的话只能算一些特别小的数据,可能这个问题本身在规模比较大的时候就没有什么意义吧

—— 来自 samsung SM-C7010, Android 8.0.0上的 v2.1.2
等下。。。这个问题不是很容易吗,大家讨论得这么起劲是跟我理解得不一样吗


l很大的时候,直观上也很容易看出,m=n的概率趋近于1,其它都趋近于0了。l,m很小,n很大的时候,l次选择不容易选到同一个,所以m=l的接近1,其它都近于0。

啊,居然不满足我自己说的这个条件了,我再想想
分母 m^n

分子,先从m个数里挑a个出来,C(n, m-a);剩下m-a个必至少在n次中出现一次,由于每个数不一样,不同次序位置也不一样,所以这个问题等价于n个有标记的球分成m-a个有标记的组。对于一个n的划分g1+g2+...+g_{m-a}=n, g_i > 0,排列数是 n!/(g1! g2! ... g_{m-a}!),用这个公式对所有n的划分求和即可。

这个不是Stirling numbers of the second kind,那个是n个有标记的球分成m-a个无标记的组,还是点区别的。

那啥,找出所有n的划分 ,并不比所谓 第二类斯特林数 简单多少阿……
实际有 C(n-1,m-a-1) 种不同的划分,而且每种划分你都要找出每个g_i

相比之下,第二类斯特林数 S(n. m-a)  * (m-a)!(无标记分组全排列化) 反而更直观……

对的,你的形式更简洁些,P(n, a; m) = C(m, a) * S(n, m-a) * (m-a)! / m^n

我的意思主要是不能直接 S(n, m-a),要乘 (m-a)!。我一般写成划分的形式方便写DP,斯特林的递推公式记不住。




@plusSharp

之前的答案不对,但错的也不多。主要就是g这个级数求和搞错了,里面有些重叠的项被我重复计数了。

这个级数看来不太好求,观察估计,对固定的l,是个l+1次多项式。最主要的项大概是m的l+1次方乘以一个系数


试着估计了下最高次项。好像结果就变成了
c(n,m)乘以(m/n)的l次方。倒也挺合理的。



我把模拟用的代码编辑在一楼了,有时间的话可以对照一下我的代码和这个递推得到的结果来推测计算方法是否正确
老实说用概率dp求得的答案不就好了......

  -

这个dp原理我还是没理解,所以就不强行实现了

—— 来自 samsung SM-C7010, Android 8.0.0上的 v2.1.2
这就没法解了, 突然对贵坛人均常春藤发生了怀疑.


突然感觉这不是概率论的题目,这是很典型的算法题,难度大抵中下的水平。

dp[j]  n个数字,当前取了i次,拿了j个不同的数字;
状态转移方程: dp[j] =(n-j+1)/n * dp[i-1][j-1]+(j/n)*dp[i-1][j] ;
其实如果这个不好理解,还有个更好理解的:
dp[i+1][j]=dp[j]*(j/n);
dp[i+1][j+1]=dp[j]*((n-j)/n);

相当于当前处于(拿了i次,出现了j种数字)
有j/n的几率拿到重复的,走到(拿了i+1次,出现了j种数字)
有(n-j)/n的几率拿到不重复的,走到(拿了i+1次,出现了j+1种数字)

想深入了解可以搜一下“概率dp入门”
有递推公式没通项公式的情况很常见啊。

你需要一个会做数学题的AI。
逻辑上很简单、计算上很复杂的题。

和这道题类似的有“求前n个质数的乘积的十进制表示中,奇数的个数”。

设你要的答案为P(m,n,a),令Q(m,n,a)=P(m,n,m-a),则有:
1. Q(m,n,1) = m*(1/m)^n
2. Q(m,k,k)=C(m,k)*k!/m^k,C(m,k) 是组合数
3. Q(m,n,k) = k/m*Q(m,n-1,k)+(m-k+1)/m*Q(m,n-1,k-1)

基本做到这一步就能看出来,递推公式有了,任意具体数值下的精确解也有了,但是通项公式拿不出来。
这么个被一堆算法教材用成RBQ的老范例题,泥潭居然前赴后继地在找显式表达式
真要有一行以内的能写出来的通项,你们当年学递推基础的时候肯定就见过了。

标签: 概率论   发布日期:06-24