快两个月没更新了，成天瞎忙…… 我们来看一个简单的题目吧，选自俄罗斯大神阿诺德（Влади́мир И́горевич Арно́льд）出的一百道题。[1] 题目是这样的：
一位游戏者藏起一枚 10 戈比或 20 戈比的硬币，另一位游戏者猜。猜对了就可以把硬币赢走，猜错了就要付出 15 戈比。这是个公平的游戏吗？双方最佳的混合策略是怎样的？
标签： 概率
任意两个自然数互质的概率？
试问：任取两个自然数，它们互质的概率是多少？即以等概率取两个自然数 \( x, y \in \{1,2,\ldots,n\}\)，令 \( P_2(n)\) 是 \(x\)、\(y\) 互质的概率，求 \(\lim_{n\to \infty} P_2(n)\) 。
随机多个色子的期望和方差
这道题的原题来自于 Project Euler 389。
扔一个均匀的四面体色子，记下点数 T；
扔 T 个均匀的六面体色子，把所有的点数加起来，记为 C；
扔 C 个均匀的八面体色子，把所有的点数加起来，记为 O；
扔 O 个均匀的十二面体色子，把所有的点数加起来，记为 D；
扔 D 个均匀的二十面体色子，把所有的点数加起来，记为 I；
求 I 的方差。
从一道赌博概率题说开去（四）
你也许已经注意到，前面谈到非公平赌博的时候每次都是赌 1 块钱。要是加大赌注会不会有影响呢？
从一道赌博概率题说开去（三）
插进来说说我为什么忽然想起写这个问题。在刚刚结束的 ACM ICPC 2013 全球总决赛中，我大闵行理工学院再创佳绩，勇夺金奖第二名，值得祝贺！看看最后的比分榜，发现我们比获得桂冠的圣彼得堡国立信息机械与光学学院少做出一道 Problem B (Hey, Better Bettor) —— 这道题一共只有两支队伍做出来，分别是冠军/东道主和第三名的东京大学。我不是搞 ACM 的，但看到这个题目还是很感兴趣跃跃欲试。原题在这里。
这道题实际上说的就是我们前面讨论的问题，不过这次换成了有“良心”的赌场。题目大意就是我们每次还是赌 1 块钱，你的胜率是 \( p\), \( 0\leq p< 50\)，可以无限制地玩下去。玩到最后，如果你赢了钱自然都归你；如果你亏了钱，赌场可以返还你一个比例 \( x\%\), \( 0\leq x<100\)。返还没有时间和额度的限制，但是只能返还一次。现在要写一个程序，给定胜率和返还比例（精确到两位小数），要求出在任意策略下赢钱的最大期望。
从一道赌博概率题说开去（二）
接着上一篇的话题。上一篇我们谈到的一个重要前提，是说这个赌博是“公平”的，胜负概率各半。在公平博弈里，资金 \(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 块还可以搞许多把 —— 我们先把这个感觉放到一边，来分析一下这个情况到底是怎样的。
相邻的树上会有多少鸟？
有一个很有意思的问题是这样的：说有一片树林是 38 棵树排成一圈，有 11 只鸟住在这片树林里，每天晚上都会回来。试证明一定存在相邻的 7 棵树上至少住着 3 只鸟。
能够连续扔出几个正面呢？
去年写过一篇博客平均投几个三分才会连续进 3 个？，现在我们再回过头来看一个类似的问题。假如我们连续扔硬币 100 次，那么大约最多会连续出现几个正面呢？
随机把绳子剪开，最短一段会有多长？
这是个很经典的题目哈，把一根一米长的绳子随机剪成几段，最短一段的期望应该是多少呢？
