Phương pháp Monte Carlo là một phương pháp số để giải các bài toán thông qua việc sử dụng các phép sinh số ngẫu nhiên và thống kê. Phương pháp này thường được áp dụng trong nhiều lĩnh vực khác nhau như vật lý, tài chính, thống kê, và máy học.

 

Trong Monte Carlo, phương pháp chấp nhận-loại bỏ (Acceptance-Rejection Method) là một kỹ thuật quan trọng để tạo ra các mẫu từ một phân phối xác suất đã biết. Kỹ thuật này thực hiện bằng cách sinh ra các mẫu từ một phân phối dự phòng dễ sinh (thường là một phân phối đều) và sau đó chấp nhận hoặc loại bỏ chúng dựa trên một quy tắc xác định.

 

Dưới đây là một phác họa cơ bản của phương pháp chấp nhận-loại bỏ:

 

1. Bước 1: Sinh một mẫu từ phân phối dễ sinh: Bắt đầu bằng cách sinh ra một mẫu từ một phân phối dễ sinh, thường là phân phối đều trên một khoảng cụ thể.

2. Bước 2: Chấp nhận hoặc loại bỏ mẫu: Với mỗi mẫu được sinh ra từ bước trước, áp dụng một quy tắc để xác định xem mẫu có được chấp nhận hay không dựa trên phân phối xác suất mong muốn.

3. Bước 3: Lặp lại quá trình: Lặp lại quá trình bước 1 và bước 2 đủ lần để thu thập số lượng mẫu cần thiết.

Phương pháp chấp nhận-loại bỏ thường được sử dụng khi không thể trực tiếp sinh ra các mẫu từ phân phối xác suất mong muốn hoặc khi việc tính toán trực tiếp xác suất sinh ra mẫu là không hiệu quả.

 

Giả sử bạn muốn sinh mẫu từ một phân phối xác suất mong muốn với hàm mật độ xác suất f(x), và bạn sử dụng phương pháp chấp nhận-loại bỏ với phân phối dễ sinh, thường là phân phối đều trên một khoảng cụ thể [a, b].

 

Bước 1: Sinh ra một mẫu từ phân phối đều trên khoảng [a, b].

Bước 2: Chấp nhận hoặc loại bỏ mẫu dựa trên quy tắc sau: Một mẫu từ phân phối đều, ký hiệu là U, sẽ được chấp nhận nếu: U≤M/f(x)​

Ở đây, x là giá trị của mẫu từ phân phối đều, và M là một hằng số sao cho M ≥ maxf(x) trên khoảng [a, b].

 

Nếu điều kiện trên được thỏa mãn, mẫu từ phân phối đều sẽ được chấp nhận là một mẫu từ phân phối xác suất mong muốn. Nếu không, mẫu sẽ bị loại bỏ và bạn cần sinh ra một mẫu mới từ phân phối đều và kiểm tra lại điều kiện.

 

Trong công thức này, M thường được chọn sao cho nó là một hằng số dễ tính toán và lớn hơn giá trị lớn nhất của hàm mật độ xác suất f(x) trên khoảng [a, b], nhưng càng gần giá trị lớn nhất của f(x) càng tốt để giảm số lần loại bỏ mẫu.