新三国杀吧 关注:228,839贴子:14,992,016
  • 5回复贴,共1

【智迟二】多套拼图的期望抽取次数解析解

取消只看楼主收藏回复



在【智迟】春节拼图活动的概率和期望及分布分析中
已经对集齐1套拼图的均等概率情况,非均等概率情况(有的碎片容易出现,有的难出现)以及考虑分布的概率分析情况等,提供了解答
对于多套拼图的集齐问题,如果用蒙特卡洛求解,精度不一定能达到要求
如果继续沿用马尔科夫链的方法,不断写递推公式,
1套=25.46,2套=40.49,3套=……
还是交给CS大佬去解决吧
深夜复习,最后还是找到了求解60套拼图的期望次数的解析方法
直接上结论
记拼图碎片的种类为N(N=9)
记需要集齐的次数为m(m=1,2,5,13,25,60)
期望由以下公式给出

其中,

更多的读者应该会更加关心
m=1,2,5,13,25,60
期望EX=?
我还是用matlab算了一下
m=1,EX=25.46次
m=2,EX=40.49次

和上帖子中,用马尔科夫方法得到的结果完全一致
m=5,13,25,60的期望抽取次数,等明天再更新
电脑配置不行,跑不出来。
至于上一个帖子中提到下式不能用于求解拼图问题的期望次数
原因如课件所示……N必须足够大,而拼图活动中,N恒等于9

最后还有一个问题没有解决,固定的抽取次数,能够集齐60套的概率是多少?最概然情况下的次数是多少?
这个问题并非毫无意义,因为我们求得的期望抽取次数EX,很大可能不是最概然情况下的抽取次数。
不过这个问题……问就是不会可能只有蒙特卡洛能告诉我们答案了


IP属地:北京1楼2020-01-31 03:52回复

    最后楼主斗胆为何时购买万能拼图,进行简单的分析
    上图是55次,目标此时是60
    有5种碎片已经达到目标,只有4种碎片不足
    那么此时若购买随机拼图,5/9的可能是亏损200元宝,4/9的可能是节约300元宝,
    收益是200/9元宝
    如果有6种碎片已经达到目标,只有3种碎片不足,那么收益为负
    这仅是一种判断的方法
    每个人都可以根据自己的目标次数进行分析
    以及,今天还会赠送一张随机拼图,我想大部分和我一样热衷精笨的玩家,应该尚未开始抽完吧
    楼主刚刚抽完了,结果如下


    IP属地:北京2楼2020-01-31 03:59
    收起回复
      仔细想了一下,如果用马尔科夫方法来递推求60套拼图的期望抽取次数,其实设置9个参数就可以了。f(60,60,60,60,60,60,60,60,60),我们的每一次抽取,都有可能让这9个参数的某一个减小1,(0减小1为0)……至于为什么上个帖中,我只用了三个大概是因为当时只考虑2套的情况吧…


      IP属地:北京来自iPhone客户端3楼2020-01-31 04:18
      收起回复
        白天更新一下结果

        再往后会有报错现象
        不过,我们可以发现 469.0855-448.9925=20=2*10
        所以m=60,EX的应该稍微小于648次
        而实际操作中,我达到55次拼图,使用了569次……这个数字与期望数字应当很接近
        再往后我就不使用随机拼图了


        IP属地:北京13楼2020-01-31 10:29
        回复
          解决了报错的问题
          第一列是m套拼图,选择了富有代表性的19种情况
          第二列是期望次数,如,60套拼图的期望抽取次数是648次(这是偶然吗……)
          第三列是第二列与第一列的商,表征在该状态下,单套拼图所需的次数,它显然会越来越小

          简单的可视化分析
          期望抽取次数EX关于目标拼图套数m是一个上凸函数,这里并没有考虑恒定的参数N=9的影响
          很明显,越往后走,它越接近直线
          30 347.6
          60 648.0……

          同时,我们得到单位所需次数(EX除以m)与目标拼图套数m之间的函数关系


          IP属地:北京22楼2020-01-31 22:07
          收起回复
            最后回到那个悬而未决的概率分布问题
            我们确实很难确定若干次抽取后能够集齐若干套拼图的概率,也无法知道最概然的次数在期望的左侧还是右侧
            但我个人的直观感受:实际的分布大概率倾向于,大多数人会以少于期望次数的拼图次数,完成若干套拼图
            (60次拼图的总开销,大概率不会超过648次,当然,这仅是对于本题概率分布的一种直观推测
            实际的情况如何,第四个难题的答案是什么,可能还要大佬们自己去验证和论证,我就不班门弄斧了)
            同时,如果合理地利用万能拼图,我们也能适当地减少开销
            以上的分析很可能说明,各种碎片应该是均等概率获得的
            本帖完


            IP属地:北京23楼2020-01-31 22:15
            回复