yuange1975 发表于 2023-11-22 12:54:18

算法挑战

卡片或者优惠券收集问题
有n种卡片,每次能收集到其中的1张卡片,每次每种卡片出现概率都是1/n。收集E次后,n种卡片每种都至少m张就不再收集。
问E(m,n)的数学期望值精确结果?


参考链接: https://weibo.com/6236276241/4970859019637996

ShuXueZhenMiHu 发表于 2023-11-23 09:28:37

啥是 emn ?

代码需要提供emn(m,n,f0)接口

BeerRabbit 发表于 2023-11-23 14:36:20

早年曾对类似的广义问题做过探索,也整出过一些结果,直接用的MMA处理(方便)。下面是当时问题的描述--------------

一、问题描述:
对于一个给定的单掉落随机包,其中第i个元素的掉落概率为 Subscript(i=1...s)。Subscript[现在对每个元素设定一个大于0的整数n, i](i=1...s),称为目标数。
分别求如下的两个期望:
1、任意元素的收集数目到达其设定的目标数,需要对该掉落包进行随机操作的次数期望;
2、所有元素的收集数目到达其设定的目标数,需要对该掉落包进行随机操作的次数期望。

二、求解函数:
1、Any2Target:参数Pro存储各个元素的掉落概率,Num存储各个元素的目标数;
2、All2Target:(同上)。

三、补充说明:
为了保证运算速度,使用数值积分N开头的函数;如果需要求取精确值(可能会影响计算速度),可以更换成没有N的函数。

.·.·. 发表于 2023-11-23 15:08:17

价值99元的入群名额+价值1000元的高级韭菜名额
第一次看见要交钱才能进的群
这个广告创意不错
有空写到小说里

yuange1975 发表于 2023-11-24 07:16:38

本帖最后由 yuange1975 于 2023-11-24 07:24 编辑


https://weibo.com/6236276241/4971490639610777

目前挑战情况。

这里对于图片太不友好,可以考虑找个大容量的主机站点。
要看图片的去上面链接。



http://t.cn/A6WBlELV

我都以为图1胜出了的时候再遇牛人,这都已经不是同级别的了。

这应该不会再有太大差距的算法了。

各级别算法比较:

1、最“业余”的算法是蒙特卡罗算法,只能大致算出来,不可能有精确结果。

2、模拟状态转移的,可以一步步得到越来越精准的结果。增加精度加大量耗费资源后可以采用连分数等手法,由近似值得到精确值。消耗资源比较大,速度慢,资源几何级数增大。所以稍微大一点的数据不可能计算出精确值。

3、通过马尔可夫状态转移和期望值的等式,最后得出来线性方程组,可以解出来精确值。矩阵(m+1)^n*(m+1)^n,大量耗费资源,解方程也太慢。
小的数据已经可以直接解方程得到精确值了。这已经属于比较大的改进了,已经是直接基于精确值的计算了。

4、线性方程组对称性,相当于直接手动解大矩阵方程组。或者把前面2的过程反过来逆推,直接得到精确值的模拟过程,每一步以精确值的计算。
这个算法一般的用字典存储之前的结果,后面的需要引用,可以计算出来emn(9,20),再大的字典法太耗费资源,计算已经不可能。

4.1优化改进的算法可以精确一点算出来这个序列顺序号,使用数组存储之前的结果,以及可以什么时候舍去不再需要的结果,emn(9,30)需要两个小时左右。再大需要更多资源以及大量计算时间。

5、采用(m+1)^n多项式法,可以减少中间结果,大量重复项可以用多项式展开的系数,大量减少了计算量。
5.1直接用多项式母函数,最后结果可以采用多项式母函数直接积分计算。
这算法MMA软件里特殊高速积分算法emn(9,30)浮点结果几秒精确结果需要几十秒,python的sympy常规积分小点几秒,emn(9,30)这数据崩溃。
⚠️⚠️⚠️不过这一结果也具有非常大的一个优势,形式非常简单。在一些数学软件里就一句就可以,python等语言也就几句。

5.2积分采用多项式展开直接计算可以减少一些不需要项。

6、再牛的就是图2的emn(9,30)几秒,emn(9,100)几十秒。这个emn(9,100)在算法5里面也是天文数据计算量。
我以为这算法已经是天花板了。

7、更牛的如图1,容斥原理,emn(9,100)几秒,对于算法6已经是十几倍提高了。数据再大和6也是几何级数一样拉开差距了。

数学算法的威力太强大了,每一个算法都是几何级数级别的改进。在这种几何级数改变的算法里,4.1这种优化方案都不值得一提。

结果没有想到,超出预期,看情况挑战可能会提前结束。
前面2-7类算法里面的优秀的都提供了加群和知识星球奖励。

lihpb00 发表于 2023-11-24 12:44:07

不错,挺厉害

wayne 发表于 2023-11-25 20:02:55

题主想 引流的 题目 我 黏贴如下
卡片或者优惠券收集问题
有n种卡片,每次能收集到其中的1张卡片,每次每种卡片出现概率都是1/n。收集E次后,n种卡片每种都至少m张就不再收集。
问E(m,n)的数学期望值精确结果? 这个结果是 $E(m,n) = n\int_0^\infty(1-(1-e^{-x}(\sum_{i=0}^{m-1}\frac{x^i}{i!}))^n)dx$,参考链接:https://math.stackexchange.com/questions/151267/coupon-collector-problem-for-collecting-set-k-times
http://www.mat.uab.cat/matmat/PDFv2014/v2014n02.pdf

wayne 发表于 2023-11-25 21:06:55

func:=b^(-1-a) a!;
Block[{m=9,n=100},ans=n*Sum] func@@p[],{p,CoefficientRules)^n,{x,y}]}]]//Timing

Block[{m=12,n=5},n Integrate)^n,{x,0,Infinity}]]
在我的巴掌大小的迷你主机上 用Mathematica代码计算 E(100,9)是 2秒钟. <<m>>表示中间省略m个数字.

结果大致是 $\frac{689888267795342864568\langle\langle25914\rangle\rangle0894248989121383871011}{376495052386639353915\langle\langle25911\rangle\rangle0000000000000000000000} =1832.3966368802802029078068319043568471841112647295...$

yuange1975 发表于 2023-11-25 21:28:32

MMA的积分本身算法确实牛。但你这个不应该算是这道题的算法,大众软件python的积分算法没这么牛,小点能跑出来大了就崩溃了。还有要求的是手机上算。

我的手机iPhone13+256G+python3.11,E(100,9)大约1秒,E(500,9)大约300秒。你可以跑跑E(500,9)看看时间?

python本身是解释执行,这就和真实执行代码的速度差距巨大。本身挑战要求了统一的python代码,目的就是比较算法本身,排除各种系统的差距。


wayne 发表于 2023-11-25 22:35:46

E(400,9) 我计算的时间的376 s, $\frac{40726766153092871212165172280799724373817<<447464>>96017859065959035360606228316980144341689}{49468246916308367168049020997359965992106<<447460>>00000000000000000000000000000000000000000}$
参考我上面的答案格式, 给出你计算E(500,9)精确结果的分子分母的 前几位数字. 然后我会补充更多的数字, 不然我怎么知道你是正儿八经的计算出来的. 陪玩是要有时间成本的.
E(500,9) 我计算的时间大约是800 s
页: [1] 2
查看完整版本: 算法挑战