# Buổi 01: Xác suất cơ bản
## 1. Giải tích kết hợp
### 1.1. Quy tắc cộng

**Ví dụ:** Có $2$ loại phương tiện để sinh viên đi học là phương tiện cá nhân và phương tiện công cộng. Trong đó phương tiện cá nhân bao gồm ô tô, bồ chở, cổng dịch chuyển. Phương tiện công cộng gồm xe buýt, máy bay, tên lửa. Vậy sinh viên có thể đi học bằng cách nào?

**Giải**

Có $3$ cách đi bằng phương tiện cá nhân và $3$ cách đi bằng phương tiện công cộng. Do đó có tổng cộng $3 + 3 = 6$ cách sinh viên di chuyển.

---

#### Quy tắc cộng: Nếu một công việc có thể được thực hiện theo $n$ cách khác nhau hoặc $m$ cách khác nhau, và hai cách này không thể xảy ra đồng thời (tức là loại trừ nhau), thì tổng số cách thực hiện công việc đó là: $n + m$ cách.

---

Trong các bài tập ứng dụng quy tắc cộng, ta nên xác định ra các trường hợp, và số cách chọn các trường hợp đó. Với ví dụ trên, các trường hợp ở đây là phương tiện cá nhân và phương tiện công cộng. Mỗi loại phương tiện có số cách chọn lần lượt là $3$. Theo quy tắc cộng thì kết quả là $6$, như bài giải ta làm ở trên.

Tổng quát, khi ta có nhiều trường hợp và mỗi trường hợp có nhiều cách chọn thì:


### 1.2. Quy tắc nhân

**Ví dụ:** Một sinh viên UIT đến trường bằng cách đi từ KTX đến chợ Nhân Văn rồi mới vòng lại UIT, tại vì bản còn phải ăn sáng. Có 4 đường đi từ KTX đến chợ Nhân Văn, từ chợ đến UIT có 2 đường. Vậy có nhiêu cách để sinh viên này đến trường?

**Giải**

Để đến trường, sinh viên cần đi qua 2 bước:
Bước 1: Đến chợ Nhân Văn, có 4 cách.
Bước 2: Từ chợ Nhân Văn đến UIT, có 2 cách.
Vậy số cách để sinh viên này đến UIT là 2 x 4 = 8 cách.

---

#### Quy tắc nhân: Nếu một công việc gồm hai bước. Bước 1 có n cách thực hiện. Bước 2 có m cách thực hiện (với mỗi cách của bước 1), thì tổng số cách thực hiện cả công việc là: n × m cách.

---

Trong các bài tập ứng dụng quy tắc nhân, ta cần xác định ra các bước, quy trình thực hiện một công việc gì đó. Và ứng với mỗi bước có các nhánh thực hiện khác nhau. Do đó cần nhân lại để ra kết quả.
Quy tắc nhân thực chất được xây dựng trên nền tảng quy tắc cộng. Ví dụ trên đây cũng có thể tính được bằng quy tắc cộng, chỉ có điều số trường hợp cần phải chia ra nhiều hơn thôi.

Tổng quát, khi ta có nhiều nhánh thực hiện thì:


### 1.3. Một số công thức cơ bản
#### 1.3.1. Tổ hợp

- Là số cách **chọn phần tử** từ một tập hợp.
- **Không phân biệt thứ tự**.

**Ví dụ:** Chọn 2 chữ trong A, B, C → các tổ hợp: AB, AC, BC (không tính BA, CA, CB vì giống nhau).

**Công thức tổ hợp:**

$$
C_n^k = \binom{n}{k} = \frac{n!}{k!(n-k)!}
$$

Với k là số phần tử cần chọn và n là tổng số phần tử của tập hợp đó.

#### 1.3.2. Chỉnh hợp

- Là số cách **sắp xếp các phần tử** trong một tập hợp.
- **Phân biệt thứ tự**.

Ví dụ: Sắp xếp 3 chữ cái A, B, C → có 6 cách (ABC, ACB, BAC, BCA, CAB, CBA).

**Công thức chỉnh hợp:**

$$
A_n^k = \frac{n!}{(n-k)!}
$$

