猜硬币的游戏

Guess

快两个月没更新了,成天瞎忙…… 我们来看一个简单的题目吧,选自俄罗斯大神阿诺德(Влади́мир И́горевич Арно́льд)出的一百道题。[1] 题目是这样的:

一位游戏者藏起一枚 10 戈比或 20 戈比的硬币,另一位游戏者猜。猜对了就可以把硬币赢走,猜错了就要付出 15 戈比。这是个公平的游戏吗?双方最佳的混合策略是怎样的?

Continue reading “猜硬币的游戏”

随机多个色子的期望和方差

dice

这道题的原题来自于 Project Euler 389。

扔一个均匀的四面体色子,记下点数 T
T 个均匀的六面体色子,把所有的点数加起来,记为 C
C 个均匀的八面体色子,把所有的点数加起来,记为 O
O 个均匀的十二面体色子,把所有的点数加起来,记为 D
D 个均匀的二十面体色子,把所有的点数加起来,记为 I
I 的方差。

Continue reading “随机多个色子的期望和方差”

从一道赌博概率题说开去(三)

插进来说说我为什么忽然想起写这个问题。在刚刚结束的 ACM ICPC 2013 全球总决赛中,我大闵行理工学院再创佳绩,勇夺金奖第二名,值得祝贺!看看最后的比分榜,发现我们比获得桂冠的圣彼得堡国立信息机械与光学学院少做出一道 Problem B (Hey, Better Bettor) —— 这道题一共只有两支队伍做出来,分别是冠军/东道主和第三名的东京大学。我不是搞 ACM 的,但看到这个题目还是很感兴趣跃跃欲试。原题在这里

这道题实际上说的就是我们前面讨论的问题,不过这次换成了有“良心”的赌场。题目大意就是我们每次还是赌 1 块钱,你的胜率是 \( p\), \( 0\leq p< 50\),可以无限制地玩下去。玩到最后,如果你赢了钱自然都归你;如果你亏了钱,赌场可以返还你一个比例 \( x\%\), \( 0\leq x<100\)。返还没有时间和额度的限制,但是只能返还一次。现在要写一个程序,给定胜率和返还比例(精确到两位小数),要求出在任意策略下赢钱的最大期望。

Continue reading “从一道赌博概率题说开去(三)”

从一道赌博概率题说开去(二)

接着上一篇的话题。上一篇我们谈到的一个重要前提,是说这个赌博是“公平”的,胜负概率各半。在公平博弈里,资金 \(X_n\) 的期望维持稳定,因此它是一个鞅。可实际上的赌场显然不是公平的,虽然很多游戏看起来离公平也并不太远,比如玩家的胜率是 \(p = 49\%\),庄家胜率是 \(51\%\) 之类。这时的条件期望
\[
\mathbb{E}[X_{n+1}|X_1, X_2,\ldots , X_n] = X_n + \big[ p \cdot 1 + (1-p) \cdot (-1) \big] \leq X_n
\] 是不断降低的,那么这个过程就称为一个上鞅。只要你一直玩一直玩,最后肯定会输得连内裤都不剩。

知道了这个不等式似乎还不太够——我们想知道能赢 100 块离场的概率。这个时候就需要构造一个新的鞅,稳定的东西才好解嘛。我们希望找到一个函数,使得
\[
\mathbb{E}[f(X_{n+1}) |X_1,X_2,\ldots,X_n] = f(X_n)
\] Continue reading “从一道赌博概率题说开去(二)”

从一道赌博概率题说开去(一)

最近网上有一道题很流行,题目是这样的:

你拿 10 块钱去赌场赌大小,你有两种玩法,一种是每次赌 10 块,一种每次赌 1 块,你决定都是输光或者赢到 100 块就走,则
A 两种方法输光的概率一样
B 第一种输光的概率较大
C 第二种输光的概率较大

不知道你的感觉如何 —— 你也许觉得要是赌 10 块的话一把就可能输光了,赌 1 块还可以搞许多把 —— 我们先把这个感觉放到一边,来分析一下这个情况到底是怎样的。

Continue reading “从一道赌博概率题说开去(一)”