Le Van Thanh's Blog

1.3. Phép thử ngẫu nhiên và không gian mẫu

Posted on February 9, 2015 by lvthanh07

Trong bài này, ta sẽ trình bày khái niệm phép thử ngẫu nhiên, không gian mẫu và các biến cố để đi đến định nghĩa xác suất theo hệ tiên đề Kolmogorov.

Phép thử ngẫu nhiên là những thí nghiệm, quan sát, hành động, … mà kết quả xảy ra một cách ngẫu nhiên, không biết trước được. Chẳng hạn, tung một đồng xu thì ta không biết trước được mặt sấp hay mặt ngửa xuất hiện, khoảng thời gian giữa hai email mà ta nhận được ta cũng không biết trước được là bao nhiêu phút. Những thí nghiệm/quan sát này là các ví dụ về phép thử ngẫu nhiên.

Tập hợp tất cả các kết quả có thể có của phép thử ngẫu nhiên được gọi là không gian mẫu, ký hiệu là $\Omega$ . Các phần tử của $\Omega$ được gọi là các biến cố sơ cấp, thường được ký hiệu là $\omega$ . Không gian mẫu còn gọi là không gian các biến cố sơ cấp. Chúng ta xem xét các ví dụ sau đây.

Ví dụ 1.3.1. Một người tung một con xúc xắc sáu mặt. Khi đó, không gian mẫu là

$\Omega=\{1,\ 2,\ 3,\ 4,\ 5,\ 6\}.$

Ví dụ 1.3.2. Giả sử ta quan sát một người lạ và dự đoán ngày sinh của người đó. Khi đó, không gian mẫu sẽ là

$\Omega=\{1/1,\ 2/1,\dots,\ 31/12\}.$

Ví dụ 1.3.3. Một người đưa thư đi qua một đoạn đường có ba cột đèn giao thông. Tại mỗi cột đèn người đó sẽ tiếp tục đi (c) nếu gặp đèn xanh hoặc vàng, và dừng lại (s) nếu gặp đèn đỏ. Khi đó, không gian mẫu là

$\Omega=\{ccc,\ ccs,\ csc,\ scc,\ css,\ scs,\ ssc,\ sss\}.$

Ví dụ 1.3.4. Số email mà một người nhận được mỗi ngày cũng là một số ngẫu nhiên. Không gian mẫu là

$\Omega=\{0,1,\ 2,\ 3,\dots\}.$

Ví dụ 1.3.5. Tuổi thọ của một loài nào đó cũng không định trước được, và nhiều khi cũng được mô hình hóa như là một số ngẫu nhiên. Trong ví dụ này, không gian mẫu là tập hợp tất cả các số thực không âm

$\Omega=\{t|t\ge 0\}.$

Trong lý thuyết xác suất, ta thường quan tâm đến một tập con nào đó của không gian mẫu, tức là một tập hợp các kết quả có thể nào đó của phép thử ngẫu nhiên. Một tập con của không gian mẫu được gọi là một biến cố, hay sự kiện. Chẳng hạn, trong Ví dụ 1.3.1., biến cố xuất hiện mặt có số chấm là một số chẵn lớn hơn $3$ là

$A=\{4,\ 6\}.$

Một biến cố sơ cấp thuộc biến cố $A$ được gọi là kết quả (biến cố sơ cấp) thuận lợi cho biến cố $A$ . Trong trường hợp xét ở trên, $4$ và $6$ là các kết quả thuận lợi cho $A$ . Tập rỗng $\emptyset$ là biến cố không chứa kết quả nào của phép thử ngẫu nhiên, và được gọi là biến cố không thể. Trong khi đó, tập $\Omega$ là biến cố chứa tất cả các kết quả có thể của phép thử ngẫu nhiên, và được gọi là biến cố chắc chắn.

Vì các biến cố là các tập hợp nên các khái niệm và phép toán đại số về tập hợp như khái niệm tập con, phần bù, giao của hai tập hợp, hợp của hai tập hợp,… được vận dụng trực tiếp trong lý thuyết xác suất. Nếu $A\subset B$ thì sự xảy ra của biến cố $A$ sẽ kéo theo biến cố $B$ . Khi đó ta nói $A$ kéo theo $B$ . Trong Ví dụ 1.3.1, biến cố xuất hiện có số chấm là một số chẵn là

