2010年1月30日 星期六

[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 被錄取的機率等於 $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)$好多了。

[Algo] Exercise 5.1-3

Question

Suppose that you want to output 0 with probability 1/2 and 1 with probability 1/2. At your disposal is a procedure BIASED-RANDOM, that outputs either 0 or 1. It outputs 1 with some probability p and 0 with probability 1 - p, where 0 < p < 1, but you do not know what p is. Give an algorithm that uses BIASED-RANDOM as a subroutine, and returns an unbiased answer, returning 0 with probability 1/2 and 1 with probability 1/2. What is the expected running time of your algorithm as a function of p?


Answer
von Neumann 曾經對這個問題提出解法,主要是利用對稱性。可以參考這份文件
主要的想法是這樣子的:我們擲銅板兩次,銅板丟出{HT}和{TH}的機率都是 $p(1-p)$ ,所以如果我們讓銅板丟出{HT}當作H,而丟出{TH}當作T,如果丟出{HH}或{TT}的話就再重新投擲兩次。這樣子的話我們就可以用這個 biased 的銅板來模擬 unbiased 的銅板。


接下來我們來關心一下期望值的問題:


所以平均我們要丟 $$\frac{1}{p(1 - p)}$$ 次銅板才可以成功的完成一回。


算這個期望值有另外一個較簡單的方法:
只丟兩次就模擬成功的機率是 $e = 2p(1 - p)$ ,而如果不成功的話,就等於丟的那兩次不算再重新丟兩次,假設期望值是丟 $t$ 次的話,那
$$t = e \times 2 + (1 - e) \times (2 + t)$$
$$ \Rightarrow t = 2/e = \frac{1}{p(1 - p)}$$

2010年1月29日 星期五

[Algo] 5.1 The hiring problem

hiring problem
假設你是老闆,而且現在有 n 個應徵者要來應徵工作,你的策略是永遠只錄取到目前為止最好的應徵者,注意的是:hire 一個應徵者的 cost 比 reject 一個應徵者的 cost 還高,也就是說你的演算法如下:

@{
\proc{Hire-Assistant}(n)
\li best = 0
\li \For i = 1 \;\textbf{to}\;n
\li \;\;\;\;\textup{interview candidate}\;i
\li \;\;\;\;\If \;\textup{candidate}\;i\;\textup{is better than candidate}\;\;best
\li \;\;\;\;\;\;\;\;best = i
\li \;\;\;\;\;\;\;\;\textup{hire candidate}\;i
}@
那我們想知道的是平均我們會花多少 cost 在 hire candidate 上面,
想當然爾,worst case 就是 hire 了 n 次。
因為應徵者是以 uniformly random 的方式前來應徵,
所以這個演算法的 running time 或者說 cost 是 depends on input,
這一類的演算法就是 randomized algorithm。


randomized algorithm: its behavior is determined not only by its input but also by vales produced by a random-number generator

[LaTeX] LaTeX on blogger

這個blog裡有提到怎麼在blogger上面用$\LaTeX$貼上數學式,我覺得實在是非常方便。以後可以用這個方法排出漂亮的數學式,而不用忍受用ASCII的方法了。

來測試一下:
inline: $y = x^2$
single line: \[y = x^2\]


inline: $\sum_{i = 1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$
single line: \[\sum_{i = 1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}\]

2010年1月16日 星期六

[Algo] 2.3 Designing algorithms

incremental approach: 像insertion sort這樣子的演算法,過程是A[1...j], A[1...j+1],逐漸完成
divide-and-conquer approach: 把整個問題切成若干個小問題,然後對每個小問題一一擊破,最後再把這些答案整合起來變成原本問題的答案

Merge Sort
Rationale
整個演算法主要是根據divide-and-conquer的方式下去進行。假設A[p...r]是一個我們想要實行sorting的一個序列。先把A[p...r]分成兩個小一點的序列,叫做L: A[p...q]跟R: A[q+1...r],假設我們有能力可以把L和R各自排序好,那把L和R組合起來變成A[p...r]就是一件簡單的事情了。

就好比現在有兩堆大小順序排好的牌堆,點數小的牌在上面,點數大的牌在下面。我們只要比較這兩個牌堆的最上面那張牌,比較小的就把他抽出來,直到某一個牌堆全部都被抽光。這樣就可以很簡單的把這兩副牌堆組合成一個排序好的牌堆。我們就是依據這個道理把L和R兩個序列合成為A[p...r]。

回到我們的前提,就是L和R必須得是排序好的序列。於是這個問題就變成是一個recursive的問題,要把A[p...r]排序好就得先把L和R排序好,排序L就跟排序A其實是同一個問題。所以這個演算法就是把A[p...r]切割成兩個序列A[p...q]和A[q+1...r],A[p...q]和A[q+1...r]也是這樣一直分割下去,分割到最小的單位就是長度為1的序列了。

pseudocode
@{
\proc{Merge-Sort}(A, p, r)
\li \If p < r
\li \;\;\;\;q = \lfloor(p+r)/2\rfloor
\li \;\;\;\;\proc{Merge-Sort}(A, p, q)
\li \;\;\;\;\proc{Merge-Sort}(A, q+1, r)
\li \;\;\;\;\proc{Merge}(A, p, q, r)
}@


@{
\proc{Merge}(A, p, q, r)
\li n_1 = q - p + 1
\li n_2 = r - q
\li \textup{// create arrays}\;L[1..n_1 + 1]\;\textup{and}\;R[1..n_2 + 1]
\li \For i = 1\;\textbf{to}\;n_1
\li \;\;\;\;L[i] = A[p + i - 1]
\li \For j = 1\;\textbf{to}\;n_2
\li \;\;\;\;R[j] = A[q + j]
\li L[n_1 + 1] = \infty
\li R[n_2 + 1] = \infty
\li \For k = p \;\textbf{to}\;r
\li \;\;\;\;\If L[i] \leq R[j]
\li \;\;\;\;\;\;\;\;A[k] = L[i]
\li \;\;\;\;\;\;\;\;i = i + 1
\li \;\;\;\;\Else
\li \;\;\;\;\;\;\;\;A[k] = R[j]
\li \;\;\;\;\;\;\;\;j = j + 1
}@