Vào ngày đầu tiên của học kỳ mới, trong một lớp có khoảng ba mươi học sinh, giáo viên chủ nhiệm hỏi: “Trong lớp này có ai trùng ngày sinh không?” Vì 1 năm có tới 365 ngày, chúng ta dễ nghĩ rằng khoảng ba mươi người thì khó có thể trùng ngày sinh. Nhưng khi tính toán thực tế, xác suất có hai người trùng ngày sinh lên tới khoảng 70%.
Hiện tượng trực giác và kết quả tính toán chênh lệch lớn như vậy được gọi là “nghịch lý ngày sinh (Birthday Paradox)”. Nói đơn giản, nghịch lý ngày sinh chỉ sự thật rằng “chỉ cần vài chục người tụ họp, xác suất có người trùng ngày sinh đã cao hơn chúng ta nghĩ rất nhiều”. Tuy không có mâu thuẫn về mặt logic, hiện tượng này vẫn mang tên nghịch lý vì khi mới nghe, chúng ta có cảm giác nó không đúng.
Trong tài liệu này, chúng ta sẽ lần lượt tìm hiểu nghịch lý ngày sinh là gì, nguyên lý tính xác suất, vì sao chúng ta lại dễ nhầm lẫn như vậy, và nguyên lý này được ứng dụng thế nào trong thực tế, chẳng hạn như bảo mật thông tin.
Nguyên lý và ứng dụng của nghịch lý ngày sinh
Xác suất trở thành năm mươi năm mươi khi có 23 người
Nghịch lý ngày sinh thường được tính toán dựa trên một số giả định. Mục đích là để đơn giản hóa phép tính.
- Độ dài của 1 năm (Days in a Year): Coi 1 năm có 365 ngày và bỏ qua ngày 29 tháng 2 xuất hiện mỗi 4 năm một lần.
- Phân phối đều (Uniform Distribution): Coi khả năng được sinh ra vào mọi ngày là như nhau.
- Tính độc lập (Independence): Coi ngày sinh của một người không ảnh hưởng đến ngày sinh của người khác và giả định không có người sinh đôi.
Trong những điều kiện này, khi có 10 người, xác suất có ít nhất một cặp trùng ngày sinh chỉ khoảng 11.7%, nên vẫn là chuyện hiếm gặp. Nhưng khi có 23 người, xác suất đạt khoảng 50.7%, lần đầu vượt quá một nửa; với 30 người là khoảng 70.6%, với 50 người là khoảng 97%, và với 70 người thì lên tới khoảng 99.9%. Như vậy, số người chỉ tăng dần từng chút nhưng xác suất lại tăng vọt.
Ngược lại, để chắc chắn có người trùng ngày sinh thì cần 366 người. Vì chỉ có 365 ngày nên người thứ 366 buộc phải trùng ngày sinh với ai đó. Thế nhưng, chỉ cần 23 người tụ họp, chưa bằng 1 phần 15 của 365 ngày trong 1 năm, xác suất đã vượt quá một nửa; chính điều này khiến hiện tượng có vẻ như một nghịch lý.
Trên thực tế, có nhiều trẻ được sinh ra hơn vào một số mùa hoặc một số ngày trong tuần, nên ngày sinh không phân bố đều. Sự không đồng đều này còn khiến xác suất trùng ngày sinh cao hơn một chút, nhưng chênh lệch không lớn, nên ngay cả khi xét dữ liệu sinh thực tế, ngưỡng vượt quá một nửa vẫn là 23 người.
Hai chìa khóa để tính xác suất
Có hai chìa khóa để hiểu nghịch lý ngày sinh.
(1) Đếm trường hợp ngược lại trước
Nếu tính trực tiếp “xác suất có người trùng ngày sinh” thì có quá nhiều trường hợp. Vì vậy, chúng ta tính “xác suất mọi người đều khác ngày sinh” trước rồi lấy 1 trừ đi kết quả đó. Xác suất người thứ hai khác ngày sinh với người đầu tiên là 364/365, còn xác suất người thứ ba khác ngày sinh với cả hai người trước là 363/365. Tiếp tục nhân như vậy đến người thứ 23, xác suất mọi người đều khác ngày sinh là khoảng 49.3%, và khoảng 50.7% còn lại chính là xác suất có người trùng ngày sinh.
(2) Đếm số cặp thay vì số người
Khi 23 người tụ họp, số cách ghép từng cặp hai người là 23×22÷2, tức 253 cách. Xác suất một cặp trùng ngày sinh chỉ là 1 phần 365, tuy nhỏ nhưng khi có tới 253 cơ hội, khả năng có một lần trùng khớp trong số đó sẽ tăng lên. Khi số người tăng, số cặp tăng nhanh hơn nhiều. Nếu số người tăng gấp 2 lần thì số cặp tăng khoảng 4 lần, nên cơ hội trùng ngày sinh cũng tăng nhanh tương ứng.
Nếu hình dung từng người lần lượt bước vào một căn phòng, trung bình cần khoảng 25 người bước vào thì mới xuất hiện cặp trùng ngày sinh đầu tiên. Đây cũng là một con số rất nhỏ so với 365.
Vì sao trực giác bỏ sót xác suất
Hiện tượng này gây ngạc nhiên vì chúng ta hiểu câu hỏi theo một cách khác. Nhiều người nghĩ đến “xác suất có ai đó trùng ngày sinh với tôi”. Trong nhóm 23 người tính cả tôi, xác suất này chỉ khoảng 6%; để vượt quá 50%, cần 254 người tính cả tôi, tức 253 người khác. Nhưng điều nghịch lý ngày sinh đặt ra là xác suất “hai người bất kỳ” trong nhóm có cả tôi trùng ngày sinh.
Cũng có ví dụ thực tế. Tại World Cup Brazil năm 2014, tất cả 32 quốc gia đều nộp danh sách gồm 23 cầu thủ mỗi đội. Theo phân tích của BBC, Anh, một nửa số đội, tức 16 đội, có cầu thủ trùng ngày sinh, và 5 đội, trong đó có Hàn Quốc, có tới hai cặp như vậy mỗi đội. Kết quả này khớp một cách đáng ngạc nhiên với phép tính rằng 23 người thì xác suất là năm mươi năm mươi.
Bài toán này được cho là do nhà toán học người Anh Harold Davenport nghĩ ra đầu tiên vào thập niên 1920, và được Richard von Mises công bố lần đầu dưới dạng bài báo khoa học vào năm 1939.
Nghịch lý ngày sinh ẩn trong bảo mật thông tin
Nghịch lý ngày sinh còn có những ứng dụng quan trọng hơn bên ngoài lớp học. Một ví dụ tiêu biểu là hàm băm (Hash Function), biến dữ liệu dù dài đến đâu thành một giá trị ngắn có độ dài cố định.
- Va chạm băm (Hash Collision): Trường hợp hai dữ liệu khác nhau có cùng giá trị băm, tương tự tình huống hai người trùng ngày sinh.
- Tấn công ngày sinh (Birthday Attack): Cuộc tấn công sử dụng nguyên lý của nghịch lý ngày sinh để tìm va chạm. Với một hàm băm có kết quả dài n bit, chỉ cần thử khoảng 2 lũy thừa (n÷2) lần, thay vì 2 lũy thừa n lần, xác suất tìm được va chạm đã vào khoảng một nửa.
- Thiết kế bảo mật (Security Design): Vì vậy, các hàm băm cần có khả năng chống va chạm được thiết kế với độ dài kết quả đủ lớn để phòng ngừa kiểu tấn công này.
Ngay cả với bảng băm dùng để tổ chức dữ liệu, khi số mục cần lưu tăng lên, người thiết kế cũng xem một vài va chạm là điều không thể tránh khỏi và tích hợp biện pháp xử lý ngay từ đầu.
Nghịch lý ngày sinh cho thấy trực giác của chúng ta quen suy nghĩ lấy “một mình tôi” làm mốc và khó nhận ra những cơ hội do vô số cặp tạo ra. Những chuyện tưởng như ngẫu nhiên, khi tính toán kỹ, có thể xảy ra thường xuyên hơn chúng ta nghĩ.
Trước một sự trùng hợp đáng ngạc nhiên, hãy đếm lại số trường hợp thêm một lần; đó chính là bước đầu tiên để hiểu đúng xác suất.
