secretary分析

到目前为止，我们对算法的分析都是基于算法在worst-case上的表现的。我们总会假设有一个adversary在已知我们设计的算法以后总会用一个最坏的输入来让我们的算法表现糟糕。然而我们发现，在某些在线算法问题下这样的分析方法太强了，以至于所有确定性算法甚至随机算法的竞争比都没有常数的竞争比，以至于worst-case分析无法比较不同算法之间的优劣。对此，一个解决方法就是采取一系列弱于worst-case的分析方法，也就是算法的beyond-the-worst-case分析。

Selecting the maximum

为了展示引入beyond-the-worst-case分析的必要性，我们考虑下面这个问题：有$n$个数依次到达，我们必须在线地选出$n$个数中最大的那个数。具体的，我们提前已知$n$的大小，接着每次会接收到一个输入数字$v_i$。对于每个接收到的数字，我们要么选择reject，然后接收下一个数；要么选择accept，不再接收输入。我们希望我们选择接受的那个数是这$n$个数中最大的那个。

Worst-Case Analysis

设$\text{OPT}$总是会选择最大的那个$v_{\max}$，$\text{ALG}$会选择$v_{\tau}$。如果用worst-case来分析，我们会用$\dfrac{v_{\tau}}{v_{\max}}$来定义竞争比，我们的目标是让$\dfrac{v_{\tau}}{v_{\max}}$尽量大。

对于确定性算法，这个问题的竞争比会趋向0。考虑$n=2$，如果算法总是选第一个数，那么只要第二个数比第一个数大$M$倍，算法的竞争比就是$1/M$；如果算法总是选第二个数，那么只要第一个数比第二个数小$M$倍，算法的竞争比也是$1/M$。当$M\to\infty$时，竞争比趋向0。

对于随机算法，竞争比依然会趋向0。由于输入数列的排列是任意的，没有理由设计一个倾向任何某个特定位置的随机算法。所以一个随机算法应该会以$1/n$的概率选择接受每个位置。那么我们可以构造这样一个输入序列：$1,M,M^2,\cdots,M^k,0,0,0,\cdots,0$。$\text{ALG}$的输出的期望是$\sum\limits_{i=0}^{k}\dfrac{1}{n}\cdot M^i=\dfrac{1}{n}\cdot \dfrac{M^{k+1}-1}{M-1}$，所以竞争比为$\dfrac{1}{n}\cdot \dfrac{M-1/M^k}{M-1}$。可见$M\to\infty$时竞争比为趋向$\dfrac{1}{n}$。因此当$n\to\infty$时，竞争比会趋向$0$。

Random Arrival - Secretary Model

由此可见，对于选最大数的问题，worst-case分析对于确定性算法和随机算法都失效了，因为worst-case下所有在线算法和最优算法相比表现都太差了。因此如果想要分析选最大数问题的在线算法，必须换一种分析方法。

在worst-case下，adversary能够选择$n$个数并以特意安排的顺序交给算法。现在我们弱化adversary的能力，考虑以下问题：已知$n$，让adversary选$n$个数，然后把这$n$个数随机打乱顺序以后，让它们依打乱后的顺序在线到达。我们分析算法选出这$n$个数中最大数的概率（这里的随机性来自这$n$个数被打乱时的随机性以及算法本身的随机性）。

这个模型称为secretary model，因为这就好像老板要从$n$个候选人中选择一个作为他的秘书，这$n$个候选人抽签决定面试顺序，在每个人面试完以后老板为了维护威严必须当场宣布是否录用。老板希望录用到最优秀的人的概率尽量大。在现代的文献中，secretary这个词就被等价地用来表示“Random Arrival”。

Wait-and-Pick

