Bài giảng Khoa học Máy tính - 2. Nhắc lại kiến thức về xác suất thống kê

1 Bài giảng 2 – Nhắc lại kiến thức về xác suất thống kê Nguyễn Phương Thái BM Khoa học Máy tính 2 Nội dung bài giảng - Không gian xác suất - Xác suất có điều kiện và sự độc lập xác suất - Định luật Bayes - Biến ngẫu nhiên - Kỳ vọng và phương sai - Phân phối có điều kiện và phân phối phụ thuộc - Ước lượng xác suất - Các phân phối chuẩn 3 Không gian xác suất - Lý thuyết xác suất có nhiệm vụ dự đoán cái gì đó sẽ xảy ra với khả năng như thế nào Ví dụ: gieo 3 đồng xu, khả năng xuất hiện cả ba mặt ngửa là thế nào? - Phép thử: là một thí nghiệm hay quan sát nào đó - Biến cố sơ cấp: kết quả đơn giản nhất của thí nghiệm - Không gian mẫu: tập tất cả các biến cố sơ cấp - Biến cố: tập con của không gian mẫu 4 Một số ví dụ Gieo một đồng tiền xu một lần. Không gian các biến cố sơ cấp (không gian mẫu) là Ω = {S, N} Gieo một đồng tiền xu hai lần. Không gian mẫu là: Ω = {SS, SN, NS, NN} Một đồng tiền được gieo liên tiếp cho tới khi lần đầu tiên xuất hiện mặt sấp thì dừng lại. Không gian mẫu có dạng: Ω = {S, NS, ..., NNS, } 5 Không gian xác suất (tiếp) - Số biến cố là 2n (giả sử số phần tử của Ω là n) - Ω được gọi là biến cố chắc chắn, ᴓ được gọi là biến cố không - Biến cố ܣ ∪ ܤ = {ݓ: ݓ ∈ ܣ hoặc ݓ ∈ ܤ} được gọi là hợp của A và B - Biến cố ܣ ∩ ܤ = {ݓ: ݓ ∈ ܣ và ݓ ∈ ܤ} được gọi là giao của A và B. Biến cố này còn được ký hiệu là AB - Biến cố ܣ\ܤ = {ݓ: ݓ ∈ ܣ và ݓ ∉ ܤ} được gọi là hiệu của A và B - Biến cố ̅ܣ = {ݓ: ݓ ∉ ܣ } được gọi là biến cố đối của A 6 Không gian xác suất (tiếp) Theo ngôn ngữ xác suất, các điều trên có nghĩa là: - ܣ ∪ ܤ xảy ra  hoặc A hoặc B xảy ra - ܣ ∩ ܤ xảy ra  cả A và B cùng xảy ra - ܣ\ܤ xảy ra  A xảy ra và B không xảy ra - ̅ܣ xảy ra  A không xảy ra 7 Không gian xác suất (tiếp) Ví dụ: Gieo một đồng tiền xu hai lần. Không gian mẫu là: Ω = {SS, SN, NS, NN}. Xét: A = {SS, SN, NS} (có ít nhất một lần xuất hiện mặt sấp) B = {NS, SN, NN} (có ít nhất một lần xuất hiện mặt ngửa) Ta có: ܣ ∪ ܤ = Ω AB = {SN, NS} (có đúng một lần xuất hiện mặt sấp) ̅ܣ = {ܰܰ} A\B = {SS} 8 Xác suất của biến cố Giả sử A là biến cố của phép thử nào đó: - P(A), tồn tại khách quan, đo khả năng xuất hiện của A Số này bằng 1 nếu A là biến cố chắc chắn, bằng 0 nếu A là biến cố không, nếu A, B là hai biến cố xung khắc thì ܲ(ܣ ∪ ܤ) = ܲ(ܣ) + ܲ(ܤ) - Giả sử Ω = {ݓଵ, ݓଶ, , ݓ௞ , }, mỗi biến cố sơ cấp được gắn với một “trọng số” ݌௞ = ݌௞(ݓ௞) sao cho: ݌௞ ≥ 0 với mọi ݇ ≥ 1 ෍ ݌௞ ௞ = 1 - Khi đó: ܲ(ܣ) = ෍ ݌௞ {௞:௪ೖ∈஺} 9 Định nghĩa cổ điển của xác suất Giả sử Ω = {w1, , wN} là không gian mẫu mà các kết quả có cùng khả năng xuất hiện, nghĩa là: P(wi) = 1/N với mọi i. Khi đó theo công thức ở slide trên, xác suất của biến cố A là: ܲ(ܣ) = |ܣ| |Ω| = ݊ ܰ Định nghĩa này cho ta một mô hình toán rất tốt với các hiện tượng ngẫu nhiên liên quan đến phép thử có tính đối xứng và đo đó các kết quả của nó được coi là có cùng khả năng xuất hiện. 10 Một số tính chất của xác suất ܲ(ᴓ) = 0, ܲ(Ω) = 1, 0 ≤ ܲ(ܣ) ≤ 1 ܲ(ܣ ∪ ܤ) = ܲ(ܣ) + ܲ(ܤ) − ܲ(ܣܤ) Nếu A và B là các biến cố xung khắc thì ܲ(ܣ ∪ ܤ) = ܲ(ܣ) + ܲ(ܤ) ܲ(̅ܣ) = 1 − ܲ(ܣ) 11 Ví dụ Một cái hộp N quả cầu được đánh số bởi các số của tập hợp các số tự nhiên từ 1 đến N. Rút lần lượt từng quả n lần, sao cho mỗi lần rút một quả, quả đó được hoàn trả lại hộp rồi mới rút lần tiếp theo. Hãy tính xác suất của biến cố: A = {các quả đã được rút là đôi một khác nhau} Không gian mẫu: Ω = {w = (a1, , an): 1 ≤ ܽ௜ ≤ ܰ} với |Ω| = ܰ௡ |ܣ| = ܣே ௡ = ܰ(ܰ − 1) (ܰ − ݊ + 1) Do đó: ܲ(ܣ) = |஺| |ஐ| = ே(ேିଵ)(ேି௡ାଵ) ே೙ 12 Xác suất có điều kiện Xác suất có điều kiện của biến cố A với điều kiện B là một số xác định theo công thức: ܲ(ܣ|ܤ) = ܲ(ܣܤ) ܲ(ܤ) nếu P(B)>0 Công thức nhân xác suất: ܲ(ܣܤ) = ܲ(ܤ)ܲ(ܣ|ܤ) = ܲ(ܣ)ܲ(ܤ|ܣ) nếu P(A)P(B)≠0 Bằng qui nạp, bạn dễ dàng suy ra công thức nhân tổng quát. 13 Một số ví dụ Ví dụ 1: Gieo một con xúc xắc cân đối và đồng chất hai lần. A là biến cố “lần đầu gieo xuất hiện mặt 1 chấm”, B là biến cố “tổng số chấm trong hai lần gieo không vượt quá 3”. Tính P(A|B). Ta thấy Ω = {(݅, ݆): 1 ≤ ݅, ݆ ≤ 6} A = {(1, 1), ,(1, 6)}, B = {(1, 1), (1, 2), (2, 1)} P(A) = 6/36; P(B) = 3/36; P(AB) = 2/36 Nếu biết rằng B đã xảy ra thì A xảy ra khi một trong hai kết quả (1, 1) và (1, 2) xảy ra. Do đó: ܲ(ܣ|ܤ) = 2 3 = 2 36 3 36 14 Một số ví dụ (tiếp) Ví dụ 2: Từ một hộp chứa a quả cầu trắng và b quả cầu đen, người ta rút ngẫu nhiên không hoàn lại từng quả một hai lần. Tính xác suất để lần thứ hai mới rút được quả cầu trắng. Ký hiệu Ak là biến cố “lần thứ k rút được quả trắng”, k = 1, 2, Theo công thức nhân xác suất ta có xác suất cần tìm là: ܲ(̅ܣଵܣଶ) = ܲ(̅ܣଵ)ܲ(ܣଶ|̅ܣଵ) = ܾ ܽ + ܾ × ܽ ܽ + ܾ − 1 15 Công thức Bayes ܲ(ܤ|ܣ) = ܲ(ܤܣ) ܲ(ܣ) = ܲ(ܣ|ܤ)ܲ(ܤ) ܲ(ܣ) Giả sử ܲ(ܣ) > 0 và {B1, B2, , Bn} là hệ đầy đủ các biến cố với ܲ(ܤ௜) > 0 với mọi i. Khi đó ta có: ܲ(ܤ௞|ܣ) = ܲ(ܤ௞)ܲ(ܣ|ܤ௞) ܲ(ܣ) = ܲ(ܤ௞)ܲ(ܣ|ܤ௞) ∑ ܲ(ܤ௜)ܲ(ܣ|ܤ௜) ௡ ௜ୀଵ Ví dụ: Từ một hộp chứa a quả cầu trắng và b quả cầu đen, người ta rút ngẫu nhiên không hoàn lại từng quả một hai lần. Hãy tính xác suất để lần đầu rút được quả trắng biết rằng lần thứ hai cũng rút được quả trắng. 16 Công thức Bayes (tiếp) Ký hiệu Ak là biến cố “lần thứ k rút được quả trắng”, k = 1, 2, Theo đề bài ta cần tính P(A1|A2). Theo công thức Bayes ta có: ܲ(ܣଵ|ܣଶ) = ܲ(ܣଵ)ܲ(ܣଶ|ܣଵ) ܲ(ܣଶ) = ܽ(ܽ − 1) ܽ(ܽ − 1) + ܾܽ 17 Sự độc lập của hai biến cố Hai biến cố A và B được gọi là độc lập nếu ܲ(ܣܤ) = ܲ(ܣ)ܲ(ܤ) Nếu ܲ(ܤ) > 0 thì dễ thấy A và B độc lập khi và chỉ khi ܲ(ܣ|ܤ) = ܲ(ܣ) 18 Biến ngẫu nhiên - Biến ngẫu nhiên là hàm ܺ: Ω → ܴ௡ (thường n=1) - Hàm mật độ xác suất (pmf): p(x) = p(X=x) = P(Ax) trong đó ܣ = {ݓ ∈ Ω: ܺ(ݓ) = ݔ} - Với biến ngẫu nhiên rời rạc ta có: ∑ ݌(ݔ௜)௜ = ∑ ܲ൫ܣ௫೔൯௜ = ܲ(Ω) = 1 19 Kỳ vọng và phương sai Kỳ vọng là giá trị trung bình của biến ngẫu nhiên. Giả sử X là biến ngẫu nhiên với pmf là p(x) mà ∑ |ݔ|݌(ݔ)௫ < ∞ thì kỳ vọng là: ܧ(ܺ) = ෍ ݔ݌(ݔ) ௫ Phương sai của biến ngẫu nhiên là một số không âm dùng để đo mức độ phân tán (tản mát) của các giá trị của biến ngẫu nhiên xung quanh giá trị trung bình của nó. ܸܽݎ(ܺ) = ܧ ቀ൫ܺ − ܧ(ܺ)൯ ଶ ቁ = ܧ(ܺଶ − ܧଶ(ܺ)) 20 Ví dụ Gieo một con xúc xắc và giả sử Y là giá trị thu được, khi đó: ܧ(ܻ) = ෍ ݕ݌(ݕ) ଺ ௜ୀଵ = 1 6 ෍ ݕ ଺ ௜ୀଵ = 21 6 = 3 1 2 ܸܽݎ(ܻ) = ܧ(ܻଶ) − ܧଶ(ܻ) = 91 6 − 49 4 = 35 12 Chú ý: Khi tính E(Y2) cần dùng ∑ ݅ଶ௡௜ୀଵ = ௡(௡ାଵ)(ଶ௡ାଵ) ଺ 21 Phân phối có điều kiện và phân phối phụ thuộc Hàm pmf phụ thuộc cho hai biến ngẫu nhiên rời rạc X, Y là: p(x, y) = P(X = x, Y = y) Hàm pmf điều kiện : ݌௑|௒(ݔ|ݕ) = ݌(ݔ, ݕ) ݌௒(ݕ) với y mà ݌௒(ݕ) > 0 Công thức nhân xác suất : p(w, x, y, z) = p(w)p(x|w)p(y|w,x)p(z|w,x,y) 22 Phân phối nhị thức - Tạo bởi dãy phép thử với chỉ hai biến cố sơ cấp, các phép thử là độc lập - Ví dụ : gieo đồng xu cân đối và đồng chất - Họ phân phối nhị thức là : ܾ(ݎ; ݊, ݌) = ܥ௡ ௥݌௥(1 − ݌)௡ି௥ Trong đó r là số lần thành công trong n lần thử. - Phân phối nhị thức được dùng nhiều trong nghiên cứu, ví dụ cho các mô hình n-gram, kiểm định giả thuyết thống kê, v.v. - Tổng quát hóa của phân phối nhị thức là phân phối đa thức 23 Phân phối nhị thức (tiếp) Hai đường cong b(r; 10, 0.7) và b(r; 10, 0.1) 24 Phân phối chuẩn - Đây là một hàm phân phối liên tục có dạng : ݊(ݔ; ߤ, ߪ) = 1 √2ߨߪ ݁ି(௫ିఓ) మ/(ଶఙమ) Trong đó ߤ là giá trị trung bình và ߪ là độ lệch chuẩn - Các ứng dụng : mô hình hóa chiều cao hay chỉ số IQ của người, các mô hình học máy, thống kê, v.v. - Tên khác: Gaussians 25 Phân phối chuẩn (tiếp) Hai đường cong n(x; 0, 1) và n(x; 1.5, 2) Chú ý: trong thống kê, nhiều khi phân phối nhị thức (rời rạc) được xấp xỉ bằng phân phối chuẩn (liên tục) – bạn hãy để ý sự tương tự của các đường cong trong hai hình ví dụ.