Microsoft PowerPoint - Lecture4_2.ppt

Size: px

Start display at page:

Download "Microsoft PowerPoint - Lecture4_2.ppt"

载糟赐庞
7 years ago
Views:

1 組合數學 ( 組合數學與機率 ) Lecture 4

2 計數 (Counting) Q1: n 個命題字母的真值表中有多少列? Q2: 一個擁有 n 個元素的集合有多少個子集合?

3 Sum and Product Rules Let m be the number of ways to do task 1 and n the number of ways to do task 2 (with each number independent of how the other task is done), and assume that no way to do task 1 simultaneously also accomplishes task 2. The sum rule: The task do either task 1 or task 2, but not both can be done in m+n ways. The product rule: The task do both task 1 and task 2 can be done in mn ways.

4 相乘原理 (Production Rule) 汽車牌照前兩位是大寫英文字母, 後四位是阿拉伯數字所組成, 那麼汽車監理所可發出個汽車牌照

5 Example 設 A = m, B = n, 試問 (1) 從 A 到 B 可定義多少個函數? (2) 從 A 到 B 可定義多少個 1-1 函數? n m P(n,m)=n(n-1)(n-2) (n-m+1)

6 Example

7 決策樹 (Decision Tree) 小明連丟五次銅板其中沒有連續出現兩次正面的結果有幾個? 13

8 Example 畫出由 X Y Z 所組成長度為 3 的字串之決策樹, 其中 Y 後面不可以跟著 Z

9 Example 21

11 容斥原理 (Principle of Inclusion- Exclusion) 1. 2.

12 Example 理學院統計選修數學, 物理, 化學三科的人數, 結果分別為 170, 130,120 人同時修數學和物理的有 45 人, 同時修數學和化學的有 20 人, 同時修物理和化學的有 22 人同時修三門課的有 3 人, 問這三門課中至少有修一門的學生有多少人?

