Chương 1:
Mô hình xác suất
Nguyễn Linh Trung Trần Thị Thúy Quỳnh
Trường Đại học Công nghệ, ĐHQGHN
Nội dung
1.1. Môi trường thiết kế
1.2. Mô hình xác suất 1.2.1. Mô hình 1.2.2. Mô hình toán học 1.2.3. Mô hình xác định 1.2.4. Mô hình xác suất
1.3. Các ví dụ
Chương 1: Mô hình xác suất
Môi trường thiết kế
N. Linh-Trung
1.1. Môi trường thiết kế
Các kỹ sư công nghệ thường làm việc với các hệ thống có tính hỗn loạn. Ví dụ:
1.2.1. Mô hình
1.2.2. Mô hình toán học
(cid:73) Chuyển động nhiệt trong các thiết bị điện tử. (cid:73) Tín hiệu được truyền trong môi trường phức tạp gồm nhiễu
1.2.3. Mô hình xác định
1.2.4. Mô hình xác suất
1.2. Mô hình xác suất
và các thành phần đa đường.
(cid:73) Quản lý và điều khiển mạng phân bố có khắp mọi nơi (dưới
1.3. Các ví dụ
dạng điểm - điểm hoặc mạng lưới).
(cid:73) Học máy (Machine learning): Bộ não cố gắng để suy ra bản
chất của thế giới thông qua các đầu vào cảm giác.
(cid:73) Thông tin trên Internet được tạo ra với tốc độ ngày càng
tăng. Các ứng dụng tìm kiếm ngày càng phải thông minh hơn để đáp ứng yêu cầu tìm kiếm nào đó. VD: đánh giá xu hướng (“like”) của con người trên các mạng xã hội.
(cid:73) ...
Mô hình xác suất là một trong những công cụ đảm bảo: nhà thiết kế cảm nhận được sự hỗn loạn để từ đó xây dựng hệ thống một cách hiệu quả (nhanh, chính xác), tin cậy (chống được lỗi, tấn công mạng), chi phí thấp (hệ thống càng đơn giản càng tốt).
3 / 26
Nội dung
1.1. Môi trường thiết kế
1.2. Mô hình xác suất 1.2.1. Mô hình 1.2.2. Mô hình toán học 1.2.3. Mô hình xác định 1.2.4. Mô hình xác suất
1.3. Các ví dụ
Chương 1: Mô hình xác suất
Mô hình
N. Linh-Trung
(cid:73) Mô hình là biểu diễn gần đúng thực thể vật lý. (cid:73) Mô hình cố gắng giải thích hành vi quan sát được thông qua
1.2.1. Mô hình
1.1. Môi trường thiết kế 1.2. Mô hình xác suất
việc một số quy luật đơn giản và dễ hiểu.
1.2.2. Mô hình toán học
1.2.3. Mô hình xác định
(cid:73) Các quy luật được sử dụng để dự đoán kết quả của các thí
1.2.4. Mô hình xác suất
nghiệm.
(cid:73) Một mô hình hữu ích giải thích tất cả các khía cạnh liên
1.3. Các ví dụ
quan của một tình huống cụ thể. Các mô hình như vậy có thể được sử dụng thay cho các thí nghiệm để trả lời các câu hỏi liên quan đến các thực thể vật lý.
(cid:73) Do đó các mô hình cho phép các kỹ sư tránh các chi phí thử
nghiệm như lao động, thiết bị và thời gian.
5 / 26
Chương 1: Mô hình xác suất
Mô hình toán học
(cid:73) Được sử dụng khi các hiện tượng quan sát có các đặc trưng
N. Linh-Trung
1.1. Môi trường thiết kế
đo đạc.
1.2.1. Mô hình
(cid:73) Được biểu diễn bởi tập các tham số, biến, các công thức toán
1.2.2. Mô hình toán học
1.2.3. Mô hình xác định
1.2. Mô hình xác suất
học liên quan giữa các tham số và các biến.
1.2.4. Mô hình xác suất
(cid:73) Nếu cho các điều kiện lối vào, mô hình toán học sẽ cho các
1.3. Các ví dụ
dự báo lối ra của thực nghiệm.
6 / 26
Chương 1: Mô hình xác suất
Mô hình xác định
(cid:73) Với điều kiện đầu vào, mô hình xác định tính chính xác kết
N. Linh-Trung
1.1. Môi trường thiết kế
quả lối ra của thực nghiệm.
1.2.1. Mô hình
1.2.2. Mô hình toán học
1.2.3. Mô hình xác định
1.2.4. Mô hình xác suất
1.2. Mô hình xác suất
(cid:73) Ví dụ: Định luật Ohm biểu diễn quan hệ I = V /R là một mô hình toán học xác định. Trong cùng điều kiện thực nghiệm nhiều lần mô hình xác định sẽ cho ra cùng kết quả. Tuy nhiên thực tế có thể sai khác so với giá trị dự đoán nhưng không đáng kể.
1.3. Các ví dụ
7 / 26
Chương 1: Mô hình xác suất
Mô hình xác suất
N. Linh-Trung
1.2.1. Mô hình
1.2.2. Mô hình toán học
(cid:73) Mô hình xác suất, còn gọi là thực nghiệm ngẫu nhiên (mô hình toán học ngẫu nhiên) được dùng để mô tả các hiện tượng trong cùng một điều kiện thực nghiệm nhưng có kết quả ngẫu nhiên, không thể dự báo.
1.2.3. Mô hình xác định
1.2.4. Mô hình xác suất
(cid:73) Ví dụ: Ba quả bóng được đánh số 0, 1, và 2 được đặt trong
1.1. Môi trường thiết kế 1.2. Mô hình xác suất
1.3. Các ví dụ
một bình tối.
(cid:73) Yêu cầu: Chọn một quả bóng trong bình và ghi lại số của quả
bóng đó.
(cid:73) Kết quả của thực nghiệm (outcome) có thể là: 0, 1, hoặc 2. (cid:73) Không gian mẫu (sample space): là tập tất cả các kết quả
có thể của thực nghiệm S = 0, 1, 2
(cid:73) Kết quả của thực nghiệm này là ngẫu nhiên và chúng ta
không thể dự đoán chính xác.
8 / 26
Chương 1: Mô hình xác suất N. Linh-Trung
1.2.1. Mô hình
1.2.2. Mô hình toán học
1.2.3. Mô hình xác định
1.2.4. Mô hình xác suất
1.1. Môi trường thiết kế 1.2. Mô hình xác suất
(cid:73) Nhưng: chúng ta vẫn phải "dự đoán các kết quả có thể" (mô hình toán học yêu cầu). Vậy, chúng ta cần dự báo cái gì? Cái gì là hành vi tốt trong những thực nghiệm như vậy?
1.3. Các ví dụ
9 / 26
(cid:73) Tính thống kê: tính trung bình số lần xuất hiện của mỗi kết quả theo số lần thực nghiệm sẽ tiến tới cùng một giá trị.
Chương 1: Mô hình xác suất N. Linh-Trung
1.2.1. Mô hình
1.2.2. Mô hình toán học
1.2.3. Mô hình xác định
1.2.4. Mô hình xác suất
1.1. Môi trường thiết kế 1.2. Mô hình xác suất
1.3. Các ví dụ
10 / 26
Chương 1: Mô hình xác suất N. Linh-Trung
1.2.1. Mô hình
1.2.2. Mô hình toán học
1.2.3. Mô hình xác định
1.2.4. Mô hình xác suất
1.1. Môi trường thiết kế 1.2. Mô hình xác suất
1.3. Các ví dụ
11 / 26
Chương 1: Mô hình xác suất
Tần suất tương đối
(cid:73) Gọi Nk(n) là số lần kết quả k xuất hiện sau n lần lặp lại thực
N. Linh-Trung
1.1. Môi trường thiết kế
nghiệm (trial - lần thử).
1.2.1. Mô hình
(cid:73) Tần suất tương đối của kết quả k là:
1.2.2. Mô hình toán học
1.2.3. Mô hình xác định
1.2.4. Mô hình xác suất
1.2. Mô hình xác suất
1.3. Các ví dụ
fk(n) =
Nk(n) n
(cid:73) Xác suất xuất hiện (mô hình xác suất) của kết quả k được
định nghĩa bởi:
fk(n)
pk = lim n→∞
(cid:73) Như trong ví dụ trên thì: p0 = p1 = p2 = 1/3. (cid:73) Nếu chúng ta thay đổi điều kiện thực nghiệm (ví dụ, 3 quả bóng nhưng đánh số 0, 0, 2), thì mô hình xác suất sẽ là: p0 = 2/3, p2 = 1/3.
12 / 26
Chương 1: Mô hình xác suất
Các tính chất của tần suất tương đối
N. Linh-Trung
1.2.1. Mô hình
1.2.2. Mô hình toán học
1.2.3. Mô hình xác định
1.2.4. Mô hình xác suất
1.1. Môi trường thiết kế 1.2. Mô hình xác suất
1.3. Các ví dụ
1. 0 ≤ fk(n) ≤ 1 2. (cid:80) k fk(n) = 1 3. Gọi E là biến cố “bóng đánh số chẵn được chọn”; cụ thể là, 0 hoặc 2. Do hai kết quả này không thể xuất hiện cùng một thời điểm nên
fE(n) = f0(n) + f2(n)
13 / 26
Chương 1: Mô hình xác suất
Phương pháp tiếp cận lý thuyết xác suất
N. Linh-Trung
1.2.1. Mô hình
(cid:73) Việc tiếp cận lý thuyết xác suất từ tần suất tương đối rất khó do phải thỏa mãn các định nghĩa và tính chất của tần suất tương đối, nhưng:
1.2.2. Mô hình toán học
1.2.3. Mô hình xác định
1.1. Môi trường thiết kế 1.2. Mô hình xác suất
1.2.4. Mô hình xác suất
(cid:73) Không biết giới hạn trong tần suất tương đối có tồn tại hay
không?
1.3. Các ví dụ (cid:73) Không thể lặp lại thực nghiệm đến vô hạn (không thể tính
giới hạn) từ đó không biết chính xác pk.
(cid:73) Có những thực nghiệm không thể tiến hành hoặc không thể
lặp lại.
(cid:73) Giải pháp: Cần xây dựng lý thuyết xác suất với các tính chất
phù hợp với tính chất của tần suất tương đối.
14 / 26
Chương 1: Mô hình xác suất N. Linh-Trung
1.1. Môi trường thiết kế 1.2. Mô hình xác suất
Các bước xây dựng mô hình xác suất gồm có: (cid:73) Định nghĩa một thực nghiệm ngẫu nhiên (cid:73) Tính không gian mẫu S (cid:73) Xây dựng lớp các biến cố F (mỗi biến cố là một tập con của
1.2.1. Mô hình
1.2.2. Mô hình toán học
S).
1.2.3. Mô hình xác định
1.2.4. Mô hình xác suất
(cid:73) Chỉ định một số P ứng với biến cố A.
(cid:73) 3 định lý xác suất dựa trên tần suất tương đối như sau:
1.3. Các ví dụ
1. 0 ≤ P [A] ≤ 1 2. P [S] = 1 3. if A, B là loại trừ lẫn nhau, thì
P [A or B] = P [A] + P [B]
Kết quả tính toán tùy thuộc vào việc chỉ định giá trị P [A] đối với mỗi ứng dụng nhất định (thông thường, chúng ta cần biết trước giá trị này).
15 / 26
Nội dung
1.1. Môi trường thiết kế
1.2. Mô hình xác suất 1.2.1. Mô hình 1.2.2. Mô hình toán học 1.2.3. Mô hình xác định 1.2.4. Mô hình xác suất
1.3. Các ví dụ
Chương 1: Mô hình xác suất
Kiểm tra cuộc hội thoại qua điện thoại
(cid:73) Bài toán 1: Kiểm tra một cuộc hội thoại xem người thực
N. Linh-Trung
1.1. Môi trường thiết kế
hiện có đang nói không.
1.2.1. Mô hình
(cid:73) Biết trước: trung bình người thực hiện nói trong 1/3 thời
1.2.2. Mô hình toán học
1.2.3. Mô hình xác định
1.2. Mô hình xác suất
gian, thời gian còn lại là khoảng im lặng (nghe, hoặc nghỉ).
1.2.4. Mô hình xác suất
(cid:73) Câu hỏi: Xây dựng mô hình xác suất từ vấn đề thực tế?
1.3. Các ví dụ (cid:73) Định nghĩa thực nghiệm: bình chứa 3 bóng: 2 bóng đen (b)
cho im lặng, 1 bóng trắng (w) cho nói.
S = {b, w} F = {∅, b, w, (b, w)}
(cid:73) Xác định không gian mẫu S và lớp các biến cố F:
(cid:73) Các xác suất được chỉ định là: P [b] = 2/3, P [w] = 1/3.
17 / 26
(cid:73) Bài toán 2: Cho hệ thống có khả năng phát đồng thời 48
Chương 1: Mô hình xác suất N. Linh-Trung
kênh hội thoại
(cid:73) Câu hỏi: Xác suất để lớn hơn 24 trong số 48 người thực hiện
1.1. Môi trường thiết kế 1.2. Mô hình xác suất
cuộc gọi độc lập nói cùng một thời điểm?
1.2.1. Mô hình
1.2.2. Mô hình toán học
1.2.3. Mô hình xác định
1.2.4. Mô hình xác suất
=22×48 tổ hợp (có hoặc không có kết quả chứa
S = 248 tổ hợp từ b, w F =2248 trong S - nhị phân)
(cid:73) Mô hình xác suất: Lặp lại thực nghiệm chọn bóng (mô hình xác suất của bài toán 1) 48 lần, tính xác suất để sau 48 lần thử, số bóng trắng lớn hơn 24? 1.3. Các ví dụ (cid:73) Xác định không gian mẫu S và lớp các biến cố F:
X > 24 thì
48 (cid:88)
P [f ] =
P (X = x)
(1)
x=25
Với P (X = x) = C48
x P [w]xP [b](48−x), C48
x =
48! x!(48−x)!
(cid:73) Các xác suất được tính là: (cid:73) P [b] = 2/3, P [w] = 1/3 (cid:73) Gọi X là số bóng trắng suất hiện sau 48 lần thử. f là biến cố
18 / 26
Chương 1: Mô hình xác suất
Hệ truyền thoại chuyển mạch gói
(cid:73) Bài toán 3: Thiết kế hệ truyền thoại chuyển mạch gói cho 48
N. Linh-Trung
1.1. Môi trường thiết kế
người dùng.
1.2.1. Mô hình
(cid:73) Gói tin:
1.2.2. Mô hình toán học
1.2.3. Mô hình xác định
1.2.4. Mô hình xác suất
1.2. Mô hình xác suất
(cid:73) Tiếng nói được biến đổi thành sóng điện áp (cid:73) Tín hiệu điện được số hóa thành một chuỗi các số nhị phân 1.3. Các ví dụ
(thông tin dưới dạng bits)
(cid:73) Các bits được gộp lại thành các gói tin (cid:73) Mỗi gói tin tương ứng với một đoạn thoại dài 10 ms (cid:73) Môi trường là ngẫu nhiên: chúng ta không biết có bao nhiêu
người nói hoặc im lặng ở một thời điểm cụ thể.
(cid:73) Bài toán được đơn giản thành: Thiết kế hệ truyền các gói tin
thoại 10 ms cho N = 48 người dùng.
19 / 26
Chương 1: Mô hình xác suất N. Linh-Trung
1.2.1. Mô hình
1.2.2. Mô hình toán học
1.2.3. Mô hình xác định
1.2.4. Mô hình xác suất
1.1. Môi trường thiết kế 1.2. Mô hình xác suất
1.3. Các ví dụ
20 / 26
Chương 1: Mô hình xác suất N. Linh-Trung
(cid:73) Các đặc trưng thoại được biết trước: trung bình, 2/3 thời gian của cuộc thoại là im lặng (nghe/nghỉ) và 1/3 là nói. (cid:73) Nếu hệ thống được thiết kế với M > 48, thì hệ thống này là
1.1. Môi trường thiết kế 1.2. Mô hình xác suất
không hiệu quả do tốn tài nguyên.
1.2.1. Mô hình
1.2.2. Mô hình toán học
(cid:73) Câu hỏi 1 [về thiết kế hệ thống]: Nên chọn giá trị M bằng
1.2.3. Mô hình xác định
bao nhiêu để hệ thống được gọi là hiệu quả?
1.2.4. Mô hình xác suất
(cid:73) Câu hỏi 2 [về hiệu năng của hệ thống]: Tính trung bình, hệ
1.3. Các ví dụ
thống sẽ phát bao nhiêu gói tin trong một ngày?
21 / 26
Chương 1: Mô hình xác suất
Bây giờ chúng ta sẽ xây dựng mô hình xác suất:
(cid:73) Thực nghiệm ngẫu nhiên: tung một đồng xu 48 lần (ứng với
N. Linh-Trung
1.1. Môi trường thiết kế
48 gói tin) và đếm (k) lần ngửa (gói tin chứa thoại); 0 ≤ k ≤ 48.
1.2.1. Mô hình
1.2.2. Mô hình toán học
1.2.3. Mô hình xác định
(cid:73) Không gian mẫu: S = {0, 1, . . . , 48}. (cid:73) Lớp biến cố: F = {x : x là tập con của S}.
1.2.4. Mô hình xác suất
1.2. Mô hình xác suất
(cid:73) Các xác suất:
1.3. Các ví dụ
(cid:73) Tung 1 lần (thực nghiệm con): Xác suất mà mặt ngửa xuất
hiện là:
p = 1/3
(cid:73) Tung N = 48 lần (thực nghiệm): Các xác suất k mặt ngửa
xuất hiện (luật xác suất nhị thức-binomial):
pk(1 − p)N −k
với k = 0, . . . , 48
pk =
N ! k!(N − k)!
22 / 26
Chương 1: Mô hình xác suất N. Linh-Trung
1.2.1. Mô hình
1.2.2. Mô hình toán học
1.2.3. Mô hình xác định
1.2.4. Mô hình xác suất
1.1. Môi trường thiết kế 1.2. Mô hình xác suất
1.3. Các ví dụ
Vậy, nên chọn giá trị M bằng bao nhiêu?
23 / 26
Chương 1: Mô hình xác suất
Giá trị trung bình (Giả thiết chọn M = 48):
(cid:73) Thực hiện thực nghiệm n lần (cid:73) A(j) là kết quả tổng số gói tin chứa thoại của hệ thống ở lần
N. Linh-Trung
1.1. Môi trường thiết kế 1.2. Mô hình xác suất
thử thứ j
1.2.1. Mô hình
1.2.2. Mô hình toán học
(cid:73) Nk(n) là số lần thử mà trong đó có k gói tin chứa thoại xuất
1.2.3. Mô hình xác định
hiện
1.2.4. Mô hình xác suất
(cid:73) Trung bình dài hạn (Long-term average) hay trung bình mẫu (sample mean): được định nghĩa là trung bình số gói tin chứa thoại được tạo ra trong 10 ms.
n (cid:88)
1.3. Các ví dụ
A(j)
1 n
j=1
Giá trị này đo hiệu năng của hệ thống.
(cid:73) Trung bình thống kê (Statistical average) hay kỳ vọng
(expected value): được định nghĩa bởi mô hình xác suất như sau:
48 (cid:88)
kpk
k=1
24 / 26
(cid:73) Quan hệ giữa Trung bình dài hạn và Trung bình thống kê như
Chương 1: Mô hình xác suất N. Linh-Trung
sau:
n (cid:88)
48 (cid:88)
48 (cid:88)
48 (cid:88)
1.1. Môi trường thiết kế 1.2. Mô hình xác suất
A(j) =
kNk(n) =
kfk(n) n→∞−−−−→
kpk
1.2.1. Mô hình
1 n
1 n
1.2.2. Mô hình toán học
j=1
k=1
k=1
k=1
1.2.3. Mô hình xác định
1.2.4. Mô hình xác suất
(cid:73) Do đó, với mô hình xác suất được xây dựng, chúng ta có thể tính xấp xỉ trung bình dài hạn và có thể biết được hiệu năng của hệ thống.
(cid:73) Vậy, có bao nhiêu gói tin mà hệ thống tạo ra trong vòng một
1.3. Các ví dụ
ngày? (cid:80)48
k=1 kpk là số gói tin trung bình được tạo ra trong 10 ms.
Vậy trong 1 ngày số gói tin được tạo ra là:
48 (cid:88)
(2)
kpk = 1, 3824 ∗ 108
24h × 60p × 60s × 1.000ms 10ms
k=1
25 / 26
Chương 1: Mô hình xác suất
Bài tập về nhà
N. Linh-Trung
(cid:73) Bài: 1.1, 1.2, 1.4, 1.8, 1.9 trang 19, 20. (cid:73) Đọc: Nội dung 1.4.
1.2.1. Mô hình
1.2.2. Mô hình toán học
1.2.3. Mô hình xác định
1.2.4. Mô hình xác suất
1.1. Môi trường thiết kế 1.2. Mô hình xác suất
1.3. Các ví dụ
26 / 26
