SPECODER's Blog

退而求其次:

如果你把眼光稍为放低一点， 能够选中第一名或第二名就好的话，那么你应该采取怎样的手段?

很自然地，一开始你仍应按以前的办法进行，自第 r 位起，等候第一个临时第一名。但是如果等了一段时间，还未出现，这是会有疑虑: 是不是第一名已成漏网之鱼? (已经在最前面r -1位中出现了)。所以你应该自第s位( s > r )起，首次碰到临时第一名或临时第二名时，你都一把抓住，因为临时第二名也可能会是实际第二名。我们也可以证明，最好的手段，就在这一类里，不过我也不证明了。我再简写如下：

最佳的选择：

首先我们先规定几个标记，以方便论证：

:表示第 k 个物品的名次，即实际名次。显然，这是个随见变量，而且我们对于该名次，之前是一无所知的，但是我们知道的，是每个物品的临时名次，也就是说，当我们看到第 k 个物品时，该物品在前 k 个物品中排第几我们是知道的。

前面简单的办法，即放弃前面一半，结果已经十分不错了，我们自然会想到跟一般的办法。

首先让我们看一个问题：

You are observing a sequence of objects which can be ranked from best to worst. You wish to choose a stopping rule which maximises your chance of picking the best object.

Here, if  (n is some large number, perhaps) are the ranks of the objects, and y_i is the chance you pick the best object if you stop intentionally rejecting objects at step i, then (R_i) and (y_i) are the sequences associated with this problem.