Day-16 雇用問題, 指示器隨機變數(indicator random variable), 隨機化演算法

2021 iThome 鐵人賽

DAY 16

自我挑戰組

從0開始啃Introduction of algorithms心得與記錄系列第 16 篇

13th鐵人賽自學筆記 algorithm

吳他，惟手熟爾

2021-09-27 11:00:40

2414 瀏覽

分享至

雇用問題

假設你要雇用新的辦公助理，而你找了一個雇用代理人去幫你推薦應聘的人，雇用代理人每天會給你推薦一個人。接著你會去面試這個人，並決定是否要雇用他。

因為雇用代理人幫你篩選出合適的應聘人，所以我們必須給雇用代理一筆費用。如果該應聘人成功通過了面試，那麼我們就將目前的辦公室助理辭去，並支付給雇用代理人仲介費。

如果日後又出現更好的辦公助理，則會將目前的辦公助理辭去，然後雇用新的，我們希望能夠估計一下這麼做我們需要花費多少錢。

下面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]

我們關心的是我們所需要花費的費用，而非執行的時間，假設面試費用需要 $c_i$ ，雇用需要 $c_h$ 。有 $n$ 個人來面試， $m$ 個人會被雇用，那麼總花費為 $O(c_in+c_hm)$ ，不論我們最終雇用了多少人，我們都需要和 $n$ 個人進行面試，因此，我們專注在分析 $c_hm$ 的部分。

這個場景和在陣列中尋找出最大值和最小值很像，透過遍歷整個陣列，每一次紀錄當前的最大值或是最小值，透過不斷的更新值直到遍歷完整個陣列我們即可得知最大值和最小值。

最壞情況

最壞的情況下，就是來了n位面試者，第1位面試者為最差的面試者，第2位面試者為第2差的面試者，第n位面試者為最好的面試者，這種情況下，雇用的費用為 $O(c_hn)$

在通常情況下，當然不會有這麼剛好的事情發生，而在分析這個問題時，我們必須知道在n位面試者中，每位面試者程度的分布情況，也就是平均分布的情況，我們希望最好的面試者出現在每一個編號的機率是均等的，也就是 $n/1$ 。

機率分析

機率分析，廣泛的使用在分析演算法中，例如在分析演算法執行時間，我們產生出所有可能的輸入來得到演算法的時間，並取平均值，得到的值即為平均情況執行時間。

對於某一些問題，如果他的輸入是可以進行一些規範或是假設的，例如假設所有輸入情況都是可能發生的，且發生機率皆均等，那就可以使用機率分析的方式設計演算法。如果輸入是無法預測的，那麼使用機率分析的方式設計演算法便是不可行的。

在僱用問題中，可以假設每一個面試者都是以隨機的順序出現，這也表示任兩個面試者之間有一定的比較關係，可以讓我們進行比較，比較出誰具有資格，也可以對其進行排名。面試者是依照隨機順序排列，假定有 $n$ 個面試者，那麼可以預期會出現 $n!$ 種排列的方式，且每一種排列方式出現的機率皆均等。

隨機化演算法

有時候我們對於輸入的情況無法去掌握，而我們為了利用機率分析的方式去設計演算法，我們會在演算法中某一個部分進行隨機化，讓機率的平均分布情況不取決於輸入的情況，而是根據隨機數產生器等等。

在僱用問題中，我們假設面試者的順序是隨機的，但我們無法確保這件事情發生，為了使用機率分析的方式設計出演算法，我們改變了HIRE-ASSISTANT(n)，我們假設雇用代理人每天會推薦給我們 $n$ 位面試者，而我們要從 $n$ 位面試者中隨機選出一位來進行面試，而這樣做可以使得面試者的順序更加的隨機。

如果一個演算法不僅僅取決於它的輸入，也取決於隨機數產生器(random-number generator)產生出來的數值，那麼我們可以說這個演算法是隨機的(randomized)。

在分析一個隨機化演算法的執行時間，我們以執行時間的期望值進行衡量，而出來的時間我們稱為期望執行時間。

一般來說，當機率分布是取決於演算法的輸入上，我們會討論的是平均執行時間。而當演算法本身具有隨機選擇，歲是有一些隨機因子，像是亂數產生器等，我們會討論他的期望執行時間。