14 一一對應 (One to One Correspondence 某城市的街道把此城市分割成一塊塊的矩形方塊, 某人從家裡 (0, 0) 出發去公司上班, 向東走過 m 塊, 向北走過 n 塊, 問此人上班的路徑有多少種?

15 依據加法法則知, 從 O 到 A 的路徑數 = 從 O 到 B 的路徑數 + 從 O 到 C 的路徑數

16 坑洞原理 (Pigeonhole Principle) 一個蘿蔔一個坑 1.

17 Example

18 坑洞原理很自然地可以延伸成 : 如果有 r 根蘿蔔放入 r 個坑洞裡, 那麼一個坑洞放一根蘿蔔若且唯若每一個坑洞都有放蘿蔔 (1-to-1 & onto function)

19 排列與組合

20 排列 (Permutation) 從 n 個不同物件中挑出 r 個不同物件做順序排列, 所可能產生的情況數目表示為 P(n,r) 一般來說,P(n,r) 可以表示成下列的公式 n P n r! (, ), r n ( n r )! 0

21 P(n,r) n! n! P( n,0) 1 ( n 0)! n! 這個結果可以解釋成 0 個物件的有序排列方式只有一種 - 空集合 n! P( n,1) n ( n 1)! 這個公式反映了事實 - 從 n 個物件中選出一個物件做排列有 n 種排列方式 n! P( n, n) n! ( n n )! 這個結果說明從 n 個物件中選出 n 個物件做排列有 n! 種排列方式

22 A, B, C, D, E 五人排成一列, 那麼 (1) A 不在頭且 B 不在尾, 有多少種排法?(2) A 在 B 的前面, 有多少種排法?(3) A 在 B 的前面且 A 與 B 相鄰, 有多少種排法?(4) C 在 A 與 B 之間有多少種排法? xxxxx

23 組合 (Combination) 從 n 個不同物件中挑出 r 個不同物件的組合數, 符號表示為 C(n,r) 從 n 個不同物件中挑出 r 個不同物件做排列的可能排列數等於選出這 r 個物件的方法,C(n,r), 乘以這 r 個物件的可能排列數目,r! 因此或者 C(n,r) r!=p(n,r) P( n, r) n! C( n, r), 0 r! r!( n r )! r n 相當於考慮順序

25 C(n,r) n! n! C( n,0) 1 0!( n 0)! n! 這個結果可以解釋成從 n 個物件選取 0 個物件的方式只有一種 - 選擇空集合

26 C(n,r) C( n,1) n! 1!( n 1)! n 這個公式反映了事實 - 從 n 個物件中選出一個物件有 n 種方式 n! C( n, n) 1 n!( n n )! 這個結果說明從 n 個物件中選出 n 個物件只有 1 種選法 - 全部都選

27 有 n 本不同的書要分給 r 個人, 他們各得 k 1, k 2,, k r 本 k 1 + k k r = n, 有多少種不同的分法?

29 消除重複計算項一般的情況是, 如果我們有 n 個物件, 其中有 n 1 個物件是同屬一類的 ( 一樣的或無法分辨的 ) 另外又有 n 2 個物件是同屬另一類的 ( 一樣的或無法分辨的 ) 以此類推乃至於有 n k 個物件是同屬另一類的 ( 一樣的或無法分辨的 ) 那麼這 n 個物件的不同排列數有 n! ( n!)( n!) ( n!) 1 2 k

30 範例

31 二項式定理 (Binomial Theorem)

32 從 n 個數中取 r 個的組合數 C(n,r) 又稱為二項式係數 x k y n k 項係數就等於從 n 個括號中取 k 個的組合數 C(n,k)

33 帕斯卡三角形

34 帕斯卡三角形將實際上的數字算出來, 我們發現帕斯卡三角形的樣子變成 :

36 帕斯卡三角形帕斯卡公式 C( n, k) C ( n 1, k 1) C ( n 1, k) 1 k n 1 or

38 二項式定理

39 二項式定理 (a+b) n 的展開係數是帕斯卡三角形的第 n 列

40 證明

42 範例

43 範例

44 組合等式 (Binomial Identities)

49 機率 (Probability) Pascal: 二項式係數 Laplace: 機率定義古典機率 :

50 隨機試驗所有可能的出象所構成的集合稱為隨機試驗的樣本空間 (sample space), 以符號 S 表之其中每一個可能的出象稱為樣本點 (sample point) 一個事件 (event) 就是樣本空間的一個子集合

51 將一枚公正的硬幣投擲兩次, 觀察正反面出現的情形, 這個試驗的樣本空間 S = {( 正, 正 ), ( 正, 反 ), ( 反, 正 ), ( 反, 反 )} 兩次都出現正面的機率為 1/4 至少出現一次正面的機率為 3/4

53 樂透彩 (Lottery) 玩家從 1~49 這 49 個數字中簽選 6 個數字, 若全選中, 便可得巨額頭獎彩金, 試問得頭彩的機率是多少? C(49,6)

54 P i 1 i 1 P( E ) i 機率公設設隨機試驗所對應的樣本空間為 S, 對於每一個事件 E, 其對應的實數, 稱為事件 E 發生的機率 (probability), 以 P(E) 表之這些機率值必須滿足下列三個公設 : (1)P (S) = 1 (2)0 P (E) 1 (3) 若 E 1, E 2, 為一序列的事件, 且當 i j 時,E 1 E j = ( 即 E i 與 E j 為互斥事件 ), 則 P P PP( E( E) i ) i i 1 i 1 i 1 i 1

55 若 E F, 則 P (E) P (F) P (E F) = P (E) + P (F) P (E F)

56 P( )=0 (since P (S) = 1, S and are mutually exclusive )

57 若有任意事件 E 1, E 2,, E n, 則 n n P Ei P( Ei ) i 1 i 1

58 條件機率 (Conditional Probability) P( A B) P( A B) P( B)

59 獨立事件 (Independence Event)

60 已知樣本空間 S 中事件 S 1, S 2,, S k 互相獨立, 則事件 A 的機率可寫成

62 分割 (Partition) 樣本空間 S 中事件 S 1, S 2,, S k 若滿足下面三個條件 (a) 當 i j 時,S i S j = (b) k i 1 E i S (c) P (S i ) > 0, i = 1,, k 則稱 S 1, S 2,, S k 為樣本空間 S 的一個分割 (partition)

63 S 1 S k A S 2 S 3

64 全機率定理 (total probability) 設 B 為 S 中事件, 則 B 可寫成 B B E 1 B E 2 B E k 其中,(B E 1 ),, (B E k ) 均為互斥因此 ( ) ( ) ( ) P B P B E 1 P B E 2 P B E k ( ) ( ) ( ) ( ) 再利用乘法法則, 可得 P( B) P ( B E ) P( E ) P ( B E ) P( E ) P ( B E ) P( E ) k k

65 貝式定理 (Baye s theorem) 若 E 1, E 2,, E k 為 S 的一個分割, 而且 E 1, E 2,, E k 的機率以及條件機率 P (B E 1 ),, P (B E k ) 皆為已知, 則可利用條件機率的定義及全機率定理, 得到 P( B E i ) P( Ei B) P( B) i k i 1 P( B E ) P( E ) P( B E ) P( E ) 1,, k i i i i

66 假若把事件 E i 視為試驗者在試驗前對於某一情況的可能假設, 則 P (E i ) 即代表此假定成立的機率這些機率值經常是由試驗者依據自己的經驗而認定的, 因此稱為事前機率 (prior probability) 現在試驗者根據試驗的結果事件 B 的發生來修正試驗前所做關於假定成立的機率這些修正過的機率稱為事後機率 (posterior probability)

67 某公司的產品是由甲乙丙三場製造已知甲乙丙三廠製造量為 50%, 25% 與 25% 而甲乙丙三廠製造之不良品各占 2%, 2% 與 4% 若三廠產品皆存放在同一倉庫內, 現隨機從倉庫內隨機抽取一件產品, 請問 (a) 其為不良品的機率為何? (b) 該不良品來自甲廠的機率為何?

68 某廠商檢驗某種產品, 已知其為良品而被檢驗為不良品的機率為 0.1, 其為不良品而被檢驗為良品的機率為 0.05 若該批產品中, 不良品佔 10%, 良品佔 90%, 今抽出一件產品檢驗之, 試求 (a) 被檢驗為良品之機率? (b) 被檢驗為錯誤之機率?

69 伯努利試驗 (Bernoulli Trials) 若一個試驗的可能結果只有兩個, 這種試驗就稱為伯努利試驗例如, 投擲一枚硬幣或射擊命中目標的試驗將伯努利試驗獨立地重複 n 次的隨機試驗稱為 n 重伯努利試驗

73 二項式分布在 n 次試驗中恰好有 k 次成功的機率為若令 q =1 p, 則這個數字恰好是二項式展開 ( p + q)n 中的第 k 項!

74 隨機變數的定義設 S 為隨機試驗的樣本空間對於每一個樣本點 s S 皆對應一個實數 X(s) 的函數 X, 稱為隨機變數所有隨機變數 X 可能對應的數值的集合, 稱為值域 (range space) 以符號 R x 表示

75 P(x) 特性機率函數 p(x) 具有下列特性 (1) 對於所有的實數 x,0 p (x) (2) i 1 p( x ) 1 i

76 期望值 (Expected Values) 設 X 為一離散隨機變數, 其可能值為 x 1, x 2,, 則稱為 X 的期望值 (expectation, expected value) 或平均數 (mean)

77 性質設 X 為隨機變數,a b 為實數, 則 (1) E (ax + b) = ae (X) + b (2) E (g (X) + h (X)) = E (g (X)) + E (h (X)) 設隨機變數 X 的期望值為, 則 2 2 x E [( X ) ] 稱為 X 的變異數變異數也可用 2, V(X) 表示

78 二項式分布設 X 為隨機變數,a b 為實數, 則 (1)V (X + b) = V (X) (2)V (ax) = a 2 V (X) (3)V (vx + b) = a 2 V (X)

79 已知隨機變數 X 的期望值為, 變異數 2 定義 E( Z) 0, V ( Z) 1 則由定理 5-4 (3), 可得 X Z 我們稱 Z 為標準化隨機變數 (standardized random variable)

80 常用離散機率分布伯努利試驗與二項分布許多隨機試驗只有兩種可能的出象, 我們稱它為伯努利試驗 (Bernoulli trial) 若伯努利試驗的出象以隨機變數 X 表之, 可令 X = 1 表示出象為成功,X = 0 表示出象為失敗, 則 X 的機率函數為 f x p p x x 1 x ( ) (1 ), 0 1 其中 0 p 1, 代表試驗成功的機率

81 設 X 為伯努利隨機變數, 則 (1)E (X) = p (2)V (X) = p (1 p) 設 X 為二項隨機變數, 則 (1)E (X) = np (2)V (X) = np (1 p)

82 超幾何分布 (Hypergeometric Distribution) 假設母體含有 N 個元素, 其中 S 個為成功,N S 個為失敗今自母體中隨意選取 n 個出來若隨機變數 X 代表 n 個中是成功的個數, 則 X 稱為超幾何隨機變數 (hypergeometric random variab), S N S k n k P( X k ), k 0,1,,min( n, s) N n

83 設 X 為超幾何隨機變數, 則 S E( X ) n (1) N S E( X ) n N V ( X ) N n n S 1 S (2) N 1 N N V ( X ) N n n S 1 S N 1 N N

84 幾何隨機分布 (geometric random distribution) 在一連串的伯努利試驗中, 我們常關心須等待多久才發生第一次成功因此設 X 為出現第一次成功的試驗次數, 其機率函數為 P X k p p k k 1 ( ) (1 ), 1,2, 3, 0 其他

85 設隨機變數 X 呈幾何分布, 則 1 E( X ) (1) p 1 E( X ) p q V ( X ), q 1 p 2 (2) p q V ( X ), q 1 p 2 p

86 波瓦松分布 (Possion Distribution) 波瓦松隨機變數所討論的機遇現象須滿足下列假定在不重疊的時間 ( 或空間 ) 內, 現象發生的次數相互獨立當考慮的時間段落很小時, 則現象發生一次的機率與該時間段落的長短成正比但與時間段落的位置無關當時間段落很小時, 現象發生兩次以上的機率近似於 0

87 若設 X 為單位時間 ( 或空間 ) 內某現象出現的次數則可證明 X 的機率函數為 k e P( X k ), k 0,1,2, k! 稱參數為的波瓦松分布, 其中表示單位時間或空間內該現象平均發生的次數

88 設 X 為參數的波瓦松隨機變數, 則 (1) E (X) = (2)V (X) =

89 負二項隨機分布 (negative binomial Distribution) 設獨立試驗, 每次成功的機率是 p,0 < p < 1, 試驗執行直到累計 r 次成功才停止, 若 X 表示所需試驗的次數, n 1 r n r P( X n ) p (1 p ), n r, r 1, r 1 而幾何隨機變數正好是負二項隨機變數的一個特例, 其參數為 (1, p)

90 負二項分布基本性質 E( X ) r p r(1 p ) V ( X ) 2 p

91 5-6 連續機率分布若隨機變數 X 的機率密度函數為則稱 X 為在區間 [a, b] 的均勻分布 (uniform distri-bution) 並以符號 U [a, b] 表之

92 連續機率分布常態隨機變數的機率密度函數為 X f ( x) exp X 2 2, 其中均為參數通常以 N (, 2 ) 表示常態分布

93 f (x) f (x) x x

94 f (x) 的曲線圖形具有下列特性 (1) 呈鐘形分布, 且對稱於 X = (2) 在 X = 處有兩個反曲點 (point of inflection) (3) 當 X 時,f (x) 0 (4) 值大時, 曲線低平值小者, 曲線高狹

95 若 X 的分布為 N (, 2 ), 隨機變數 Y = ax + b, 則 Y 的分布為 N (a + b, a 2 2 )

96 中央極限定理 (Central Limit Theorem) 若從平均數, 變異數 2 的一個無限或大母體中, 抽出大小為 n 的隨機樣本則樣本平均數的抽樣分布將趨近於平均數, X 標準差的常態分布 X 為標準常態變數 Z 的一個值 Z n X n

97 THE END

Microsoft Word - Probability.doc

Microsoft Word - Probability.doc 十一機率 (Probability).... 分立變值 (discrete variate) 及連續變值 (continuous variate)..... 連續變質 (Continuous variate)/ 連續變數 (Continuous variable)..... 分立變值 (Discrete variate)/ 間斷變數 (Discrete variable)....