Với k là số phần tử cần chọn và n là tổng số phần tử của tập hợp đó.

**Chỉnh hợp chập k gấp k! lần so với tổ hợp chập k với cùng một số n. Tại sao lại như vậy?** Với mỗi tổ hợp (không quan trọng thứ tự), ta có k! cách xếp lại thứ tự để tạo ra các chỉnh hợp.

#### 1.3.3. Hoán vị

- Là chỉnh hợp khi chọn toàn bộ phần tử để sắp xếp.

$$
P_n = n!
$$

### 1.4. Ứng dụng

- Trong **xác suất thống kê**: để đếm số trường hợp thuận lợi và toàn bộ không gian mẫu.
- Trong **tin học**: các thuật toán sinh hoán vị, tổ hợp, cây tìm kiếm…
- Trong **mật mã học**: đếm số mã khóa, mật khẩu.
- Trong **lập kế hoạch**, **tối ưu hóa**, và nhiều lĩnh vực kỹ thuật, khoa học máy tính, kinh tế.

## 2. Xác suất cơ bản
### 2.1. Sự kiện là gì?

**Biến cố - sự kiện (event)** là một kết quả nào đó mà ta quan tâm.
Ví dụ tôi quan tâm đến : Hôm nay crush mặc áo màu gì? (sự kiện) => Cách kiểm tra là lại ngó (phép thử)

**Phép thử** là việc thực hiện một số điều kiện nào đó để quan sát kết quả xảy ra.

**Sự kiện sơ cấp** là kết quả của phép thử và không thể chia nhỏ ra nữa.

**Không gian mẫu** là tập tất cả các sự kiện sơ cấp có thể xảy ra.
=> Trong toán học thì sự kiện là tập con của không gian mẫu.

**Ví dụ**: Gieo xúc xắc một lần
Thì không gian mẫu là {1, 2, 3, 4, 5, 6}
Từng phần tử riêng biệt trong không gian mẫu là sự kiện sơ cấp.
Sự kiện A: "Gieo được mặt chẵn" là {2, 4, 6}.
Sự kiện B: "Gieo được mặt < 4" là {1, 2, 3}.
Sự kiện C: "Gieo được mặt lục" là {6}.

Ngoài ra còn có các loại sự kiện chắc chắn, sự kiện không thể, sự kiện ngẫu nhiên.

### 2.2. Quan hệ và phép toán của các sự kiện

Giả sử A và B là 2 sự kiện trong cùng một phép thử.

#### 2.2.1. Quan hệ kéo theo

Sự kiện A được gọi là kéo theo sự kiện B nếu A xảy ra thì B xảy ra. Kí hiệu A => B.
Theo góc nhìn tập hợp thì có thể nói rằng tập hợp A là con của tập hợp B.


#### 2.2.2. Quan hệ tương đương

Sự kiện A được gọi là tương đương với sự kiện B nếu A => B và B => A. Kí hiệu A <=> B hoặc A = B.
Theo góc nhìn tập hợp thì A = B vì A là con B và B là con A.

#### 2.2.3. Sự kiện tổng

Sự kiện C = A + B xảy ra khi có ít nhất một trong hai sự kiện A và B xảy ra.
Theo góc nhìn tập hợp thì C là hợp của A và B.

Tổng quát: Sự kiện tổng của n sự kiện xảy ra khi ít nhất một trong n sự kiện đó xảy ra.


#### 2.2.4. Sự kiện tích

Sự kiện C = A.B xảy ra khi và chỉ khi A và B cùng xảy ra.
Theo góc nhìn tập hợp thì C là giao của A và B.

Tổng quát: Sự kiện tích của n sự kiện xảy ra khi tất cả n sự kiện đó xảy ra.


#### 2.2.5. Sự kiện đối lập

Sự kiện đối lập với sự kiện A, kí hiệu A~, là sự kiện xảy ra khi A không xảy ra.
Theo góc nhìn tập hợp thì A~ là phần bù của A trong không gian mẫu.


#### 2.2.6. Sự kiện hiệu