我们首先考虑下面这个确定性算法：总是拒绝前一半的数，记录下前一半数中最大的那个称为$m$，接着在后半段开始后选择第一个大于$m$的数作为输出（如果没有就输出$m$）。我们可以证明这个算法总是有$1/4$的概率回答正确：注意到，如果第二大的数出现在前半段，并且最大数出现在后半段，算法一定会输出正确。而第二大数出现在前半段的概率是$1/2$，最大数出现在后半段的概率是$1/2$。这两个事件不是独立的，但是它们是正相关(positively correlated)的，因为第二大数出现在前半段会让最大数更容易出现在后半段，最大数出现在后半段会让第二大数更容易出现在前半段。因此至少有$1/2\cdot 1/2=1/4$的概率最这两个事件同时发生，也即算法至少有$1/4$的概率会成功。这样我们就得到了一个竞争比为$4$的算法。

我们可以优化上面的算法。在上面的算法中，“前一半”事实上是我们选择了$50\%$这个常数。下面我们设这个常数是$c$，设$m=cn$。设最大数出现在第$t$个， 那么如果满足$t>m$并且前$t-1$个数中最大的那个落在前$m$个中，算法就会成功。可以枚举$t$，计算出概率$\sum\limits_{t=m+1}^{n}\dfrac{1}{n}\cdot \dfrac{m}{t-1}=\dfrac{m}{n}\sum\limits_{t=m+1}^{n}\dfrac{1}{t-1}=\dfrac{m}{n}(H_n-H_m)$。当$n\to\infty$时，$\dfrac{m}{n}(H_n-H_{m})\to \dfrac{m}{n}\ln\dfrac{n}{m}=-c\ln c$，$c\in (0,1)$。对$c$求导可得$c=1/e$时有最大值$1/e$。也就是说，我们总是拒绝前$n/e$的人然后选最大的那个，就能得到一个竞争比为$e$的算法。

我们可以证明，竞争比不能做得比$e$更好，也即不存在一个算法成功的概率超过$1/e$。我们可以设计如下动态规划：令$p[i]$表示如果强行拒绝前$i-1$个数，算法所能成功的最优概率。那么显然有$p[n+1]=0$，写出状态转移方程$p[i]=\dfrac{1}{i}\cdot \max(p[i+1],\dfrac{i}{n})+\dfrac{i-1}{i}\cdot p[i+1]$。其中，前一项表示第$i$个数恰好是前$i$个数中最大的，这一事件发生的概率是$\dfrac{1}{i}$，此时如果我们选择拒绝，那么算法成功概率是$p[i+1]$，如果选择接受，那么算法成功概率就是“前$i$个数中的最大数恰好是$n$个数中的最大数”这一事件的概率$\dfrac{i}{n}$；第二项表示第$i$个数不是前$i$个数中最大的，这一事件发生的概率是$\dfrac{i-1}{i}$，此时我们总是选择拒绝，因此概率是$p[i+1]$。可以看出，$p[i]$这一数列可以由递推计算得到。可以验证，$\forall i\in [n],p[i]\leq 1/e$。

Random Arrival with Time

还有一种等价地看“随机到达”的视角。在原来的设定下，当我们说“$n$个候选人以打乱顺序的方式到达”的意思是，我们会从$n$个数的$n!$个permutation中均匀随机采样一个来作为候选人的顺序。我们也可以引入“时间”的概念来等价地描述这件事。设我们独立重复地从实数闭区间$[0,1]$中采样$n$次，得到$t_1,\cdots,t_n$。把$t_i$分配给第$i$个候选人作为出场时间，那么显然这$n$个人的出场顺序的分布应当是均匀的（没有理由倾向任何某个特定的出场顺序）。在候选人有了出场时间$t_i$这一属性以后，我们可以把Wait-and-Pick算法修改如下：候选人按时到达，在时刻$\dfrac{1}{e}$以前，我们总是选择拒绝，并记下最大的数；在时刻$\dfrac{1}{e}$以后，选择最早到达的比记下的最大数大的那个数。

我们来分析这一修改后的算法的成功概率：设最大数在时刻$t$出现，那么当且仅当$t\in [\dfrac{1}{e},1]$才有可能成功。对于每个固定的$t$，我们能成功当且仅当第二大数出现在$[0,\dfrac{1}{e}]$当中，因此每个$t$对应的成功的概率密度为$\dfrac{1}{e}\cdot \dfrac{1}{t}$。根据全概率公式，算法的成功概率为$\displaystyle\int_{1/e}^{1}\dfrac{1}{et}\text{ d}t=\dfrac{1}{e}[\ln t]^1_{1/e}=\dfrac{1}{e}$。我们看到，用这种方式我们也得到了相同的概率。我们之后会看到，这种利用“到达时间”来刻画随机排序的视角是很有用的。

