Bài giảng Mô hình hóa và mô phỏng mạng - Cơ bản về thuyết xác suất - Nguyễn Đức Tài

Nội dung text: Bài giảng Mô hình hóa và mô phỏng mạng - Cơ bản về thuyết xác suất - Nguyễn Đức Tài

1. TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN TPHCM MÔ HÌNH HÓA VÀ MÔ PHỎNG MẠNG CƠ BẢN VỀ THUYẾT XÁC SUẤT TS. Nguyễn Đức Tài
2. XÁC SUẤT (PROBABILITY) Từ xác suất (probability) bắt nguồn từ chữ probare trong tiếng Latin và có nghĩa là "để chứng minh, để kiểm chứng". Nói một cách đơn giản, probable là một trong nhiều từ dùng để chỉ những sự kiện hoặc kiến thức chưa chắc chắn, và thường đi kèm với các từ như "có vẻ là", "mạo hiểm", "may rủi", "không chắc chắn" hay "nghi ngờ", tùy vào ngữ cảnh. "Cơ hội" (chance), "cá cược" (odds, bet) là những từ cho khái niệm tương tự. Nếu lí thuyết cơ học (cơ học cổ điển) có định nghĩa chính xác cho "công" và "lực", thì lí thuyết xác suất nhằm mục đích định nghĩa "khả năng". Tiếng Hán việt – “Khái xuất” (đại khái, đại xuất)
3. KHÁI NIỆM, ĐỊNH NGHĨA Sự kiện – bất kỳ việc nào mà trong kết quả thực nghiệm là có thể xảy ra hoặc là không xảy ra. Xác suất (Probability) của sự kiện là thước đo mang tính định lượng chỉ mức độ khả năng [xuất hiện] khách quan của sự kiện đó. Biến ngẫu nhiên (random variable) là biến mà có thể nhận giá trị này hay giá trị khác, mà không biết trước. Biến ngẫu nhiên có thể là có 2 loại:  Rời rạc: Ví dụ: Số bài toán được thực hiện bởi máy tính trong một ngày, số lượng truy cập bộ nhớ ngoài trong quá trình giải bài toán,  Liên tục: có thể nhận bất kỳ giá trị nào trong một khoảng nào đó. Những khoảng thời gian giữa những thời điểm đến của những yêu cầu (request) giải quyết bài toán, hoặc là giữa những thời điểm hình thành messageđược truyền trong mạng truyền thông.  Ví dụ biến ngẫu nhiên: X - số lượng truy cập đến ổ cứng trong quá trình giải bài toán, có thể nhận các giá trị sau x1=0,x2=1, ,xn=n.
4. LUẬT PHÂN BỐ CỦA BIẾN NGẪU NHIÊN Mô tả toán học của biến ngẫu nhiên được cho bằng luật phân bố, thiết lập sự tương ứng giữa giá trị và xác suất xuất hiện của chúng. Luật phân bố các biến ngẫu nhiên rời rạc: Ký hiệu mà xác suất mà biến ngẫu nhiên X nhận giá trị :
5. LUẬT PHÂN BỐ CỦA BIẾN NGẪU NHIÊN Luật phân bố các biến ngẫu nhiên liên tục: Hàm phân bố xác suất (hay đơn giản gọi là hàm phân bố, distribution function) của biến ngẫu nhiên X là xác suất mà biến ngẫu nhiên X nhận giá trị nhỏ hơn một giá trị cho trước x nào đó: Tính chất của hàm phân bố:  Hàm phân bố F(x) là hàm không giảm theo đối số của nó, nghĩa là nếu , thì ;  ;  .
6. LUẬT PHÂN BỐ CỦA BIẾN NGẪU NHIÊN Xác suất mà biến ngẫu nhiên nhận giá trị trong khoảng (a,b) nào đó được xác định bởi hàm phân bố: Hàm phân bố F(x) là đặc trưng phổ quát của biến ngẫu nhiên và được sử dụng vừa cho các giá trị liên tục và giá trị rời rạc. Hàm phân bố biến ngẫu nhiên rời rạc X, mà nhận các giá trị được xác định: trong đó – xác suất mà biến ngẫu nhiên X nhận giá trị .
7. MẬT ĐỘ PHÂN BỐ XÁC SUẤT (DISTRIBUTION DENSITY) Mật độ phân bố xác suất f(x) được xác định bởi đạo hàm của hàm phân bố F(x): Tính chất của mật độ phân bố:  Là một hàm không âm: f(x)≥0;  Liên hệ giữa F(x) và f(x):
8. CÁC ĐẶC TÍNH ĐỊNH LƯỢNG CỦA BIẾN NGẪU NHIÊN Giá trị trung bình, mà xung quanh nó tập hợp những giá trị có thể của biến ngẫu nhiên; Cấp độ phân tán của những giá trị xung quanh giá trị trung bình; Tính không đối xứng (hay tính lệch) của mật độ phân bố; Tính dốc (tính nhọn của đỉnh) của mật độ phân bố.
9. THỜI ĐIỂM (MOMENT) CỦA PHÂN BỐ Thời điểm ban đầu được xem như tương đối so với gốc tọa độ. Thời điểm trung tâm – tương đối so với giá trị trung bình (mong đợi toán học), nghĩa là trung tâm phân bố. Để mô tả biến ngẫu nhiên thường sử dụng tập hợp vô cùng các thời điểm ban đầu và thời điểm trung tâm. Giữa các thời điểm và luật phân bố biến ngẫu nhiên tồn tại một sự tương ứng, có nghĩa là, khi biết luật phân bố có thể tính được bất cứ thời điểm (moment) nào, số lượng của chúng (thời điểm) là vô cùng
10. THỜI ĐIỂM BAN ĐẦU Thời điểm ban đầu cấp độ s: Thời điểm ban đầu cấp độ 1: Giá trị trung bình Giá trị trung bình hay mong đợi toán học đặc trưng cho vị trí của biến ngẫu nhiên trên trục số, chỉ ra một giá trị trung bình theo xác suất. Thời điểm ban đầu cấp độ hai của biến ngẫu nhiên X đặc trưng cho độ phân tán , nghĩa là sự tản mát các biến ngẫu nhiên tương đối so với gốc tọa độ.
11. THỜI ĐIỂM TRUNG TÂM Thời điểm trung tâm cấp độ s Hiệu của biến ngẫu nhiên và mong đợi toán học là độ lệch của biến ngẫu nhiên với mong đợi toán học và gọi là biến ngẫu nhiên trung tâm. Khi đó thời điểm trung tâm cấp độ s biến ngẫu nhiên X có thể đuợc xác định như là mong đợi toán học cấp độ s của biến ngẫu nhiên trung tâm tương ứng: Bất kỳ biến ngẫu nhiên nào thì thời điểm trung tâm cấp bậc 1 đều bằng không, vì mong đợi toán học của biến ngẫu nhiên trung tâm là bằng không.
12. THỜI ĐIỂM TRUNG TÂM Thời điểm trung tâm thứ hai được gọi là độ phân tán biến ngẫu nhiên và được ký hiệu là D[X]: Có thể chứng minh rằng: Độ phân tán D[X] (dispersion) cũng như thời điểm ban đầu thứ hai đặc trưng cho độ tản mát các giá trị của biến ngẫu nhiên nhưng là tương đối so với mong đợi toán học, và có thước đo (dimension) là bình phương của biến ngẫu nhiên. Một đặc tính độ tản mát, mà thước đo của nó trùng với chiều đo của biến ngẫu nhiên gọi là độ lệch trung bình bình phương (standard deviation) Một đặc tính tản mát mà không có thước đo, gọi là hệ số biến thiên (variation coefficient):
13. VÍ DỤ MINH HỌA CÁC ĐẶC TÍNH ĐỊNH LƯỢNG Phân bố rời rạc của giá trị ngẫu nhiên X những khoảng thời gian đến của một luồng nào đó: X=[5,8,2,4,6], p1=p2= =p5=0.2 Giá trị trung bình = Thời điểm ban đầu cấp độ 1 = α1[X]= M[X]=0.2x5+0.2x8+0.2x2+0.2x4+0.2x6=0.2x25=5 (M[X]=25/5=5) (vì xác suất bằng nhau) Độ phân tán (tản mát) so với gốc tọa độ: 2 2 2 2 2 α2[X]=0.2x5 +0.2x8 +0.2x2 +0.2x4 +0.2x6 = 29 Biến ngẫu nhiên trung tâm: Xc=[0,3,-3,-1,1] Thời điểm trung tâm cấp bậc 1: β1[X]= (0+3+(-3)+(- 1)+1)/5=0 độ phân tán D[X] so với giá trị trung bình: 2 2 2 2 2 D[X]= β1[X]= (0 +3 +(-3) +(-1) +1 )/5=4 Độ lệch trung bình bình phương (standard deviation): σ[X]=√D[X]=2 Hệ số biến thiên: ν[X]=σ[X]/ M[X]=2/5=0.4
14. NHỮNG PHÂN BỐ ĐIỂN HIÌNH CỦA BIẾN NGẪU NHIÊN Các luật phân bố biến ngẫu nhiên rời rạc được sử dụng rộng rãi nhất là:  Phân bố Poisson;  Phân bố hình học. Những luật phân bố biến ngẫu nhiên liên tục:  Thống nhất (uniform);  Mũ (exponential);  Erlang (HypoExponential);  Erlang chuẩn hóa;  HyperExponential;  HyperErlang;
15. PHÂN BỐ POISSON Biến ngẫu nhiên Poisson thỏa mãn những điều kiện sau:  Số lượng sự kiện diễn ra trong hai khoảng thời gian phân biệt là độc lập.  Xác suất một sự kiện diễn ra trong một khoảng thời gian nhỏ là tỷ lệ thuận với toàn bộ chiều dài của khoảng thời gian đó. Ứng dụng:  Số người chết do ngựa đá trong quân đội Phổ (lần đầu tiên được ứng dụng);  Dị tật bẩm sinh và di truyền đột biến;  Bệnh hiếm gặp (như bệnh bạch cầu, nhưng không phải là AIDS vì nó là truyền nhiễm và do đó không độc lập);  Tai nạn xe hơi;  Lưu lượng dòng chảy và khoảng cách trống lý tưởng;  Số lỗi đánh máy trên một trang;  Tóc tìm thấy trong hamburger của McDonald;  Lỗi của một máy tính trong một tháng.
16. PHÂN BỐ POISSON 0.7 0.6 0.5 0.4 a=0.5 P(X=k) 0.3 a=1 a=2 0.2 0.1 0 0 1 2 3 4 5 6 7 8 k
17. PHÂN BỐ HÌNH HỌC (GEOMETRIC DISTRIBUTION) Phân bố hình học (geometric distribution) biến ngẫu nhiên rời rạc X=k có dạng: 0.9 0.8 0.7 0.6 γ=0.2 0.5 γ=0.5 0.4 P(X=k) γ=0.8 0.3 0.2 0.1 0 Ví dụ về phân bố hình học: 0 1 2 3 4 5 6 7 8 Chọn một con bài từ một bộ bài (không có lá joker) và đoán màu (cơ, rô, chuồn, bích) của nó trước khi nhìn vào nó. Số lần đoán sai sẽ có trước khi đoán đúng có thể được ước tính là [mang tính] hình học (25%). Sự phân bố hình học giả sử rằng là không đổi với mỗi một thử nghiệm, sau mỗi lần sẽ phải đặt lá bài và xáo trộn lại
18. PHÂN BỐ THỐNG NHẤT (UNIFORM) Biến ngẫu nhiên liên tục X phân bố một cách thống nhất (giống nhau, uniform) trong khoản (a,b), nghĩa là xác suất bằng nhau cho tất cả các giá trị từ tối thiểu (a) đến tối đa (b)
19. PHÂN BỐ MŨ (EXPONENTIAL) Điểm đặc biệt của phân bố mũ là, hệ số biến thiên của nó không phụ vào tham số α và luôn bằng 1: . 1 4 0.9 0.8 3.5 α=0.5, M[X]=2 0.7 3 0.6 α=1, M[X]=1 2.5 0.5 α=2, M[X]=0.5 2 0.4 1.5 0.3 1 0.2 0.5 0.1 0 0 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8
20. PHÂN BỐ MŨ (EXPONENTIAL) Giải thích: Nếu các sự kiện được cho là xảy ra ngẫu nhiên theo thời gian (tức là theo tiến trình Poisson) và thời gian trung bình giữa các sự kiện bằng , thì thời gian giữa các sự kiện liên tiếp sẽ được phân bố theo Exp (α). Ví dụ, nếu doanh nghiệp bảo hiểm nhận thấy rằng một số loại thảm họa thiên nhiên cụ thể xảy ra trung bình 5.5 năm một lần, thì thời gian giữa các thiên tai liên tiếp có thể được mô hình hóa như là Exp (1/5.5) năm. Phân bố mũ được sử dụng rộng rãi trong thuyết hàng đợi khi mô tả các tiến trình ngẫu nhiên [chạy] trong các mô hình hàng đợi. Phân bố này tạo điều kiện đạt được những kết quả phân tích đơn giản và có dạng rõ ràng.
21. PHÂN BỐ ERLANG Phân bố Erlang cấp độ k là phân bố mà mô tả biến ngẫu nhiên liên tục X, nhận những giá trị dương (0;+∞) và là tổng của k lần biến ngẫu nhiên không phụ thuộc với nhau, phân bố theo chỉ một và một loại phân bố mũ với tham số α 1 0.9 0.8 0.7 0.6 k=1 0.5 k=2 0.4 k=4 0.3 0.2 0.1 0 0 1 2 3 4 5 6 7 8 Hệ số biến thiên của phân bố Erlang phụ thuộc vào tham số k và nhận giá trị nhỏ hơn hoặc bằng 1.
22. PHÂN BỐ SIÊU MŨ (HYPEREXPONENTIAL) Để xấp xỉ [phân bố] trong những trường hợp phân bố thực của biến ngẫu nhiên liên tục nào đó có hệ số biến thiên lớn hơn 1. Có th ch ng minh 4 ể ứ 3.5 rằng, xác suất xuất 3 hiện những giá trị 2.5 nhỏ của biến ngẫu 2 γ=2 nhiên với phân bố γ=4 1.5 siêu mũ là lớn hơn Exp 1 nhiều so với xác suất 0.5 xuất hiện các giá trị 0 lớn. 0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2 Với phân bố mũ:
23. ‘ĐUÔI’ CỦA HÀM MẬT ĐỘ PHÂN BỐ SIÊU MŨ. 0.02 0.018 0.016 0.014 0.012 γ=2 0.01 γ=4 0.008 Exp 0.006 0.004 0.002 0 4 4.4 4.8 5.2 5.6 6 6.4 6.8 7.2 7.6 8 8.4 8.8 9.2 9.6 1) Đường cong của mật độ phân bố siêu mũ với hệ số biến thiên bằng 4 có ‘đuôi dài’ còn gọi là ‘đuôi nặng’, đặc trưng cho sự ít thay đổi. 2) Với phân bố siêu mũ, xác suất xuất hiện giá trị lớn của biến ngẫu nhiên là cao hơn đáng kể so với, ví dụ như phân bố mũ. 3) Khác nhau cơ bản phân bố siêu mũ với phân bố mũ ở chỗ, phân bố siêu mũ đặc trưng bởi xác suất lớn xuất hiện những giá trị nhỏ của biến ngẫu nhiên và cũng lúc, xác suất lớn xuất hiện những giá trị lớn của biến ngẫu nhiên.
24. CÁC ĐẶC TÍNH ĐỊNH LƯỢNG CỦA CÁC PHÂN BỐ ĐIỂN HÌNH