Sự kiện C = A - B là sự kiện mà A xảy ra nhưng B không xảy ra.
Dễ thấy A~ = không gian mẫu - A.
Ta có thể biến đổi A - B = A.B~


Ngoài ra, ta có cách biểu diễn khác cho các sự kiện hiệu giữa A và B.


#### 2.2.7. Hai sự kiện xung khắc

Hai sự kiện A và B được gọi là xung khắc với nhau nếu chúng không đồng thời xảy ra trong cùng một phép thử, tương đương với việc A.B là tập hợp rỗng.


Nếu B là sự kiện đối lập của A => A và B xung khắc.
Nếu A và B xung khắc => B là tập con của A~.

#### 2.2.8. Ví dụ

Sự kiện A: "Sinh viên thi qua môn DSA"
Sự kiện B: "Sinh viên thi qua môn OOP"
Sự kiện C: "Sinh viên thi môn DSA được điểm xuất sắc"
Sự kiện D: "Sinh viên thi môn DSA được điểm >= 5"
Sự kiện E: "Sinh viên thi môn DSA được điểm 4"

Ta có:
Sự kiện A + B: "Sinh viên thi qua ít nhất một trong 2 môn DSA và OOP"
Sự kiện A.B: "Sinh viên thi qua cả hai môn DSA và OOP"
Sự kiện A~: "Sinh viên thi không qua môn DSA"
Sự kiện A - B: "Sinh viên thi qua môn DSA nhưng không qua môn OOP"

Sự kiện C => Sự kiện A (vì được điểm xuất sắc thì chắc chắn là qua môn rồi).
Sự kiện D <=> Sự kiện A (vì được điểm >=5 thì tính là qua môn)
Sự kiện E và D là xung khắc (vì không thể cùng xảy ra).

#### 2.2.9. Các tính chất

Các tính chất tương tự với các phép toán trên tập hợp.



### 2.3. Các định nghĩa xác suất
#### 2.3.1. Xác suất của một sự kiện

Xác suất của một sự kiện là số nằm giữa 0 và 1, đo lường khả năng xuất hiện của sự kiện đó khi phép thử được thực hiện. Kí hiệu xác suất của sự kiện A là P(A).


#### 2.3.2. Xác suất theo định nghĩa cổ điển

Xét một phép thử có hữu hạn kết cục xảy ra (có n kết cục), các kết cục này là đồng khả năng xuất hiện. Trong đó có m kết quả thuận lợi cho A.

$$
P(A) = \frac{m}{n}
$$

**Ví dụ:** Gieo xúc xắc một lần
Thì không gian mẫu là {1, 2, 3, 4, 5, 6}
Gọi A là sự kiện gieo được mặt chẵn.
Xác suất của A là

$$
P(A) = \frac{3}{6} = \frac{1}{2}
$$

#### 2.3.3. Xác suất theo quan điểm hình học

Giả sử tập hợp **vô hạn** kết cục đồng khả năng của một phép thử có thể biểu thị bởi một miền hình học H có độ đo (độ dài, diện tích, thể tích,...) hữu hạn khác 0, còn tập các kết cục thuận lợi cho A là miền A.

$$
P(A) = \frac{|A|}{|H|}
$$

Với |A| là độ đo của miền A và |H| là độ đo của miền H.

**Lưu ý**: Khái niệm đồng khả năng trên H có nghĩa là điểm gieo có thể rơi vào bất kì điểm nào thuộc H.

**Ví dụ:** Quãng đường từ tim em đến tim crush là 2006km. Tính xác suất để thính em thả bị crush phũ đâu đó trong khoảng 305km đổ lại.


(Hình mang tính chất minh họa dễ nhìn, không dùng để minh họa bài toán)

**Giải**

Gọi A là xác suất thính bị phũ <= 305km tính từ tim em.

$$
P(A) = \frac{305}{2006} = 0.152
$$

#### 2.3.4. Xác suất theo quan điểm thống kê

Vì tính đồng khả năng là rất khó để có được trong thực tế, cần có một cách khác để xác định xác suất của một sự kiện.

Giả sử một phép thử có thể thực hiện lặp lại nhiều lần trong những điều kiện giống nhau. Nếu trong n lần thực hiện phép thử trên có m lần xảy ra A, khi đó tỉ lệ