Ordinal Versus Cardinal

Secretary Maximum问题有一个变形叫Game of Googol，描述如下：在$n$张纸片上分别写下互不相同的$n$个不超过$10^{100}$的整数（这就是为什么游戏名字称为googol，因为googol就是$10^{100}$的意思），接着把这些纸片背面朝上然后打乱。我们每次可以翻开一张纸，然后决定是否选它作为最大值的决定。一旦决定就不能继续翻开别的纸。我们希望我们翻出最大数的概率尽量大。

我们看到game of googol这个问题和secretary唯一的区别在于，在game of googol中，一个数最大也不可能超过$10^{100}$，而secretary maximum中数字是没有上界的。换言之，在secretary中我们只能基于比较来得出最大值，而在game of googol中我们是有可能利用数字大小本身的信息来做判断的，比如如果翻出一个数已经非常接近$10^{100}$，我们大概率可以把这个数选为最大数。

基于比较的算法称为ordinal algorithm，基于数字具体大小的算法称为cardinal algorithm。显然ordinal algorithm不会比cardinal做的更好。

尽管可能采取的算法不同，以上两个问题本身都是最大化找到最大数的概率。换言之，任务本身是基于比较的，我们把这样的任务称为ordinal task。如果我们修改最大化的目标，比如改为最大化输出的数的期望，那么这就变成了一个cardinal task。这三个问题之间会有一些subtle difference，这里就不详细展开了。

Secretary Matching

接下来，我们用secretary model来分析二分图在线匹配问题。也即，我们要分析右侧节点以随机顺序到达的二分图在线匹配问题。我们考虑带权的二分图匹配，也即我们的目标是边权之和最大，而不是边数最多。对于二分图$G=(U\cup V,E)$，左侧的点$U$是offline的，$V$是随机到达的，每次到达时会给出与其相连的点以及对应的边权。我们需要在每个点$v$到达时就进行匹配的决策，不能后悔。

我们注意到，如果左侧点集$U$只包含一个点，那么这个问题就退化为了上一节讨论的在线选最大数问题：匹配就意味着选择，边权就是数。因此，我们现在其实是在讨论secretary问题的推广。

Wait-and-Match

于是，我们考虑把Wait-and-Pick算法也推广，称为Wait-and-Match。右侧在线到达的点共有$|V|$个，我们总是拒绝匹配任何最先到达的$|V|/e$个点。接着，对于第$t$个到达的点$v_t$，我们记$V_t=\{v_1,v_2,\cdots,v_t\}$，我们这样做决策：我们对于二分图$G$中由点$U\cup V_t$构成的导出子图做带权的最大匹配，设匹配结果为$\text{MWM}(U,V_t)$，如果$\text{MWM}(U,V_t)$中$v_t$被加入了匹配，设匹配边为$(u_t,v_t)$，那么我们观察当前在线算法中的$u_t$是否已经被匹配。如果已经匹配，那么拒绝匹配$v_t$；如果没有匹配，那么用$v_t$匹配$u_t$。

我们容易验证，以上算法对于$|U|=1$的情形就是Wait-and-Pick，因为$u_t$存在当前仅当当前数目前为止的最大数，也即第一个比前$|V|/e$个数中任何数都要大的数，此时我们做出匹配，也即做出选择。

下面我们来分析Wait-and-Match的竞争比。

