Reservoir sampling — mẫu ngẫu nhiên từ stream

TL;DR: Bài toán: bạn cần lấy ra một nhúm nhỏ, ví dụ 1000, phần tử ngẫu nhiên từ một dòng dữ liệu chảy mãi, nhưng không biết trước dòng đó dài bao nhiêu và không thể lưu cả dòng để bốc thăm. Mẹo của reservoir sampling: luôn giữ sẵn k "chỗ" trong tay; khi phần tử thứ i đi qua, cho nó một cơ hội nhỏ (giảm dần khi dòng dài ra) giành lấy một chỗ đang giữ, đổi chỗ thì ngẫu nhiên. Kết quả: dừng lúc nào cũng được, và mỗi phần tử đã thấy đều có cơ hội ngang nhau lọt vào nhúm cuối cùng, không thiên vị phần tử đến sớm hay đến muộn. Spark (khi ước lượng ranh giới chia phân vùng để sort) và PostgreSQL (khi ANALYZE lấy mẫu dòng để làm thống kê) đều dùng họ thuật toán này. Tên kỹ thuật của "k chỗ giữ trong tay" là reservoir.

Hệ thống monitoring của bạn nhận 10 triệu event mỗi giờ. Bạn cần lấy 1000 event đại diện để phân tích, nhưng không thể lưu tất cả. Lấy 1000 event đầu tiên? Sai, thiên vị về buổi sáng, bỏ qua spike buổi chiều. Lấy mỗi event thứ 10.000? Sai, bỏ qua burst ngắn giữa các mốc lấy mẫu. Bạn cần một mẫu mà mỗi event có cùng cơ hội được chọn, bất kể nó nằm chỗ nào trong dòng, gọi là mẫu đều xác suất (uniform random sample).

Reservoir sampling giải đúng bài này, chỉ tốn bộ nhớ đủ chứa k phần tử và không cần biết dòng dài bao nhiêu.

1. Trực giác: người gác cửa phát vé

Trước khi đụng công thức, hãy hình dung một cảnh quen. Bạn đứng ở cửa một sự kiện, dòng người đi qua liên tục, không ai biết tối nay sẽ có bao nhiêu người — có thể vài trăm, có thể vài nghìn. Nhiệm vụ: chọn ra ngẫu nhiên 1 người (hoặc k người) để tặng quà, sao cho ai đi qua cũng có cơ hội trúng ngang nhau. Bạn không thể bắt cả dòng người đứng lại xếp hàng để đếm rồi mới bốc thăm, dòng cứ chảy.

Mẹo của người gác cửa: luôn giữ một tấm vé trong tay. Người đầu tiên đi qua, bạn đưa vé cho họ. Người thứ i đi qua, bạn cho họ một cơ hội đúng bằng 1/i để giành lấy tấm vé đang giữ — nếu giành được, vé đổi sang tay người mới; nếu không, vé ở yên. Cơ hội này nhỏ dần khi dòng dài ra (người thứ 1000 chỉ có 1/1000 cơ hội). Dừng ở người thứ n bất kỳ, xác suất mỗi người đã qua đang cầm vé đều đúng 1/n (với k vé thì k/n).

Reservoir sampling là bản giữ k vé thay vì 1:

Điểm cốt lõi: cơ hội k/i nhỏ dần khi dòng dài ra, và nhịp giảm đó vừa khéo để cân bằng. Người đến sớm phải qua nhiều lần có nguy cơ bị thay, người đến muộn ít lần hơn nhưng cơ hội vào ban đầu cao hơn; hai phía triệt tiêu nhau thành cơ hội cuối cùng bằng nhau cho tất cả. Phần "vì sao bằng nhau" có chứng minh gọn ở mục 3.

1.1 Phát biểu bài toán

Nói lại cho chặt:

• Đầu vào: một dòng phần tử x_1, x_2, ..., x_n chảy vào lần lượt; độ dài n chưa biết trước (có thể vô tận).
• Đầu ra: một nhúm k phần tử, sao cho mỗi phần tử trong dòng có cơ hội đúng bằng k/n nằm trong nhúm cuối.
• Ràng buộc: chỉ được giữ đủ chỗ cho k phần tử — không lưu cả dòng (bộ nhớ O(k)).

Nếu biết n trước, bài này dễ: trộn ngẫu nhiên cả dòng (Fisher-Yates shuffle) rồi lấy k phần tử đầu — nhưng cách đó cần giữ cả dòng trong bộ nhớ (O(n)). Reservoir sampling bỏ được ràng buộc "phải biết n" và "phải lưu cả dòng" mà vẫn giữ tính công bằng.