$$
f_n(A) = \frac{m}{n}
$$

gọi là tần suất xuất hiện của A trong n phép thử. Sau đó ta cho số phép thử tăng lên vô hạn:

$$
P(A) = \lim_{n \to \infty} f_n(A) = \lim_{n \to \infty} \frac{m}{n}.
$$

Thực tế nó xấp xỉ bằng tần suất của A khi n đủ lớn.

**Ví dụ:** Xác suất tung đồng xu được mặt ngửa là 0.5 vì với số lượng tung đủ nhiều thì nó xấp xỉ bằng số này.

#### 2.3.5. Nhận xét

Nhược điểm của định nghĩa cổ điển là sự hữu hạn của các phép thử, và các phép thử phải đồng khả năng. Định nghĩa theo quan điểm hình học và thống kê giúp khắc phục nhược điểm này.

### 2.4. Công thức cộng xác suất

Ý tưởng của công thức xuất phát từ **nguyên lí bao hàm - loại trừ (P.I.E)**, dễ dàng thấy nó trong các bài toán tổ hợp đếm.

Nếu A và B là hai sự kiện bất kì thì ta có

$$
P(A + B) = P(A) + P(B) - P(AB)
$$

Nếu A và B xung khắc thì

$$
P(A + B) = P(A) + P(B)
$$


Trường hợp tổng quát:

$$
P\left( \bigcup_{i=1}^{n} A_i \right) =
\sum_{i} P(A_i) - \sum_{i<j} P(A_i A_j) + \sum_{i<j<k} P(A_i A_j A_k) - \cdots + (-1)^{n-1} P\left( \bigcap_{i} A_i \right).
$$

Nếu n sự kiện đôi một xung khắc thì:

$$
P(A_1 + A_2 + \cdots + A_n) = P(A_1) + P(A_2) + \cdots + P(A_n)
$$

### 2.5. Công thức nhân xác suất
#### 2.5.1. Xác suất điều kiện

Xác suất xảy ra A với điều kiện B đã xảy ra trước đó được gọi là xác suất có điều kiện B của A. Kí hiệu P(A|B).

$$
P(A|B) = \frac{P(AB)}{P(B)}
$$

Có thể hiểu là tính xác suất chọn được miền A trong miền B, sau khi B đã xảy ra thì B thành không gian mẫu.

**Ví dụ:** Xác suất để một sinh viên vừa dùng Codeblocks vừa dùng DevC++ là 30%. Xác suất để một sinh viên dùng DevC++ là 40%. Biết rằng crush em dùng DevC++, xác suất để bản dùng Codeblocks là bao nhiêu?

**Giải**

Gọi A là sự kiện sinh viên dùng Codeblocks.
B là sự kiện sinh viên dùng DevC++.
Theo đề bài P(AB) = 0.3 và P(B) = 0.4
Vậy xác suất cần tính là:

$$
P(A|B) = \frac{P(AB)}{P(B)} = \frac{0.3}{0.4} = 0.75
$$

#### 2.5.2. Công thức nhân xác suất

$$
P(AB) = P(B)P(A|B) = P(A)P(B|A)
$$

Tổng quát cho n sự kiện:

$$
P(A_1 A_2 \ldots A_n) = P(A_1) \cdot P(A_2 \mid A_1) \cdot P(A_3 \mid A_1 A_2) \cdots P(A_n \mid A_1 A_2 \ldots A_{n-1})
$$

Nếu n sự kiện này đôi một độc lập:

$$
P(A_1 A_2 \ldots A_n) = P(A_1) \cdot P(A_2) \cdots P(A_n)
$$
#### 2.5.3. Hai sự kiện độc lập

Hai sự kiện A và B gọi là độc lập nếu việc xảy ra hay không xảy ra của sự kiện này không ảnh hưởng đến việc xảy ra của sự kiện kia.