$B=\{2,\ 4,\ 6\}.$

Với hai biến cố $A$ và $B$ xét ở trên, ta thấy $A$ kéo theo $B$ .

Hợp của hai biến cố, $C=A\cup B$ , là biến cố xảy ra khi và chỉ khi biến cố $A$ hoặc biến cố $B$ xảy ra. Nói cách khác, biến cố $C=A\cup B$ là tập hợp gồm các kết quả thuộc $A$ hoặc thuộc $B$ .

Giao của hai biến cố, $C=A\cap B$ (hoặc $C=AB$ ), là biến cố xảy ra khi và chỉ khi cả hai biến cố $A$ và $B$ đồng thời xảy ra. Nói cách khác, biến cố $C=A\cap B$ là tập hợp gồm các kết quả thuộc $A$ và thuộc $B$ .

Hiệu của hai biến cố, $C=A\backslash B$ , là biến cố xảy ra khi và chỉ khi $A$ xảy ra và $B$ không xảy ra. Nói cách khác, biến cố $C=A\backslash B$ là tập hợp gồm các kết quả thuộc $A$ nhưng không thuộc $B$ .

Phần bù của một biến cố $A$ , ký hiệu là $\overline{A}$ , là biến cố xảy ra khi và chỉ khi biến cố $A$ không xảy ra. Nói cách khác, $\overline{A}=\Omega\backslash A$ . $\overline{A}$ được gọi là biến cố đối kháng của biến cố $A$ . Như vậy, $\overline{A}$ là biến cố chứa tất cả những phần tử của không gian mẫu mà không thuộc $A$ .

Nếu $A\cap B=\emptyset$ , thì ta nói $A$ và $B$ xung khắc hay rời nhau. Rõ ràng là $A$ và $\overline{A}$ là hai biến cố xung khắc.

Trong Ví dụ 1.3.3, nếu $A$ là biến cố người đưa thư dừng ở đèn giao thông thứ nhất và $B$ là biến cố người đưa thư dừng ở cột đèn thứ hai, thì

$A=\{sss,\ ssc,\ scs,\ scc\},$

$B=\{sss,\ ssc,\ css,\ csc\}.$

$A\cup$ B là biến cố người đưa thư dừng ở đèn giao thông thứ nhất
hoặc đèn giao thông thứ hai:

$A\cup B=\{sss,\ ssc,\ scs,\ scc,\ css,\ csc\}.$

$A\cap$ B là biến cố người đưa thư dừng ở cả hai đèn giao thông thứ
nhất và đèn giao thông thứ hai:

$A\cup B=\{sss,\ ssc\}.$

$\overline{A}$ là biến cố người đưa thư không dừng ở đèn giao thông
thứ nhất:

$\overline{A}=\{ccc,\ ccs,\ csc,\ css\}.$

Nếu $C$ là biến cố người đưa thư không dừng ở đèn giao thông nào,
thì $C=\{ccc\}$ . Trong trường hợp này $A$ và $C$ rời nhau, $B$ và
$C$ rời nhau: $A\cap C=\emptyset$ , $B\cap C=\emptyset$ .

Sau đây ta liệt kê một số tính chất của các phép toán đối với tập hợp.

Tính giao hoán:

$A\cup B = B\cup A,$

$A\cap B = B\cap A.$

Tính kết hợp:

$(A\cup B)\cup C = A\cup (B\cup C),$

$(A\cap B)\cap C = A\cap (B\cap C).$

Tính phân phối:

$(A\cup B)\cap C = (A\cap C)\cup (B\cap C),$

$(A\cap B)\cup C = (A\cup C)\cap (B\cup C).$

Công thức De Morgan:

$\overline{A\cup B}=\overline{A}\cap \overline{B},$

$\overline{A\cap B}=\overline{A}\cup \overline{B}.$

