V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
这是一个专门讨论 idea 的地方。

每个人的时间,资源是有限的,有的时候你或许能够想到很多 idea,但是由于现实的限制,却并不是所有的 idea 都能够成为现实。

那这个时候,不妨可以把那些 idea 分享出来,启发别人。
morningD
V2EX  ›  奇思妙想

吃火锅想到的一个概率问题:锅里还剩几个蛋

  •  1
     
  •   morningD · 2020-06-26 16:10:32 +08:00 · 5107 次点击
    这是一个创建于 1372 天前的主题,其中的信息可能已经有所发展或是发生改变。
    背景:假如我去吃火锅,已知锅里有 N 个鹌鹑蛋,我想要把这些蛋捞来吃。每个蛋被捞到的概率均为 P (重庆火锅红汤,看不到锅底,),并且一次捞出的个数没有限制。但是,如果我连续 T 次都没捞到,那我就会放弃。

    问题:当我放弃后,锅里剩下的鹌鹑蛋的个数的期望 E 是多少?(可以假设 N=10, P=0.2, T=5 )

    这应该是一个概率论问题,一直没想到如何得到公式解。用程序模拟得到数据解应该是可行的。
    第 1 条附言  ·  2020-06-27 15:16:31 +08:00

    补充一下结论: N=10, P=0.2, T=5的情况下,E=0.5499853034737232(根据9楼的DP解法得到)

    结果可以参考下图: hotpot

    左图是我用程序模拟的,右图是DP解法。E随着T的增加快速下降,N的增加不会带来E的显著提升。可以看到坚持捞5次是不错的选择,E<1。

    可以总结出一个有趣(但无用)的吃蛋小技巧,无论放了多少蛋在锅里,当你的耐心值 T 固定时,剩下的蛋的期望是基本一致的。

    36 条回复    2020-07-01 09:32:06 +08:00
    daen
        1
    daen  
       2020-06-26 16:27:05 +08:00   ❤️ 1
    瞎猜一下:N*(1-P)^T
    morningD
        2
    morningD  
    OP
       2020-06-26 16:51:49 +08:00
    @daen 你的思路是转换成等价的问题吧。对于每个蛋来说,连续 5 次没被捞到的概率是(1-P)^T,所以根据二项分布的期望,剩下的个数的期望是 N*(1-P)^T 。感觉挺合理的
    murmur
        3
    murmur  
       2020-06-26 17:02:02 +08:00
    E=0,因为你捞不出来那肯定是都被别人捞走了,吃火锅是那么大一个漏勺,如果你鹌鹑蛋都捞不出来他大概率就是没了
    vinew
        4
    vinew  
       2020-06-26 17:07:26 +08:00 via iPhone
    @murmur 那如果一个人吃海底捞的情景,蛋一定是被服务员捞走了🤣
    gwy15
        5
    gwy15  
       2020-06-26 17:17:46 +08:00
    能解出来解析表达式,我得写写。最后得解一个 n 元 1 次方程,或者递归也可以。
    Jooooooooo
        6
    Jooooooooo  
       2020-06-26 17:18:51 +08:00
    挺好的问题, 可以上知乎问问
    murmur
        7
    murmur  
       2020-06-26 17:22:17 +08:00   ❤️ 2
    既然有兄弟想认真讨论,我就写几句
    这种把现实生活转到数学上肯定加了巨多的限制,否则没法解,比如我提几个
    1 、楼主捞蛋是怎么进行的,是一个地方一下还是围着锅转一圈
    2 、有其他的食材干扰楼主判断么,比如你是捞到大的东西就去看一下
    3 、总在一个地方捞么,如果捞不到会不会换地方
    4 、有没有其他人干扰你捞食材
    本人挑食,涮锅子基本上荤菜只吃鹌鹑蛋,专业捞蛋选手,只要锅里有我绝对能给他捞出来,你还想让我放弃
    TigerK
        8
    TigerK  
       2020-06-26 17:50:21 +08:00
    额,吃火锅从来没点过鹌鹑蛋,想问问好吃不?是连壳子一块下去煮吗?
    gwy15
        9
    gwy15  
       2020-06-26 18:39:08 +08:00   ❤️ 5
    https://gwy15.com/blog/%E7%81%AB%E9%94%85%E6%8D%9E%E8%9B%8B

    v 站不支持公式,我丢我博客去了。相对于直接求解 DP 的 O(n^2 T) ,把复杂度降到了 O(n^2)。由最后的分式结果我比较怀疑能找到 O(n) 的解法。
    sephinh
        10
    sephinh  
       2020-06-26 18:56:27 +08:00 via Android
    在你思考这个问题的时候,蛋已经全被别人拿漏勺打扫干净了....
    murmur
        11
    murmur  
       2020-06-26 18:57:32 +08:00
    @TigerK 很好吃,一般都是剥皮煮熟的给你,自助火锅可能要自己剥皮
    morningD
        12
    morningD  
    OP
       2020-06-26 19:06:23 +08:00
    @daen 我写了一个简单的程序验证了一下,根据前面假设的数值,循环 1000 次的平均期望是 0.001 ,N*(1-P)^T=3.2768,所以你的猜想大概率不正确
    morningD
        13
    morningD  
    OP
       2020-06-26 19:07:29 +08:00
    @TigerK 还不错哦,基本每次必点,一般都是煮好的并剥好的,烫一下就能吃
    morningD
        14
    morningD  
    OP
       2020-06-26 19:11:39 +08:00
    @sephinh 哈哈,但是这又回到了这个概率问题,别人如何确定已经打扫干净了呢?根据我多次吃火锅(红汤)的经验,永远不知道锅底还剩下什么
    morningD
        15
    morningD  
    OP
       2020-06-26 19:13:49 +08:00
    @murmur 其实我就想知道的就是这个“大概率”是多少
    morningD
        16
    morningD  
    OP
       2020-06-26 19:23:08 +08:00
    @gwy15 非常感谢,我去写个程序验证一下。另外,咱把这个问题扩展一下,如果希望期望<e,那么 T 的最小下界应该是多少呢?
    假如 e=1,是的,我最多只能忍受送一个蛋给服务员,那我应该怎么捞
    Elethom
        17
    Elethom  
       2020-06-26 19:31:12 +08:00 via iPhone
    感觉这里用户的统计学水平还不如手游玩家,这种抽卡期望的问题早就被研究透彻了。

    帮你转化一下:十连抽,SSR 掉率 20%,抽到就收手,抽五次还没抽到就不抽了。
    morningD
        18
    morningD  
    OP
       2020-06-26 19:35:31 +08:00
    @Elethom 不是等价的问题,锅里蛋的个数是固定了,并且也有一次捞到多个的情况
    Elethom
        19
    Elethom  
       2020-06-26 20:05:01 +08:00
    @morningD 你再想想。
    murmur
        20
    murmur  
       2020-06-26 20:11:13 +08:00
    @Elethom 抽卡也是不一样的,fgo 国服以前有保底,比如说 5%的概率,那 20 抽(次)就是必出
    murmur
        21
    murmur  
       2020-06-26 20:14:10 +08:00
    楼主这个问题应该假设为,一个锅里分布着鱼蛋和鹌鹑蛋,问捞起鹌鹑蛋的期望是多少,先简化问题才能分析,首先得保证能捞到东西,如果捞不到东西我就会满锅扒拉
    dingyaguang117
        22
    dingyaguang117  
       2020-06-26 20:27:40 +08:00
    因为连续捞 T 次没捞到,这个过程就会结束。所以这个动作序列的总长度为

    (T-1)*(N-1) + 1 。

    我觉得可以用暴力搜索解决
    dingyaguang117
        23
    dingyaguang117  
       2020-06-26 20:28:18 +08:00
    @dingyaguang117 更正,总长度最大为 (T-1)*(N-1) + 1
    morningD
        24
    morningD  
    OP
       2020-06-26 20:35:57 +08:00
    @morningD
    @daen 12 楼的模拟错了,应该是 0.615 。sorry
    Elethom
        25
    Elethom  
       2020-06-26 20:43:20 +08:00 via iPhone
    @murmur 杠精?
    morningD
        26
    morningD  
    OP
       2020-06-26 21:08:29 +08:00
    @Elethom 你是正确的。准确来说,对应的是有 N 个 SSR,连续 5 次 10 连没抽到新卡就放弃的情况。
    daen
        27
    daen  
       2020-06-26 21:34:26 +08:00 via iPhone
    @morningD 的确,我给的算法有很大问题,没有考虑蛋和蛋相互之间的影响,这导致了最终结果的误差非常大
    newtype0092
        28
    newtype0092  
       2020-06-26 23:50:40 +08:00   ❤️ 2
    @murmur “每个蛋被捞到的概率均为 P,并且一次捞出的个数没有限制”,这个就是明确的数学条件,背景只是套一个场景,条件一致的情况下用勺子捞蛋看是否捞出和扔骰子看点数没有区别,讨论概率问题谁管你说的那些“情况”。
    murmur
        29
    murmur  
       2020-06-27 00:02:19 +08:00
    @newtype0092 好吧,这么复杂的一个问题就被简化为这么简单一个模型,还一时间让人接受不了
    xiadong1994
        30
    xiadong1994  
       2020-06-27 02:43:12 +08:00
    @morningD 建议你把你的模拟代码发出来,这种概率问题的“模拟”程序很有可能有错。
    sixg0d
        31
    sixg0d  
       2020-06-28 06:28:48 +08:00   ❤️ 1
    初高中搞数学竞赛的对这种题就不陌生了,记得华东师大的竞赛丛书里有一册讲概率的,很多这种类型的题,还套上了驴象之争、东风西风之类的背景,挺有意思的。

    9 楼 @gwy15 给出的(1.7)式可以直接推出来的。根据(捞到的)首次捞出来的个数分情况(也就是求条件期望),如果一直没捞到,就是式中的首项,首次捞到 L 个蛋的条件下,最后的期望就是 f(n-L),而捞到 L 的概率就是若干次(0~T-1)捞空紧随着一次 L 的概率,也就是(1.7)式中 f(n-L)的系数。具体的求和号前是若干次捞空的概率,后面是捞 L 的二项式概率。
    sixg0d
        32
    sixg0d  
       2020-06-28 06:52:43 +08:00
    至于你说的期望不太受 N 影响,用这种递推想法可以很直观得解释:有 N 蛋而结束捞蛋的概率是(1-p)^{NT},所以有很大概率会继续捞下去,所以最后的期望约等于 N 比较小的时候。至于 N 比较小时期望的变化,以及你所说的合理策略,其实是跟 p 有关的
    967182
        33
    967182  
       2020-06-28 16:09:24 +08:00
    哎,我次火锅的时候就光顾着捞了,捞完就往嘴里塞,重来没想过这么高深的问题。
    zhuweiyou
        34
    zhuweiyou  
       2020-06-29 14:45:12 +08:00
    蛋不够了,喊服务员再叫一盘吧。
    garyzhuang
        35
    garyzhuang  
       2020-06-30 17:59:08 +08:00
    这取决于汤勺的大小吧
    richieboy
        36
    richieboy  
       2020-07-01 09:32:06 +08:00
    P 的值明显是越来越小的
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2812 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 14:59 · PVG 22:59 · LAX 07:59 · JFK 10:59
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.