$$
\left\{
\begin{aligned}
P(A) &= P(A \mid B) = P\left(A \mid \overline{B}\right) \\
P(B) &= P(B \mid A) = P\left(B \mid \overline{A}\right)
\end{aligned}
\right.
$$

Hai sự kiện A và B độc lập khi và chỉ khi:

$$
P(AB) = P(A)P(B)
$$

Nếu A và B độc lập thì các cặp sau cũng độc lập: A và B~, A~ và B~, A~ và B.

**Lưu ý**: Cần phân biệt rõ độc lập và xung khắc, tránh nhầm lẫn.

### 2.6. Công thức Bernoulli

Tiến hành n phép thử độc lập. Giả sử trong mỗi phép thử chỉ có thể xảy ra một trường hợp: A xảy ra hoặc không xảy ra. Xác suất để A xảy ra trong mỗi phép thử đều bằng p. Đây là dãy phép thử Bernoulli.
Xác suất để A xảy ra đúng k lần trong n phép thử của dãy phép thử Bernoulli là:

$$
p_n(k) = C_n^k p^k q^{n-k}, \quad q = 1 - p; \quad k = 0, 1, \ldots, n.
$$

Đây là nền tảng của phân phối xác suất nhị thức sau này. Có thể hiểu là chọn k chỗ để A xảy ra trong dãy phép thử n chỗ đó.

### 2.7. Công thức xác suất đầy đủ và công thức Bayes


#### 2.7.1. Nhóm đầy đủ


Đối với một sự kiện A thì ta có nhóm đầy đủ {A, A~}
Đối với 2 sự kiện A và B thì ta có nhóm đầy đủ {AB, AB~, A~B, A~ B~}.


#### 2.7.2. Công thức xác suất đầy đủ

Giả sử có nhóm đầy đủ từ A~1~ đến A~n~. Xét sự kiện H sao cho H chỉ xảy ra khi có ít nhất 1 trong các sự kiện trong nhóm trên xảy ra. Khi đó ta có công thức xác suất đầy đủ:

$$
P(H) = \sum_{k=1}^{n} P(A_k) \cdot P(H \mid A_k)
$$

Có thể hiểu là khi H xảy ra thì một sự kiện A~i~ nào đó xảy ra.

**Ví dụ:** Xét một lớp học hè môn Giải Tích ở UIT, có hai loại là sinh viên học lại và sinh viên học cải thiện. Biết xác suất sinh viên học cải thiện trong lớp đó là 60%. Sau kì thi cuối kì, có một số sinh viên đã qua môn. Xác suất sinh viên học lại qua môn là 50%, còn xác suất sinh viên học cải thiện qua môn là 90%. Tính xác suất sinh viên trong lớp đó qua môn.

**Giải**

Vì sinh viên qua môn thì chỉ thuộc hai loại là sinh viên học lại và cải thiện, 2 loại này tạo thành một nhóm đầy đủ.
Do đó ta áp dụng công thức trên:

$$
P(H) = P(A_1) \cdot P(H \mid A_1) + P(A_2) \cdot P(H \mid A_2)
$$

Với A~1~ là sinh viên học lại, A~2~ là sinh viên học cải thiện.
Ta có P(A~1~) = 1 - 0.6 = 0.4, P(A~2~) = 0.6, P(H|A~1~) = 0.5, P(H|A~2~) = 0.9.

#### 2.7.3. Công thức Bayes

Có thể xem bài toán với công thức Bayes là bài toán ngược với bài toán công thức xác suất đầy đủ, vì ta sẽ đi tính P(A~i~ | H).

$$
P(A_i \mid H) = \frac{P(A_i) \cdot P(H \mid A_i)}{\sum_{k=1}^{n} P(A_k) \cdot P(H \mid A_k)}
$$

**Ví dụ:** Xét lại ví dụ ở mục 2.7.2. Chọn một trong số những sinh viên đã qua môn, tính xác suất sinh viên đó học cải thiện?

**Giải**

Trước tiên ta cần tính P(H). Công việc này đã được làm ở mục 2.7.2.
Áp dụng công thức Bayes:

$$
P(A_2 \mid H) = \frac{P(A_2) \cdot P(H \mid A_2)}{P(H)}
$$

Thay số vào như ví dụ mục trước đó ta ra xác suất cần tính.