Các phép toán hợp, giao, phần bù,… rất dễ hình dung nếu chúng ta vẽ sơ đồ Venn, một công cụ rất đơn giản và hiệu quả.

Posted in Thống kê toán học và xử lý số liệu | Leave a comment

1.2. Phép đếm

Posted on February 8, 2015 by lvthanh07

Trong Bài 1.1, ta đã trình bày một ví dụ về cách định nghĩa xác suất theo quan điểm cổ điển của Fermat và Pascal. Khi một phép thử ngẫu nhiên có $n$ kết quả đồng khả năng (equally probable outcomes), trong đó có $m$ kết quả thuận lợi cho sự kiện $A$ , thì xác suất của biến cố $A$ được định nghĩa

$P(A)=\dfrac{m}{n}.$

Do đó chúng ta thường phải đếm số kết quả có thể của một phép thử ngẫu nhiên, số phần tử thuận lợi cho một sự kiện $A$ nào đó. Trong mục này, chúng ta trình bày những kiến thức cơ bản về giải tích tổ hợp để phục vụ cho việc này.

1.2.1. Quy tắc nhân

Quy tắc nhân là một trong những nguyên lý cơ bản nhất của giải tích tổ hợp, có thể phát biểu như sau.

Định lý 1.2.1. Một hoạt động gồm hai bước thực hiện, trong đó có $m$ cách thực hiện bước thứ nhất và $n$ cách thực hiện bước thứ hai. Khi đó có $mn$ cách thực hiện hoạt động đó.

Ví dụ 1.2.2. Một lớp học có $36$ sinh viên nam và $42$ sinh viên nữ. Giảng
viên cần chọn $1$ nam và $1$ nữ đi tham gia tình nguyện hè. Khi đó giảng viên có $36\times 42=1512$ cách chọn.

Ví dụ 1.2.3. Một thương hiệu kem hộp có các loại như sau: miệng hộp có $2$ kiểu tròn hoặc vuông, kem có $4$ màu hoặc hồng, hoặc trắng, hoặc tím nhạt, hoặc cốm, và có $3$ hương vị là hoặc vị dừa, hoặc vị chocolate, hoặc vị dâu. Như vậy, có tất cả $2\times 4 \times 3=24$ loại kem của thương hiệu đó.

Ví dụ 1.2.4. Một từ hệ nhị phân $8$ -bit gồm $8$ ký tự, mỗi ký tự là số $0$ hoặc số $1$ . Hỏi có bao nhiêu từ khác nhau như vậy?

Ta thấy rằng ký tự thứ nhất (bit thứ nhất) có $2$ cách chọn, bit thứ hai có $2$ cách chọn, và cứ tiếp tục như thế cho đến bit thứ tám. Như vậy, có tất cả $2\times 2 \times\dots \times 2=2^8=256$

Ví dụ 1.2.5. Một phân tử DNA là một dãy gồm bốn dạng nucleotides, ký hiệu bởi $A$ , $G$ , $C$ và $T$ . Phân tử có thê là một dãy dài hàng triệu đơn vị và do đó có thể được mã hóa cho một lượng khổng lồ thông tin. Ví dụ một phân tử dài một triệu đơn vị ( $10^6$ ), khi đó sẽ có $4^{10^6}$ các dãy khác nhau. Con số khổng lồ này chứa gần một triệu chữ số.

1.2.2. Hoán vị và tổ hợp

Một hoán vị (permutation) của một tập hợp là một cách sắp xếp thứ tự các phần tử của tập hợp đó. Cho tập $S$ có $n$ phần tử. Để biết tất cả số hoán vị của $S$ , ta áp dụng quy tắc nhân bằng cách lập luận như sau: Phần tử thứ nhất có $n$ cách chọn, phần tử thứ hai có $n-1$ cách chọn, phần tử thứ ba có $n-2$ cách chọn, …, và phần tử cuối cùng có $1$ cách chọn. Như vậy, số các hoán vị của tập $S$ là

$P_n=n(n-1)(n-2)\dots 1=n!.$

Từ tập $S$ gồm $n$ phần tử, chúng ta lấy ra $k$ phần tử và gọi $k$ phần tử này là một mẫu cỡ $k$ .

