Day-16 雇用问题, 指示器随机变数(indicator random variable), 随机化演算法

雇用问题

假设你要雇用新的办公助理，而你找了一个雇用代理人去帮你推荐应聘的人，雇用代理人每天会给你推荐一个人。接着你会去面试这个人，并决定是否要雇用他。

因为雇用代理人帮你筛选出合适的应聘人，所以我们必须给雇用代理一笔费用。如果该应聘人成功通过了面试，那麽我们就将目前的办公室助理辞去，并支付给雇用代理人仲介费。

如果日後又出现更好的办公助理，则会将目前的办公助理辞去，然後雇用新的，我们希望能够估计一下这麽做我们需要花费多少钱。

下面HIRE-ASSISTANT的虚拟码表示以上的想法。假设将来应徵办公助理的人依序编号1号到n号。整个过程就是面试完第i号人後，决定面试者i号是否为目前最好的人选，初始化时，会假设第0号为所有候选人中最差的。

HIRE-ASSISTANT(n)
best = 0 // 第0号候选人(最差的)
for i  = 1 to n
    interview candidate[i]
    if candidate[i] is better that candidate[best]
        best = i
        hire candidate[i]

我们关心的是我们所需要花费的费用，而非执行的时间，假设面试费用需要，雇用需要。有个人来面试，个人会被雇用，那麽总花费为，不论我们最终雇用了多少人，我们都需要和个人进行面试，因此，我们专注在分析的部分。

这个场景和在阵列中寻找出最大值和最小值很像，透过遍历整个阵列，每一次纪录当前的最大值或是最小值，透过不断的更新值直到遍历完整个阵列我们即可得知最大值和最小值。

最坏情况

最坏的情况下，就是来了n位面试者，第1位面试者为最差的面试者，第2位面试者为第2差的面试者，第n位面试者为最好的面试者，这种情况下，雇用的费用为

在通常情况下，当然不会有这麽刚好的事情发生，而在分析这个问题时，我们必须知道在n位面试者中，每位面试者程度的分布情况，也就是平均分布的情况，我们希望最好的面试者出现在每一个编号的机率是均等的，也就是。

机率分析

机率分析，广泛的使用在分析演算法中，例如在分析演算法执行时间，我们产生出所有可能的输入来得到演算法的时间，并取平均值，得到的值即为平均情况执行时间。

对於某一些问题，如果他的输入是可以进行一些规范或是假设的，例如假设所有输入情况都是可能发生的，且发生机率皆均等，那就可以使用机率分析的方式设计演算法。如果输入是无法预测的，那麽使用机率分析的方式设计演算法便是不可行的。

在雇用问题中，可以假设每一个面试者都是以随机的顺序出现，这也表示任两个面试者之间有一定的比较关系，可以让我们进行比较，比较出谁具有资格，也可以对其进行排名。面试者是依照随机顺序排列，假定有个面试者，那麽可以预期会出现种排列的方式，且每一种排列方式出现的机率皆均等。

随机化演算法

有时候我们对於输入的情况无法去掌握，而我们为了利用机率分析的方式去设计演算法，我们会在演算法中某一个部分进行随机化，让机率的平均分布情况不取决於输入的情况，而是根据随机数产生器等等。

在雇用问题中，我们假设面试者的顺序是随机的，但我们无法确保这件事情发生，为了使用机率分析的方式设计出演算法，我们改变了HIRE-ASSISTANT(n)，我们假设雇用代理人每天会推荐给我们位面试者，而我们要从位面试者中随机选出一位来进行面试，而这样做可以使得面试者的顺序更加的随机。

如果一个演算法不仅仅取决於它的输入，也取决於随机数产生器(random-number generator)产生出来的数值，那麽我们可以说这个演算法是随机的(randomized)。

在分析一个随机化演算法的执行时间，我们以执行时间的期望值进行衡量，而出来的时间我们称为期望执行时间。

一般来说，当机率分布是取决於演算法的输入上，我们会讨论的是平均执行时间。而当演算法本身具有随机选择，岁是有一些随机因子，像是乱数产生器等，我们会讨论他的期望执行时间。

指示器随机变数(indicator random variable)

为了分析演算法的情况，这里引入指示器随机变数的概念。可以让机率和期望值之间更方便的进行转换。给定样本空间S，事件A，那麽事件A对应到的指示器随机变数定义为

举一个简单的例子，我们试着求出硬币投掷出现正面朝上的期望次数。样本空间为(样本空间表示所有事件的集合，以硬币来说，就有正正,反反,正反,反正)，其中正面和反面皆为， ，接着定义指示器随机变数，对应到发生硬币正面朝上的事件。这个变数作为计数器，纪录硬币正面朝上的次数，如果正面朝上则数值为1，反之则为0

那麽在抛掷一次硬币时，正面朝上的期望次数就是指示器变数的期望值:

因此在投掷一枚硬币时，正面朝上的期望次数为。

以投篮来说，假设有一个人2分球，命中率为50%，那麽他每一次出手的期望分数就是1分，如果有一个人3分球命中率为33%，那麽他每一次出手期望分数就是接近1分。

因此我们可以推导出，给定样本空间S和S中一个事件A，设，则
这表示指示器随机变数的期望值，其实就是A事件发生的机率。

上面这个关系，可以让我们很方便的转换期望值和机率之间的关系，当我们掷了次硬币，我们可以使用指示器随机变数，用来表示第次投掷出现正面的事件，当我们投掷次，就会出现次正面

