Lesson 48 — Thuật toán ngẫu nhiên
Ba minh hoạ tương tác: reservoir sampling (chọn mẫu đều từ stream), Fisher-Yates shuffle (xáo trộn đều), và Monte Carlo ước lượng π. Bấm chạy để thấy ngẫu nhiên hội tụ về kết quả "đều" như thế nào.
1 · Reservoir Sampling (Algorithm R)
Stream chảy qua từng phần tử. Reservoir giữ k mẫu; phần tử thứ i (1-indexed) được nhận với xác suất k/i, thay một slot ngẫu nhiên. Chạy nhiều lần để thấy mỗi phần tử được chọn với tần suất ~ k/n (đều).
Tần suất mỗi phần tử được chọn (sau "Chạy 2000 lần") — kỳ vọng đều ~ k/n:
2 · Fisher-Yates Shuffle
Đi từ cuối mảng: tại vị trí i, đổi chỗ với một vị trí ngẫu nhiên j ∈ [0, i] (bao gồm i). Mỗi hoán vị có xác suất đều 1/n!. Phần tử đã "khoá" (xanh) không di chuyển nữa.
⚠ Naive shuffle (swap với j ∈ [0, n-1] toàn dải) bị bias vì sinh nn đường đi không chia hết n! — một số hoán vị xuất hiện nhiều hơn. Fisher-Yates sinh đúng n! đường đi (song ánh) nên đều.
3 · Monte Carlo ước lượng π
Ném điểm ngẫu nhiên đều vào hình vuông cạnh 2. Tỉ lệ điểm rơi trong đường tròn bán kính 1 ≈ diện tích tròn / vuông = π/4. Suy ra π ≈ 4 · (trong / tổng). Sai số giảm ~ 1/√n.