[数学]挑西瓜 (optimal stopping problem)

有N个房间,每个房间有一个西瓜,需要你挑出最大的那个西瓜.你需要按着房间顺序一个房间一个房间的查看西瓜.每当你看完一个房间的西瓜后,你需要立即决定是(1)挑选当前的西瓜还是(2)接着往下看.如果挑了当前的西瓜你就不能看后面其他房间.如果往下看了就要放弃当前西瓜而只能选择后面房间里的西瓜.使用怎样的策略能够让你最大化自己挑到最大西瓜的概率.

Sol: 这是传说中的Secretary Problem. 一个众所周知的算法是: 对于前s个房间只用于观察,我们记下前s-1个房间最大西瓜的尺寸.然后从第s+1个房间开始,一旦碰到比我们记下的尺寸还大的,就挑选之.如果一直没有碰到,就挑选最后一个房间里的.记Pr(s)为挑到最大西瓜的概率.

Pr(s) = \sum_{j=s}^n \frac{1}{n}\frac{s-1}{j-1}=\frac{s-1}{n}\sum_{j=s}^n \frac{1}{j-1}

这里1/n 是最大西瓜在第j个房间的概率,(s-1)/(j-1)是之前j-1个房间中最大的西瓜在房间1到房间s-1的概率. 可以证明s取n/e的时候这个概率取最大值.


Odds算法是该题另一种解法,事实上它的实用性更广.