首先，我们分析当我们匹配$(u_t,v_t)$时$\mathbb E[w(u_t,v_t)]$的大小。注意，这里的随机性来自$V$中节点到达顺序的随机性。注意到，第$t$条被匹配的边的权值的期望等价于前$t$条被匹配的边中最后一条被匹配的边的权值大小的期望。而由于到达是均匀随机的，因此前$t$条被匹配的边中，每一条的权值大小的期望都应当是相等的。因此有$\mathbb E[\text{MWM}(U,V_t)]=t\cdot \mathbb E[w(u_t,v_t)]$（$\text{MWM}$代表Max-Weighted Matching）。设$\text{OPT}=\text{MWM}(U,V)=\mathbb E[\text{MWM}(U,V_n)]$，其中$n$表示$\text{OPT}$中参与匹配的$V$中节点的个数，那么应当有$\mathbb E[\text{MWM}(U,V_t)]\geq \dfrac{t}{n}\mathbb E[\text{MWM}(U,V_n)]$，因为我们总可以选取$\text{OPT}$中匹配的边在$(U,V_t)$中形成一个“子匹配”，而系数$\dfrac{t}{n}$再次是由于每条匹配边的权重期望都相等。这样我们就得到了$\mathbb E[w(u_t,v_t)] =\dfrac{1}{t}\mathbb E[\text{MWM}(U,V_t)] \geq \dfrac{1}{t}\cdot \dfrac{t}{n}\text{OPT}=\dfrac{1}{n}\cdot \text{OPT}$。这说明，每一次匹配对结果的期望产生的贡献为$\dfrac{1}{n}\cdot \text{OPT}$。

下面我们证明，对于任意的offline点$u\in U$，在第$t$个在线点到达后它仍未被匹配的概率$\geq \dfrac{n}{et}$。首先注意到，对于某个固定的点$u$，它恰好在第$t$次被匹配的概率的概率为$\dfrac{1}{t}$，因为$\text{MWM}(U,V_t)$是一个确定性的结果，而$V_t$的顺序是均匀随机的。所以$u$没被匹配的概率$\geq \dfrac{t-1}{t}$进一步我们可以说，如果我们固定$V_t$是$V$中的一个子集$S$，那么一定成立$\Pr[u=u_t\mid V_t=S]\leq \dfrac{1}{t}$。那么就可以得到$u$在第$t$次以后仍未匹配的概率至少是它在第$t$次未被匹配、在第$t-1$次未被匹配、……、在第$n/e$次未被匹配这些事件同时发生的概率，所以$\Pr[u \text{ is unmatched at }t]\geq \dfrac{t-1}{t}\cdot \dfrac{t-2}{t-1}\cdots \dfrac{n/e}{n/e+1}=\dfrac{n}{et}$。注意，这里我们之所以可以直接把这些概率相乘，是因为这些事件是独立的，原因在于$\Pr[u=u_t\mid V_t=S]\leq \dfrac{1}{t}$这一结论是对于任何固定的$S$成立的，而不依赖于具体的顺序。这说明，每一个在线节点到达时能进行匹配的概率至少为$n/et$。

综上，我们分析算法的期望结果$\text{ALG}=\mathbb E[\text{MWM}(U,V_n)]$。从第$n/e+1$次开始枚举，我们已经计算得到每一次能进行匹配的概率时$n/et$，匹配产生的贡献的期望为$\dfrac{\text{OPT}}{n}$，因此$\text{ALG}=\sum\limits_{t=n/e+1}^{n}\dfrac{n}{et}\cdot \dfrac{\text{OPT}}{n}=\dfrac{\text{OPT}}{e}(H_n-H_{n/e})$，当$n\to\infty$时$H_n-H_{n/e}\to \ln n/(n/e)=\ln e=1$。因此$\dfrac{\text{ALG}}{\text{OPT}}\to \dfrac{1}{e}$。

综上， 我们证明了Wait-and-Match算法在期望意义下有竞争比$\dfrac{1}{e}$。我们注意到，这和上一节分析选最大数时的算法在形式上几乎是完全相同的，都是先忽略最早到达的特定比例的候选人，接下来贪心地选取。

Max-weight Forests

下面考虑这样一个问题：对于一张无向图$G=(V,E)$，边有边权且非负，要求出它的最大生成森林。注意对于$\text{OPT}$来说，最大生成森林就是最大生成树。现在考虑这个问题的secretary版本：边以随机顺序在线到达，我们需要在每条边到达时做出选或不选的决策。我们希望算法选出的最大生成森林尽量大。