Việc lấy mẫu có thể là lấy mẫu có hoàn lại (sampling with relacement), hoặc lấy mẫu không hoàn lại (sampling without replacement), lấy mẫu có tính thứ tự (order matters) hoặc lấy mẫu không tính đến thứ tự (order does not matter).

Nếu có kể đến thứ tự, ta hình dung tập $S$ là một rổ bóng có đánh số từ $1$ đến $n$ . Lấy mẫu có hoàn lại là ta chọn một quả bóng từ rổ, sau khi ghi số thì trả lại rổ và lấy quả thứ hai, và cứ tiếp tục như vậy cho đến quả bóng thứ $k$ . Như vậy, quả bóng thứ nhất có $n$ cách chọn, quả bóng thứ hai có $n$ cách chọn, …, quả bóng thứ $k$ có $n$ cách chọn. Theo quy tắc nhân, có tất cả $n^k$ cách lấy mẫu có thứ tự và có hoàn lại. Lấy mẫu không hoàn lại là ta chọn một quả bóng từ rổ, sau khi lấy số xong thì không trả lại rổ mà tiếp tục lấy quả thứ hai, và tiếp tục như vậy cho đến quả bóng thứ $k$ . Như vậy, quả bóng thứ nhất có $n$ cách chọn, quả bóng thứ hai có $n-1$ cách chọn, …, quả bóng thứ $k$ có $n-k+1$ cách chọn. Theo quy tắc nhân, có tất cả

$n(n-1)...(n-k+1)=\frac{n!}{(n-k)!}$

cách lấy mẫu có thứ tự và không hoàn lại. Như vậy, ta đã chứng minh định lý sau đây.

Định lý 1.2.6. Từ một tập $S$ gồm $n$ phần tử, số cách lấy mẫu cỡ $k$ có thứ tự và có hoàn lại là $n^k$ , số cách lấy mẫu cỡ $k$ có thứ tự và không hoàn lại là $n!/(n-k)!$ .

Ta thường ký hiệu

$P_{n}^k=\dfrac{n!}{(n-k)!}.$

Nếu $k=n$ thì $P_{n}^n=n!$ . (Số cách lấy mẫu cỡ $n$ có thứ tự từ một tập gồm $n$ phần tử chính là số các hoán vị của tập hợp đó.)

Bây giờ ta xét số cách lấy mẫu không tính đến thứ tự. Cụ thể, nếu chọn một mẫu cỡ $k$ từ một tập $S$ gồm $n$ phần tử, thì có bao nhiêu các mẫu khác nhau? Trước hết, chúng ta xét việc lấy mẫu không hoàn lại. Theo quy tắc nhân, số mẫu có tính thứ tự ( $P_{n}^k$ ) sẽ bằng số mẫu không tính thứ tự nhân với số cách thay đổi thứ tự các phần tử trong mẫu. Vì một mẫu cỡ $k$ sẽ có $k!$ cách thay đổi thứ tự các
phần tử trong mẫu, nên số mẫu không tính thứ tự là

$\dfrac{P_{n}^k}{k!}=\dfrac{n!}{k!(n-k)!}.$

Nếu chúng ta ký hiệu số này là $C_{n}^k$ , thì ta đã chứng minh định lý sau đây.

Định lý 1.2.7. Từ một tập $S$ gồm $n$ phần tử, số cách lấy mẫu cỡ $k$ không tính thứ tự và không hoàn lại là $C_{n}^{k}$ .

Bây giờ ta sẽ xét một số ví dụ. Trong các ví dụ sau đây, các đẳng thức có thể được chứng minh dễ dàng. Tuy nhiên, ta sẽ chứng minh bằng cách phân tích ý nghĩa tổ hợp của từng ví dụ. Cách chứng minh này không những hiểu sâu hơn về mặt ý nghĩa của các đẳng thức, mà còn giúp chúng ta nhớ được các đẳng thức này một cách dễ dàng.

Ví dụ 1.2.8. Chứng minh rằng