当我们得到这样的关系，我们可以用另一种方式计算出出现正面次数的期望值

正常使用期望值的定义进行计算:

相比直接使用期望值的定义进行计算，指示器随机变数将所求的随机变数分解成许多单一事件，接着对每一个事件求期望值，这一步较为简单，皆个合并这一些结果求出答案。

使用指示器随机变数分析雇用问题

假设面试者以随机顺序的方式出现，令为一个随机变数，表示我们雇用新的办公助理的次数。

我们可以使用指示器随机变数来简化

令为第个面试者会被雇用，发生该事件的指示器随机变数

以及，表示第1个面试者被雇用，发生该事件的指示器随机变数。

假设面试者被录用，表示他比到号面试者都要来的优秀，假设第1号面试者来面试，前面没人比他优秀，因此他必定录取，，第2个面试者如果被录用的条件为他比第1号面试者来得优秀，由於顺序是随机的，因此他被录用的期望值为1/2，以此类推。

计算

得到我们面试了个人，但平均起来，我们只会雇用他们之中个人。

因此，假设面试者以随机的方式出现，整个HIRE-ASSISTANT所需要花费的费用为

指示器随机变数练习

有n位客人，他们每一个人给餐厅负责保管帽子的服务生一顶帽子。服务生会以随机的方式将帽子归还给顾客，请问拿到自己帽子的顾客期望数量是多少?

令为第i个客人拿到自己的帽子，发生该事件的指示器随机变数为

对於每一个顾客，拿到自己帽子的期望值为

计算

随机演算法

在许多时候，我们不知道输入的分布情况，我们无法确定每一种输入的排列情况是否都会是机率均等的出现，也因此我们在这种情况无法使用平均情况进行分析。

对於雇用问题，我们在雇用问题的函式中加入了随机数产生器，可以让我们产生出随机的排列，而这个随机性就不是依赖於我们的输入，也就是我们不是假定输入是随机的，而是我们对输入做一些随机化的操作，让他变成均匀分布的。在演算法执行前，先随机排列输入，也就是面试者，让所有排列情况都会是机率均等的。在这个情况下，我们大约会雇用个新的办公助理。

依靠随机数产生器，那麽最差的情况即为随机数产生器产生出第1号是最差的面试者，第n号是最好的面试者，最差情况由随机数产生器而产生，并不依靠输入。

将HIRE-ASSISTANT随机化，只要改变面试者的顺序即可

RANDOMIZED-HIRE-ASSISTANT(N)
randomly permute the list of candidates
best = 0 // 第0号候选人(最差的)
for i = 1 to n
    interview candidate i
    if candidate i is better that candidate best
        best = i
        hire candidate i

这里可以得出一个结论，随机演算法RANDOMIZED-HIRE-ASSISTANT的雇用花费的期望值为

而这个结论，可以不用使用面试者顺序必须随机的这个前提。

随机排列阵列

上面我们使用的随机化方式是改变输入阵列中元素的排列顺序，这里会探讨两种随机化的方式，我们目标是给定一个阵列A，包含元素1到n，我们要产生出随机排列的A阵列。

PERMUTE-BY-SORTING

将每一个元素给予一个随机的优先级，然後根据这个优先级对阵列中的元素进行排叙。

例如: 如果有一个阵列，随机产生出的优先级，就会产生出新的阵列，因为2的优先级最小，3的优先级最大。这个随机化的过程称为PERMUTE-BY-SORTING。

PERMUTE-BY-SORTING(A)
n = A.length
let P[1...n] be a new array
for i = 1 to n
    P[i] = RANDOM(1, n^3)
sort A, using P as sort keys

C++实作

#include <iostream>
#include <vector>
#include <ctime>

using namespace std;
void random_array(vector<int> &);
void sort_array(vector<int> &, vector<int> &);
int main(void)
{
    srand(time(NULL));
    vector<int> a = {1, 2, 3, 4, 5};
    random_array(a);
    for (auto i : a)
    {
        cout << i << ' ';
    }
}

void random_array(vector<int> &a)
{
    int n = a.size();
    vector<int> p;
    for (int i = 1; i < n; i++)
    {
        p.push_back(rand() % n ^ 3 + 1);
    }
    sort_array(a, p);
}

void sort_array(vector<int> &a, vector<int> &p)//insertion sort
{
    for (int i = 0; i < a.size(); i++)
    {
        int key = p[i];
        int key1 = a[i];
        int j = i - 1;
        while (j >= 0 && p[j] > key)
        {
            p[j + 1] = p[j];
            a[j + 1] = a[j];
            j--;
        }
        p[j + 1] = key;
        a[j + 1] = key1;
    }
}

RANDOMIZE-IN-PLACE(A)

给定一个阵列，含元素1到n，我们要做的就是在每一次迭代，让和每一个随机选取阵列内的元素进行交换，RANDOMIZE-IN-PLACE可以在的时间内完成。

RANDOMIZE-IN-PLACE(A)
n = A.length
for i = 1 to n
    swap A[i] with A[RANDOM(i, n)]

C++实作如下

#include <iostream>
#include <vector>
#include <ctime>

using namespace std;
int main(void)
{
    srand(time(NULL));
    vector<int> a = {1, 2, 3, 4, 5};
    for (int i = 0; i < a.size(); i++)
    {
        swap(a[i], a[rand() % a.size()]);
    }
    for (auto i : a)
    {
        cout << i << ' ';
    }
}

参考资料:Introduction to algorithms 3rd