solution

Lấy mẫu loại bỏ (rejection sampling) là kỹ thuật Monte Carlo để lấy mẫu từ một phân phối mục tiêu có mật độ $f$ khi ta chỉ biết cách lấy mẫu từ một phân phối đề xuất $g$ đơn giản hơn, với điều kiện tồn tại hằng số $M$ sao cho $f(x) \le M\cdot g(x)$ với mọi $x$.

Xét phân phối mục tiêu có mật độ tam giác $f(x) = 2x$ trên $[0,1]$, phân phối đề xuất $g$ là phân phối đều trên $[0,1]$ (mật độ $g(x)=1$), và $M = 2$ (vì $\max f = 2$). Với một điểm đề xuất $u \sim g$ và một số ngẫu nhiên quyết định $v \sim \text{Uniform}(0,1)$, điểm $u$ được CHẤP NHẬN nếu:

$v \le \dfrac{f(u)}{M\cdot g(u)} = u$

Cho sẵn $n$ cặp $(u_i, v_i)$ đã sinh sẵn (không cần sinh ngẫu nhiên). Hãy tính:

• Số mẫu được chấp nhận $k$
• Tỉ lệ chấp nhận $k/n$ (Monte Carlo ước lượng xác suất chấp nhận của thuật toán)
• Giá trị trung bình của các $u_i$ được chấp nhận (ước lượng kỳ vọng của phân phối mục tiêu, $E[X]=2/3$ về mặt lý thuyết)

Quy ước: nếu $n=0$ hoặc không có mẫu nào được chấp nhận, tỉ lệ chấp nhận và/hoặc giá trị trung bình quy định bằng $0$.

Ví dụ: $n=1$, cặp (0.2, 0.9): vì $0.9 > 0.2$ nên bị từ chối. Output: 0 0.000000 0.000000.