算法挑战

yuange1975

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

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

ShuXueZhenMiHu

啥是 emn ？

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

BeerRabbit

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

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

二、求解函数：
1、Any2Target：参数Pro存储各个元素的掉落概率，Num存储各个元素的目标数；
2、All2Target：（同上）。

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

.·.·.

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

yuange1975

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

不错，挺厉害

wayne

题主想 引流的 题目 我 黏贴如下

卡片或者优惠券收集问题
有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/q ... lecting-set-k-times
http://www.mat.uab.cat/matmat/PDFv2014/v2014n02.pdf

wayne

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

复制代码

1. Block[{m=12,n=5},n Integrate[1-(1-E^-x Sum[x^i/i!,{i,0,m-1}])^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

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

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

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

wayne

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