雇用问题

在新的一年里，你摇身一变成为了一个big boss，接下来你要雇佣一堆手下来给你干活，但是有了好的还会想要更好的，于是乎，你决定每天都进行面试，一旦面试到了新的更好的员工就把原来的员工换掉，为此你特底雇佣了介绍人，他会每天给你介绍一个人来让你进行面试。于是乎你每天的任务就是，面试，考虑要不要雇佣。

basic employ = 0
for i in 0 to n:
    interview candidate i
    if i better basic employ:
        basic employ = i
        hire candidate

这里我们假设该岗位的初始员工是最差的，随后的每个面试遇到了更好的就会进行雇佣然后把原员工替换掉。和以前有所不同的是，在这里我们不考虑算法的运行时间，而是考虑雇佣的成本，但这两者本质上是相同的，我们假设每天面试所需要消耗的成本为a，那么我们对n个人进行面试的总成本就是an，我们假设雇佣一个人的成本是b，我们雇佣了m个人，那么我们雇佣的总成本既是bm，这样看来，我们一共消耗的费用就是O(an+bm),其中的an是固定的，可操作空间在于bm，那么如果要使我们的消费尽量少的话，我们就要尽量少的进行雇佣。但谁也不知道这个是不是最好的，下一个会不会更好。

随机算法

虽然从表面上来看来面试人的质量是随机的，但事实上我们不能保证，假如人家商量好按照level从小到大来面试呢？所以我们需要将随机的权力掌握在我们自己手里，例如我们将所有要面试的人汇总在一张表上，只看名字，每天随机抽取一个幸运面试者。这种进行了随机化处理而不是单纯依赖于原始输入情况的算法我们称之为随机算法，通常利用random函数生成随机数对输入进行随机化，而对于随机算法我们一般计算它的期望运行时间来进行评估。

指示器随机变量

给定一个样本空间S和一个事件A，那么事件A对应的指示器随机变量I{A}定义为：
{ 1 如果A发生
I{A} = I
{ 0 如果A不发生

举个例子，对于抛硬币而言就是样本空间S有两个，一为正面向上H，二为反面向上T，也就是S={H,T}。而且易知P{H}=P{T}=1/2。接下来定义一个指示器随机变量X_H ，对应着硬币正面向上的事件H。这个变量计数抛硬币时正面向上的次数，正面向上为1，反面向上为0。所以
{ 1 正面向上，H发生
X_H =I{H}= I
{ 0 反面向上，T发生

所以在抛硬币中，正面向上的期望就是指示器变量X_H的期望值：
E[X_H]=E[I{H}]= 1 * 1/2 + 0 * 1/2 = 1/2
因此抛一枚硬币的时候，正面向上的期望次数为1/2。

那么如果我们抛n次硬币，正面向上的次数会为多少呢？这种情况下我们就需要考虑一个，两个，三个......n个硬币正面向上的概率。我们设指示随机变量X_i 对应第i次抛硬币正面向上的事件，X_i = I{第i次抛掷时出现事件H}。设随机变量X表示n次抛硬币中出现正面的总次数，即X=∑ⁿ_i=1 X_i 。对其求期望为E[X] = ∑ⁿ_i=1E[X_i],易知E[X_i] = 1/2，所以E[X] = n/2。

用指示器随机变量对于雇佣问题的分析

对于雇佣问题，我们需要考虑的是是否要对该员工进行雇佣，所以样本空间也是两个，雇佣为Y，不雇佣为N，即为S={Y，N}，所以我们定义一个指示器随机变量X_Y ，对应着我们对员工进行雇佣的事件Y。
{ 1 对员工进行雇佣，Y发生
X_Y = I{Y} = |
{ 0 不对该员工进行雇佣，N发生

所以期望值显而易见为E[X_Y] = 0 * P{N} + 1 *P{Y} = P{Y}。那么我们进行n次面试，考虑我们进行的雇佣次数，我们可以设X_i 对应第i次面试进行雇佣，X_i = I{第i次面试时发生事件Y}，设随机变量X表示n次面试中雇佣的总次数，即X=∑ⁿ_i=1 X_i，期望为E[X] = ∑ⁿ_i=1E[X_i]，在第i次面试中，如果要进行雇佣，即意味着这个面试者会比前面i-1名面试者都更优秀，因为面试的顺序是随机的，所以第i名面试者比之前的的面试者更优秀的概率为1/i，即他有1/i的概率被雇佣，所以E[X_i]=1/i。E[X] = ∑ⁿ_i=11/i = ln n+O(1),（运用了调和数集的）。