$k C_{n}^{k}=n C_{n-1}^{k-1}.$

Đối với ví dụ này, ta xét bài toán chọn $k$ người trong một lớp học gồm $n$ người để thành lập một đội tình nguyện, sau đó chọn ra một người làm đội trưởng. Khi đó, vế trái chính là số cách chọn theo thứ tự nêu ở bài toán. Bây giờ nếu ta chọn một người làm đội trưởng trước, sau đó chọn $k-1$ tình nguyện viên trong $n-1$ người còn lại, thì số các cách chọn chính là vế phải.

Đẳng thức sau đây được phát hiện bởi nhà toán học Vandemonde.

Ví dụ 1.2.9. [Đẳng thức Vandemonde] Chứng minh rằng

$C_{m+n}^{k}=\sum_{j=0}^k C_{m}^{j}C_{n}^{k-j}.$

Tương tự Ví dụ 1.2.8, ta xét bài toán chọn $k$ người trong một lớp học gồm $m+n$ người. Khi đó, có $C_{m+n}^{k}$ cách chọn. Bây giờ, ta chia nhóm $m+n$ người thành hai nhóm, nhóm thứ nhất gồm $m$ người, nhóm thứ hai gồm $n$ người. Số cách chọn $k$ người trong hai nhóm trên chính là chọn $j$ người ở nhóm thứ nhất và chọn $k-j$ người ở nhóm thứ hai, trong đó $j=0,1,\dots, k$ . Như vậy, có tất cả $\sum_{j=0}^k C_{m}^{j}C_{n}^{k-j}$ cách chọn, và do đó cả đẳng thức được chứng minh.

Bài tập: Chứng minh đẳng thức Pascal sau bằng cách phân tích ý nghĩa của số $C_{n}^{k}$ như trong các ví dụ trên.

$C_{n}^{k}=C_{n-1}^{k-1}+C_{n-1}^{k}.$

Posted in Thống kê toán học và xử lý số liệu | Leave a comment

1.1. Fermat và Pascal: Những người đặt nền móng cho lý thuyết xác suất

Posted on February 2, 2015 by lvthanh07

Blaise Pascal (1623-1662) và Pierre de Fermat (1601-1665) là hai nhà toán học đặt nền tảng cho lý thuyết xác suất hiện đại. Năm 1654, qua trao đổi thư từ, Blaise Pascal và Pierre de Fermat đã giải quyết một bài toán thú vị của lý thuyết trò chơi (Problem of Points) mà ta có thể tóm tắt (link Tiếng Anh) như sau: Vào một ngày nọ, Pascal và Fermat ngồi nói chuyện với nhau trong một quán cà phê ở Paris. Sau một ngày thảo luận căng thẳng về những vấn đề toán học hóc búa, họ quyết định mỗi người sẽ bỏ ra $50$ Francs để chơi trò chơi tung đồng xu và lấy tiền đi ăn tối. Nếu mặt ngửa xuất hiện, Fermat được $1$ điểm, nếu mặt sấp xuất hiện, Pascal sẽ được một điểm. Ai nhận được $10$ điểm thì trò chơi sẽ kết thúc và người đó sẽ nhận toàn bộ $100$ Francs. Nhưng một điều bất ngờ đã xảy ra. Khi Fermat được $8$ điểm và Pascal được $7$ điểm thì Fermat nhận được tin là có một người bạn của anh ấy ốm nặng. Người báo tin đồng ý sẽ đưa Fermat cùng về Toulouse nhưng với điều kiện Fermat phải về ngay lập tức. Khi Fermat trở lại Toulouse thì một vấn đề nảy sinh: Làm thế nào để chia số tiền $100$ Francs?

Và trong một bức thư gửi Pascal sau này, Fermat đã nêu cách giải quyết như sau:

Tôi (Fermat) chỉ cần $2$ điểm nữa là thắng cuộc chơi, trong khi đó bạn (Pascal) cần thêm $3$ điểm, nên ta cần tung đồng xu tối đa thêm bốn lần nữa thì cuộc chơi sẽ kết thúc. Trong bốn lần tung này, nếu bạn không nhận được đủ $3$ điểm, đồng nghĩa với việc tôi sẽ có thêm $2$ điểm và sẽ dành chiến thắng. Nếu ký hiệu mặt ngửa bởi $N$ và mặt sấp bởi $S$ , thì có tất cả $16$ kết quả có thể xảy ra sau đây:

