Introduction to Probability Theory ‧1‧ - Preliminaries for Randomized Algorithms Speaker: Chuang-Chieh Lin Advisor: Professor Maw-Shang Chang National Chung Cheng University Dept. CSIE, Computation Theory Laboratory January 4, 2006

Computation Theory Lab., Dept. CSIE, CCU, Taiwan For convenience, we omit the contents of set theory concepts, counting techniques, and the discussion of sample spaces and probability measures. Computation Theory Lab., Dept. CSIE, CCU, Taiwan

Computation Theory Lab., Dept. CSIE, CCU, Taiwan Outline Chapter 1: Probability Some useful theorems and principles Conditional probability Theorem of total probability Bayes’ theorem Independent events Independent trails Computation Theory Lab., Dept. CSIE, CCU, Taiwan

Kolmogorov axioms (柯莫格洛夫公理) 1. For any event A  S, P(A)  0. 2. P(S) = 1. 3. If A1, A2, … are mutually exclusive events, then P(A1A2 …) = P(A1) + P(A2) + … . Computation Theory Lab., Dept. CSIE, CCU, Taiwan

Computation Theory Lab., Dept. CSIE, CCU, Taiwan Useful theorems P() = 0 for any experiment. For any event A  S, P(A) = 1  P(A). If A  S, B  S are any two events, then P(AB) = P(A) + P(B)  P(AB). If A  B, then P(A)  P(B). _ Computation Theory Lab., Dept. CSIE, CCU, Taiwan

Conditional probability In an experiment with sample space S, let B be any event such that P(B) > 0. Then the conditional probability of A occurring, given that B has occurred, is for any A  S. Computation Theory Lab., Dept. CSIE, CCU, Taiwan

Computation Theory Lab., Dept. CSIE, CCU, Taiwan 假設你在超市買牛奶，總共有 40 盒供你選，但其中有 10 盒已腐壞（外表看不出來）。假設你買了兩盒牛奶，兩盒都是好的機率是多少？ 令 A 事件代表你選的第一盒是好的，令 B 事件代表你選的第二盒是好的。 Computation Theory Lab., Dept. CSIE, CCU, Taiwan

Theorem of total probability If A1, A2,…, An is a partition of S, and B is any event, then B A1 A2 A3 A4 A5 A6 A7 Computation Theory Lab., Dept. CSIE, CCU, Taiwan

Computation Theory Lab., Dept. CSIE, CCU, Taiwan From the theorem of total probability, and granted that A1, A2,…, An is a partition of S, we have This result is known as Bayes’ theorem (貝式定理). Computation Theory Lab., Dept. CSIE, CCU, Taiwan

Computation Theory Lab., Dept. CSIE, CCU, Taiwan 假設被選中參加一項刑案審判的陪審團，不論被告有罪或無罪，都有 95% 的機會做出正確判決。另外還假設當地警方執法非常嚴格，在被審判的人當中，有 99% 事實上是有罪的。若已知陪審團判某被告無罪，則該名被告真的是無罪的機率是多少？ 令 A1 代表被告有罪之事件，則 代表他無罪的事件。 再令 B 代表被告獲判無罪的事件。 我們要算的是 P(A2 | B)。 Computation Theory Lab., Dept. CSIE, CCU, Taiwan

Computation Theory Lab., Dept. CSIE, CCU, Taiwan 在審判前，這名被告無罪的機率為 0.01，在他獲判無罪之後，這個值增加到了0.161。 Computation Theory Lab., Dept. CSIE, CCU, Taiwan

Computation Theory Lab., Dept. CSIE, CCU, Taiwan Independent events If A  S and B  S are any two events with nonzero probabilities, A and B are called independent if and only if P(A  B) = P(A)P(B) That is, P(A) = P(A | B) and P(B) = P(B | A). Computation Theory Lab., Dept. CSIE, CCU, Taiwan

Computation Theory Lab., Dept. CSIE, CCU, Taiwan Independent trials An experiment is said to consist of n independent trials if and only if S = T1  T2  …  Tn. For every (x1, x2, …, xn)  S, P({(x1, x2, …, xn)}) = P1({x1})P2({x2}) … Pn({xn}), where Pi({xi}) is the probability of xi  Ti occurring on trial i. Computation Theory Lab., Dept. CSIE, CCU, Taiwan

Computation Theory Lab., Dept. CSIE, CCU, Taiwan 假設力穎在修演算法這門課時，某天老師給了一個隨堂考，有 4 題是非題和 3 題選擇題(每題有 3 個選項)。每一小題只有一個對的答案。因為力穎都不會，因此每一題的答案都用猜的。假設力穎至少得答對六題才算及格。 我們可用七個獨立試驗(independent trials)來描述這個事件。 設 T = {r, w} (i.e., right answer and wrong answer)，則sample space S = T T T T T T T 令 A 事件代表他隨堂考及格。 Computation Theory Lab., Dept. CSIE, CCU, Taiwan

Computation Theory Lab., Dept. CSIE, CCU, Taiwan Pi({r}) = 1/2 if i = 1, 2, 3, 4, else, Pi({r}) = 1/3. 則 P(A) = 所以力穎的狗運要好才行。 Computation Theory Lab., Dept. CSIE, CCU, Taiwan

Computation Theory Lab., Dept. CSIE, CCU, Taiwan 正氣歌 文天祥 天地有正氣 雜然賦流形 下則為河岳 上則為日星 于人曰浩然 沛乎塞蒼冥 皇路當清夷 含和吐明庭 時窮節及現 一一垂丹青 在齊太史簡 在晉董狐筆 在秦張良錐 在漢蘇武節 為巖將軍頭 為稽侍中血 為張睢陽齒 為顏長山舌 或為遼東帽 清操厘冰雪 或為出師表 鬼神泣狀烈 或為度江輯 慷慨吞胡羯 或為擊賊笏 逆豎頭破裂 是氣所旁簿 凜烈萬古存 當其貫日月 生死安足論 地維賴以立 天柱賴以尊 三綱實絲命 道義為之根 嗟余遘陽九 錄也實不力 楚囚纓其冠 傳車送窮北 鼎鑊甘如飴 求之不可得 陰房闃鬼火 春院閟天黑 牛驥同一皁 鸛棲鳳凰食 一朝蒙霧露 分作溝中瘠 如此再寒暑 百沴自辟易 哀哉沮洳場 為我安樂國 豈有他繆巧 陰陽不能賊 顧此耿耿存 仰視浮雲白 悠悠我心悲 蒼天曷有極 哲人日已遠 典型在夙昔 風檐展書讀 古道照顏色 Computation Theory Lab., Dept. CSIE, CCU, Taiwan

Thank you.

Computation Theory Lab., Dept. CSIE, CCU, Taiwan References [L94] H. J. Larson, Introduction to Probability, Addison-Wesley Advanced Series in Statistics, 1994; 機率學的世界, 鄭惟厚譯, 天下文化出版. [MR95] R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge University Press, 1995. [H01] 黃文典教授, 機率導論講義, 成大數學系, 2001. Computation Theory Lab., Dept. CSIE, CCU, Taiwan