指示器隨機變數(indicator random variable)

為了分析演算法的情況，這裡引入指示器隨機變數的概念。可以讓機率和期望值之間更方便的進行轉換。給定樣本空間S，事件A，那麼事件A對應到的指示器隨機變數 $I\begin{Bmatrix}A\end{Bmatrix}$ 定義為
$\displaystyle I\begin{Bmatrix}A\end{Bmatrix}=\left\{ 1 \ if\ A\ occurs.\\ 0 \ if\ A \ does\ not \ occur. \right.$

舉一個簡單的例子，我們試著求出硬幣投擲出現正面朝上的期望次數。樣本空間為 $S=\begin{Bmatrix} H, T\end{Bmatrix}$ (樣本空間表示所有事件的集合，以硬幣來說，就有正正,反反,正反,反正)，其中正面和反面皆為 $1/2$ ， $P_r\begin{Bmatrix}H\end{Bmatrix} =P_r\begin{Bmatrix}T\end{Bmatrix}=1/2$ ，接著定義指示器隨機變數 $X_H$ ，對應到發生硬幣正面朝上的事件 $H$ 。這個變數作為計數器，紀錄硬幣正面朝上的次數，如果正面朝上則數值為1，反之則為0
$X_H = I\begin{Bmatrix}H\end{Bmatrix} =\left\{ 1 \ if\ H\ occurs.\\ 0 \ if\ T \ occurs.\ \right.$

那麼在拋擲一次硬幣時，正面朝上的期望次數就是指示器變數 $X_H$ 的期望值:
$\displaystyle E\begin{bmatrix}X_H\end{bmatrix}=E\begin{bmatrix}I\begin{Bmatrix}H\end{Bmatrix}\end{bmatrix}=1*P_r\begin{Bmatrix}H\end{Bmatrix}+0*P_r\begin{Bmatrix}T\end{Bmatrix}\\=1*(1/2)+0*(1/2)=1/2$
因此在投擲一枚硬幣時，正面朝上的期望次數為 $1/2$ 。

以投籃來說，假設有一個人2分球，命中率為50%，那麼他每一次出手的期望分數就是1分，如果有一個人3分球命中率為33%，那麼他每一次出手期望分數就是接近1分。

因此我們可以推導出，給定樣本空間S和S中一個事件A，設 $X_A=I\begin{Bmatrix}A\end{Bmatrix}$ ，則 $E[X_A] = P_r\begin{Bmatrix}A\end{Bmatrix}$
這表示指示器隨機變數的期望值，其實就是A事件發生的機率。

上面這個關係，可以讓我們很方便的轉換期望值和機率之間的關係，當我們擲了 $n$ 次硬幣，我們可以使用指示器隨機變數 $X_i$ ，用來表示第 $i$ 次投擲出現正面的事件，當我們投擲 $n$ 次，就會出現 $X$ 次正面
$\displaystyle X = \sum_{i=1}^nX_i\\ E[X] = E[\sum_{i = 1}^nX_i]$
當我們得到這樣的關係，我們可以用另一種方式計算出出現正面次數的期望值
$\displaystyle E[X] = E[\sum_{i = 1}^nX_i] = \sum_{i=1}^nE[X_i]=\sum_{i=1}^n1/2=n/2$

正常使用期望值的定義進行計算:
$\displaystyle E[X_H] = E[I\begin{Bmatrix}H\end{Bmatrix}]=X*P_r\begin{Bmatrix}H\end{Bmatrix}+(n-X)*P_r \begin{Bmatrix} T \end{Bmatrix} = X * 1/2+n/2-X/2=n/2$

相比直接使用期望值的定義進行計算，指示器隨機變數將所求的隨機變數 $X$ 分解成許多單一事件，接著對每一個事件求期望值，這一步較為簡單，皆個合併這一些結果求出答案。

使用指示器隨機變數分析雇用問題

假設面試者以隨機順序的方式出現，令 $X$ 為一個隨機變數，表示我們雇用新的辦公助理的次數。
$\displaystyle E[X]=\sum_{x=1}^nxP_r \begin{Bmatrix}X = x\end{Bmatrix}$
我們可以使用指示器隨機變數來簡化

令 $X_i$ 為第 $i$ 個面試者會被雇用，發生該事件的指示器隨機變數
$X_H = I\begin{Bmatrix}H\end{Bmatrix} =\left\{ 1 \ if\ candidate\ i\ is\ hired.\\ 0 \ if\ candidate\ i \ is\ not\ hired.\ \right.$

以及 $X = X_1 + X_2 + ... +X_n$ ， $X_1$ 表示第1個面試者被雇用，發生該事件的指示器隨機變數。

假設面試者 $i$ 被錄用，表示他比 $1$ 到 $i - 1$ 號面試者都要來的優秀，假設第1號面試者來面試，前面沒人比他優秀，因此他必定錄取， $E[X_1] = 1$ ，第2個面試者如果被錄用的條件為他比第1號面試者來得優秀，由於順序是隨機的，因此他被錄用的期望值為1/2，以此類推。
$E[X_i] = 1/i$

計算 $E[X]$
$\displaystyle E[X] = E[\sum_{i=1}^nX_i] \\=\sum_{i=1}^n E[X_i] \\=\sum_{i=1}^n1/i \\= lnn+O(1)$
得到我們面試了 $n$ 個人，但平均起來，我們只會雇用他們之中 $lnn$ 個人。

因此，假設面試者以隨機的方式出現，整個HIRE-ASSISTANT所需要花費的費用為 $O(c_hlnn)$

指示器隨機變數練習

有n位客人，他們每一個人給餐廳負責保管帽子的服務生一頂帽子。服務生會以隨機的方式將帽子歸還給顧客，請問拿到自己帽子的顧客期望數量是多少?

令 $X_i$ 為第i個客人拿到自己的帽子，發生該事件的指示器隨機變數為
$\displaystyle X_H = I\begin{Bmatrix}H\end{Bmatrix} =\left\{ 1 \ if\ customer\ i\ get\ his\ own\ hat.\\ 0 \ if\ customer\ i\ doesn't\ get\ his\ own\ hat. \right.$

對於每一個顧客，拿到自己帽子的期望值為 $1/n$
$E[X_i]=1/n$
計算 $E[X]$
$\displaystyle E[X]=E[\sum_{i=1}^nX_i]=\sum_{i=1}^nE[X_i]=\sum_{i=1}^n1/n=1$

隨機演算法

在許多時候，我們不知道輸入的分布情況，我們無法確定每一種輸入的排列情況是否都會是機率均等的出現，也因此我們在這種情況無法使用平均情況進行分析。

對於僱用問題，我們在僱用問題的函式中加入了隨機數產生器，可以讓我們產生出隨機的排列，而這個隨機性就不是依賴於我們的輸入，也就是我們不是假定輸入是隨機的，而是我們對輸入做一些隨機化的操作，讓他變成均勻分布的。在演算法執行前，先隨機排列輸入，也就是面試者，讓所有排列情況都會是機率均等的。在這個情況下，我們大約會雇用 $O(lnn)$ 個新的辦公助理。

依靠隨機數產生器，那麼最差的情況即為隨機數產生器產生出第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的雇用花費的期望值為 $O(c_hlnn)$

而這個結論，可以不用使用面試者順序必須隨機的這個前提。

隨機排列陣列

上面我們使用的隨機化方式是改變輸入陣列中元素的排列順序，這裡會探討兩種隨機化的方式，我們目標是給定一個陣列A，包含元素1到n，我們要產生出隨機排列的A陣列。

PERMUTE-BY-SORTING

將每一個元素 $A[i]$ 給予一個隨機的優先級 $P[i]$ ，然後根據這個優先級對陣列 $A$ 中的元素進行排敘。

例如: 如果有一個陣列 $A = \begin{Bmatrix}1, 2, 3, 4\end{Bmatrix}$ ，隨機產生出的優先級 $P=\begin{Bmatrix}36, 3, 62, 19\end{Bmatrix}$ ，就會產生出新的陣列 $B =\begin{Bmatrix}2 ,4 ,1,3\end{Bmatrix}$ ，因為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)

給定一個陣列 $A$ ，含元素1到n，我們要做的就是在每一次迭代，讓 $A[i]$ 和每一個隨機選取陣列內的元素進行交換，RANDOMIZE-IN-PLACE可以在 $O(n)$ 的時間內完成。

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