$NNNN$

$NNNS\ NNSN\ NSNN\ SNNN$

$SSNN\ NNSS\ SNNS\ NSSN\ SNSN\ NSNS$

$SSSN\ SSNS\ SNSS\ NSSS$

$SSSS$ .

Vì trong $16$ kết quả trên, có $11$ kết quả thuận lợi cho tôi. Do đó, $100$ Francs cần được chia theo tỉ lệ $11:5$ nghiêng về phía tôi, nghĩa là, tôi sẽ nhận $(11/16)*100 =68.75$ Francs, và bạn sẽ nhận $31.25$ Francs.

Pascal rất hài lòng với cách giải quyết của Fermat. Tuy nhiên, Pascal nhận thấy phương pháp liệt kê tất cả các trường hợp có thể xảy ra của Fermat tương đối tẻ nhạt đối với bài toán tổng quát. Pascal đã lý luận như sau: Trong lời giải của Fermat, ta nhận thấy nếu có $2$ hoặc hơn $2$ mặt ngửa xuất hiện thì Fermat sẽ thắng cuộc. Số các kết quả có hai mặt ngửa khi tung đồng xu $4$ lần là $C_{4}^{2}$ . Như vậy, số các trường hợp thuận lợi cho Fermat là

$C_{4}^{4}+C_{4}^{3}+C_{4}^{2}=C_{4}^{0}+C_{4}^{1}+C_{4}^{2}$ .

Đây chính là $3$ số hạng đầu tiên trong dòng thứ năm trong tam giác Pascal:

$C_{0}^{0}$

$C_{1}^{0}\ C_{1}^{1}$

$C_{2}^{0}\ C_{2}^{1}\ C_{2}^{2}$

$C_{3}^{0}\ C_{3}^{1}\ C_{3}^{2}\ C_{3}^{3}$

$C_{4}^{0}\ C_{4}^{1}\ C_{4}^{2}\ C_{4}^{3}\ C_{4}^{4}$

Đối với bài toán tổng quát, khi người chơi thứ nhất và người thứ hai lần lượt cần $k$ và $l$ điểm nữa để dành phần thắng, thì số tiền sẽ chia cho người thứ nhất theo tỉ lệ $r=x/y$ , trong đó $latex $ là tổng số $l$ số hạng đầu tiên của dòng thứ $(k+l)$ trong tam giác Pascal, còn $y$ là tổng của tất cả các số hạng trong dòng đó:

$r=\dfrac{C_{k+l-1}^{0}+C_{k+l-1}^{1}+\dots+C_{k+l-1}^{l}} {2^{k+l-1}}$ .

Trở lại trò chơi của Fermat và Pascal $(k=2,l=3)$ , số tiền chia cho Fermat theo tỉ lệ

$\dfrac{C_{4}^{0}+C_{4}^{1}+C_{4}^{2}}{2^4}.$

Cho dù lý luận trên của Fermat và Pascal tương đối đơn giản đối với chúng ta ngày nay, nhưng nó là một cuộc cách mạng vào những năm giữa thế kỷ 17. Đó chính là cách định nghĩa xác suất theo quan điểm cổ điển. Khi một phép thử ngẫu nhiên có $n$ kết quả đồng khả năng (equally probable outcomes), trong đó có $m$ kết quả thuận lợi cho sự kiện $A$ , thì xác suất của biến cố $A$ được định nghĩa

$P(A)=\dfrac{m}{n}.$

Trong bài toán chia điểm của Fermat và Pascal, có $16$ kết quả đồng khả năng có thể xảy ra khi tung một đồng xu cân đối $4$ lần, trong đó có $11$ kết quả thuận lợi cho sự kiện $A$ (sự kiện Fermat thắng cuộc). Vậy

$P(A)=\dfrac{11}{16}.$