[Algo] 5.2 Indicator random variables

Indicator random variables

給定一個 sample space $S$，而 $A$ 是一個 event，那麼 indicator random variable $I\{A\}$ 的定義如下：

$I\{A\} = 1$， if $A$ ocurs
$I\{A\} = 0$， if $A$ does not occur



Lemma 5.1
Given a sample space $S$ and an event $A$ in the sample space $S$, let $X_A = I\{A\}$. Then $E[X_A] = \mbox{Pr}\{A\}\mbox{.} \blacksquare$



candidate i 被 hire 的機率
candidate i 被錄取的話，代表從 candidate 1 到 candidate (i-1)  的 rank 都比 candidate i 還要來的低，所以candidate i 被錄取的機率等於 $1/i$
麻煩一點的算法是這樣：




Expected value of random variable 
$E[X + Y] = E[X] + E[Y]$
這個性質叫做 linearity of expectation，即使 $X$ 和 $Y$ 不是獨立的也是成立的。


Approximation by integrals
When $f(k)$ is a monotonically increasing function, we can approximate it by integrals:
$$\int_{m-1}^{n} f(x)dx \leq \sum_{k=m}^{n} f(k) \leq \int_{m}^{n+1} f(x)dx.$$
When $f(k)$ is a monotonically decreasing function, we can use a similar method:
$$\int_{m}^{n+1} f(x)dx \leq \sum_{k=m}^{n} f(k) \leq \int_{m-1}^{n} f(x)dx.$$


用 indicator random variable 來分析 hiring problem
令 $X$ 為我們 hire 新應徵者次數的 random variable，$X_i$ 是第 i 個應徵者被錄取的 indicator random variable，所以我們知道$X = X_1 + X_2 + \cdots + X_n$。
根據 Lemma 5.1，我們知道
$$E[X_i] = \mbox{Pr}\{\mbox{candidate \textit{i} is hired}\} = \frac{1}{i}$$
$$E[X] = \sum_{i = 1}^{n} E[X_i] = \sum_{i = 1}^{n} 1/i = \ln n + O(1)$$
(根據 Approximation by integrals )
所以結論就是即使面試 $n$ 個應徵者，我們平均只會僱用 $\ln n$ 個人而已，比 worst case $O(n)$好多了。