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).

Reservoir:
Bấm "Bước tiếp" để xử lý từng phần tử của stream.

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.

Bấm "Swap tiếp" để xáo từng bước.

⚠ 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.

Thử: tăng số điểm ×100 — sai số giảm chỉ ~10 lần (tỉ lệ 1/√n): mỗi chữ số chính xác thêm phải trả giá ×100 điểm.

Tổng: 0 · Trong tròn: 0 · π ≈ —