智游城

标题: 想了个概率题目，有兴趣的来看看 [打印本页]

作者: notch 时间: 2013-2-8 13:58
标题: 想了个概率题目，有兴趣的来看看
每个盒子里或者是空的，或者是有一枚金币
将10个盒子作为一组，一共有10组盒子
每组盒子的金币总数不同，最少0枚，最多9枚
游戏规则：
你可以开任一组盒子中的任一个，看到是否有金币，如果有金币，你可以拿走。
接下来你可以选择把这一组全打开，拿走所有的金币，然后游戏结束
或者选择去开下一组盒子中的某一个，继续选择是否打开新的一组
一旦决定打开一组盒子，游戏结束
否则一直继续下去，直到没有盒子
问：有没有什么策略可以让得到的金币概率上最多

作者: Howard 时间: 2013-2-9 01:33
游戏规则好像少说了一句话。

按题设，就一直开单个盒子就可以了，一直从#1开到#100，取走所有金币

可能是这样一句话：“一旦开了某组内的任一盒子，又不选择全部打开该组，则该组其他盒子不允许再打开”

另外盒子里面或者空的，或者有1枚金币，空的跟有金币的盒子是50% vs 50%的概率吗？还是不清楚

作者: maomaobiao 时间: 2013-2-9 14:14
本帖最后由 maomaobiao 于 2013-2-9 17:24 编辑

Howard 发表于 2013-2-9 03:33
游戏规则好像少说了一句话。

按题设，就一直开单个盒子就可以了，一直从#1开到#100，取走所有金币

回答你最后一个问题，应该是这么理解：

在总共有 0 枚金币的那十个盒子，有金币的概率全部 = 0%

在总共有 1 枚金币的那十个盒子，有金币的概率平均值 = 10%

在总共有 2 枚金币的那十个盒子，有金币的概率平均值 = 20%

......

在总共有 9 枚金币的那十个盒子，有金币的概率平均值 = 90%

------------------------------

1. 在第一次任意打开某一组盒子中的某一个，得到金币的概率是 (0+0.1+0.2+... +0.9)/10 = 45% (也就是总共45枚金币分布在100个盒子里)

  1.1 当打开第一个盒子为空，游戏结束，金币的期望 = 55%*0 = 0
  1.2 当打开第一个盒子为金币，可以
   1.2.1 打开这一组的10个盒子，游戏结束，金币的期望 = 45% * （1*0.1 + 2*0.1 + 3*0.1 +... 9*0.1）= 2.02
   1.2.2 打开另一组的某个盒子，进入2.
在第一步结束游戏的金币期望值为2.02

2.这里需要计算一下概率，如果简化地认为45枚金币平均低分布在100个盒子，则剩下90个盒子里平均分布了45-4.5 = 40.5个金币，第二步打开金币的概率 = 40.5/90 = 45%，不变。

  2.1 当打开第二个盒子为空，游戏结束，金币的期望 = 0
  2.2 当打开第二个盒子为金币，可以
   2.2.1 打开这一组的10个盒子，游戏结束，金币的期望 = 2.02

如果以上的计算正确，那么在任何一步的金币期望都是2.02。等等，但是45枚金币并非平均分布在100个盒子里，在第一打开金币之后，十个盒子全部为空的权重上升，也就是说，在第二步打开金币的概率是略低于45%的。或者这么理解，已经有一枚金币被用掉了，所以，第二步打开金币的概率 = （45 - 1 - 0.45*9）/ 90  =44.39%。

于是乎，第二次打开那一组盒子结束游戏的金币期望实际上要低于2.02。
依次类推，在第一次打开是金币的时候，就果断打开这一组盒子，应该是最优策略。

粗略想的结果是这样，有待推敲。

作者: maomaobiao 时间: 2013-2-9 14:26
我好像忽略了，可以拿走已到手的金币这个条件

作者: 天使也无奈 时间: 2013-2-9 18:16
那么复杂的

作者: maomaobiao 时间: 2013-2-10 08:05
简化一个条件：

当打开一个盒子发现金币之后，如果选择打开这一组余下的所有盒子，则

1/9 可能 0 more
1/9  1 more
1/9  2 more
...
  1/9 9 more

所以，在这个相对独立的事件中，只要发现金币，并且打开余下的盒子，就可以默认得到了 5 个金币。

------------------------------------

策略 1 :　在打开第一个盒子，发现是金币时就打开余下的盒子，终止游戏。

　　　55%　什么也得不到
　　　45% 得到5个金币
　　total EV  = 5*45% = 2.25

策略 2:　在打开第二个盒子，发现是金币时就打开余下的盒子，终止游戏。

　　　55% 什么也得不到
　　　45% 得到一个金币之后，又有55.56%什么也得不到
　　　45% 得到一个金币之后，又有44.44%再得到5枚金币
   total EV = 45% * (1 + 5 * 44.44%) = 1.44

.....

最优策略就是，第一次打开盒子就中止游戏。

作者: notch 时间: 2013-2-13 17:07
可能题目里头有歧义
如果开出来的箱子里头没有金币
你仍然可以选择是否开这一组箱子
或者放弃这一组箱子
选择开下一组箱子中的一个

作者: maomaobiao 时间: 2013-2-14 08:32
本帖最后由 maomaobiao 于 2013-2-14 10:34 编辑

notch 发表于 2013-2-13 19:07
可能题目里头有歧义
如果开出来的箱子里头没有金币
你仍然可以选择是否开这一组箱子

就是说不管开没开出来金币，都可以选择

1. 打开这一组盒子
2. 打开另外一组（没有被开过的盒子）。

一直开最多有10次机会，第十次不论结果如何，只能打开眼下这一组的盒子。是这个意思吧？

-------------------------------

极端的情况，开10次，得到9个金币，或者0个；从平均的期望看45个金币分布在100个盒子里，开10次可以得到 4.5个金币。

而我们也知道，不管如何同一组的10个盒子，可以默认为里面有4.5个；但是，一旦打开其中一个发现有金币，则这10个盒子则应该默认为有5个金币。

------------------------------------

继续极端的情况，最大收益是，开10次，得到9个金币，然后最后一组开出额外8个，总共17个金币；或者，开10次得到0个金币，然后最后一组什么也没有，总共0。算术平均是8.5个，但是从概率的平均分布看，我们应该得到4.5+4.5 = 9个金币。

所以，估计一下，最优解因该是一直开，直到开出5个金币（或者开10个得到小于5个金币），然后在开出第5个的时候打开那一组的盒子，得到5+4 = 9个金币。具体的计算回头再弄吧，太麻烦了。

欢迎光临智游城 (http://zhiyoucheng.co/)