对于这个问题，我们自然想要尝试使用和之前类似的算法：忽略前一小部分到达的边，接着对于每条边只要不成环就加入。可惜的是，可以证明这样的算法的竞争比不是常数（只需构造一个hat example，此处省略）。这意味着我们不得不尝试其它模式的算法。

我们提出下面这样一个算法，并证明这个算法有$\dfrac{1}{2e}$的竞争比。初始时，把$1,2,\cdots,|V|$打乱顺序形成一个随机的permutation $\pi$，并把它们分配给每个节点。这样我们就形成了节点间的一个随机的序关系。接下来，对于每条到达的边$(u,v)$，我们把它看作一条有向边，它从序较小的点指向序较大的点。对于每个节点，我们只考虑入边而不考虑出边。因此对于每个节点，可以看作有若干条入边随机到达。我们的算法是：用之前选最大数的$1/e$竞争比算法选出每个节点的恰好一条入边。为了做到这一点，我们可以采取“到达时间”的刻画，忽略时间$[0,1/e]$内到达的入边，接着选出第一条比之前所有边权值都大的边。

我们注意到，由于我们只在每个节点的入边中选择恰好选择一条，整张图上被选的边不可能形成环（这正是序关系的作用！），因此算法执行的结果一定是一个生成森林。并且，我们可以对算法结果给出如下分析：对于每个节点$u$，无向图上一条与$u$相连的边成为$u$的入边的概率恰好应该是$\dfrac{1}{2}$，算法选到的边至少是最大边$e_u^*$的$\dfrac{1}{e}$（因为这是一个$1/e$竞争比的算法！），因此$\text{ALG}\geq\dfrac{1}{2e}\sum\limits_{u\in V}e_u^*$。而显而易见的是，$\sum\limits_{u\in V}e_u^*\geq \text{OPT}$，这样我们就得到了$\text{ALG}\geq \dfrac{1}{2e}\text{OPT}$。所以这是一个$\dfrac{1}{2e}$竞争比的算法。

目前已知的这个问题的最优ratio是$1/4$，略大于$1/2e$。

Matroid Secretary

我们可以把Max-weight Forests的问题推广到一般的拟阵(matroid)上。

拟阵是指这样一类代数结构：称有限集合$M$能形成拟阵$(M,I)$，其中$I$是$M$的幂集的一个子集（也即一族$M$的子集的集合，$I$成为独立集），如果满足以下三个条件：(1) $\varnothing \in I$；(2) $\forall A \in I$，$\forall A'\subseteq A$，$A'\in I$，也即独立集的任何一个子集都是独立集，这个性质称为向下封闭性(downward-closed property)；(3) $\forall A,B\in I$， $|A|>|B|\implies$ $\exists x\in A\setminus B,B\cup\{x\}\in I$，也即如果独立集$A$比独立集$B$大小更大，那么总可以从$A$中挑出一个不属于$B$的元素使得$B$和这个元素拼成一个独立集。这个性质称为增广性(augmentation property)。

那么我们可以发现，以无向图的边集作为有限集合$M$，所有能形成生成森林的$M$的子集恰好形成了独立集集合$I$，$(M,I)$就构成了一个图拟阵(graphic matroid)。向下封闭性：一个生成森林的子集依然是一个森林；增广性：如果生成森林$E_1$比生成森林$E_2$边数更多，那么$E_1$中连通块数量更少，那么根据鸽巢原理至少存在$E_1$中的一个连通块横跨了$E_2$中的两个连通块，选取一条连接这两个连通块的边加入$E_2$依然会形成森林。

是否存在一个常数竞争比的Matroid-secretary算法仍是一个open problem。肯定这一事实的猜想就是所谓的Matroid Secretary Conjecture。

参考文献

https://en.wikipedia.org/wiki/Graphic_matroid

https://en.wikipedia.org/wiki/Matroid

Beyond the Worst-Case Analysis of Algorithms - Chapter 11 - Random-Order Models