KHI NÀO KIỂU XÀO BÀI OVERHAND QUÊN ĐƯỢC THỨ TỰ CỖ BÀI?

Xào bài là phiên bản cụ thể của một câu hỏi cơ bản trong xác suất: một quá trình ngẫu nhiên cần bao lâu để quên điểm xuất phát của nó? Một cỗ bài vừa mở hộp thì nằm theo thứ tự. Mỗi lần xào lại làm nó lộn xộn thêm một chút, cho tới khi không còn phát hiện được dấu vết nào của thứ tự ban đầu.

Các nhà toán học phân biệt hai cấp độ trả lời. Thời gian trộn (mixing time) cho biết bậc độ lớn. Một điểm cắt (cutoff) nói lên nhiều hơn hẳn: quanh một thời điểm chính xác, cỗ bài chuyển từ “rõ ràng chưa trộn” sang “trộn hoàn toàn” gần như ngay lập tức. Xào ít hơn thế một chút thì vẫn còn nhận ra được; xào lâu hơn một chút thì không.

Xào bài dưới con mắt nhà toán học

Trong kiểu xào bài overhand (overhand shuffle), bạn cầm cỗ bài ở một tay và thả từng tập bài nhỏ sang tay kia. Bài báo mô hình hóa nó như sau: mỗi khe trong số n − 1 khe giữa các lá bài kề nhau bị cắt một cách độc lập với xác suất p, và thứ tự của các tập bài tạo thành bị đảo ngược. Một lượt đi hết cỗ bài được tính là một lần xào.

Theo bài báo, các công trình trước đã xác định được bậc độ lớn. Pemantle đã kẹp thời gian trộn giữa n² và n² log n; sau đó Jonasson chỉ ra rằng n² log n là bậc đúng. Nhưng hằng số chính xác, và liệu có xảy ra một điểm cắt sắc nét hay không, vẫn còn bỏ ngỏ: Diaconis và Pal đã đưa điểm cắt của kiểu xào overhand vào danh sách các bài toán mở năm 2022.

Kết quả

Yunjiang Jiang chứng minh rằng điểm cắt tồn tại và xác định vị trí của nó.

Định lý. Với xác suất cắt p cố định, kiểu xào bài overhand trộn đều, ở bậc nhất, sau

p² / (2(1 − p)π²) × n² log n

lần xào. Ngay trước đó một chút, cỗ bài còn xa mới ngẫu nhiên; ngay sau đó một chút, nó gần như ngẫu nhiên.

Với p = 1/2 — trung bình cắt ở một nửa số khe — công thức trở thành n² log n / (4π²).

Chứng minh vận hành ra sao

Chứng minh có ba phần độc lập.

1. Cận dưới theo dõi một lá bài duy nhất. Vị trí của nó biến đổi theo một cách gọn gàng đáng kinh ngạc: những mẫu hình dạng cosin chính xác tắt dần với tốc độ đã biết, ngay cả với một cỗ bài hữu hạn. Cộng lại trên toàn cỗ bài, chúng giữ một dấu vết phát hiện được của thứ tự ban đầu cho tới thời điểm được dự đoán.
2. Cận trên so sánh hai cỗ bài chỉ khác nhau ở việc hoán đổi hai lá. Khi được xào bằng cùng những nhát cắt ngẫu nhiên, sự khác biệt này hành xử như hai vị trí được đánh dấu lang thang trong cỗ bài cho tới khi chúng trở thành láng giềng và có thể hợp nhất. Tốc độ điều đó xảy ra khớp với cận dưới.
3. Một bất đẳng thức tĩnh về hoán vị, không liên quan gì đến xào bài, biến phép so sánh này thành một khẳng định về toàn bộ cỗ bài. Đây là phần kỹ thuật nhất của bài báo, được xây dựng bằng đệ quy trên những bảng đếm cách các lá bài phân bố giữa các khối.

Bài báo cũng chứng minh một điểm cắt cho một cách đo độ hỗn loạn khác, entropy tương đối, nhưng không xác định vị trí chính xác của nó.

Công thức nói gì về một cỗ bài thật

Thay một cỗ bài 52 lá vào công thức với p = 1/2 sẽ được 52² × ln 52 / (4π²), khoảng 270 lần xào. Đây là phép tính của chính chúng tôi, không phải con số trong bài báo, và chỉ nên được hiểu như một chỉ dấu ước chừng: định lý mô tả hành vi của những cỗ bài rất lớn, và số hạng hiệu chỉnh chưa được định lượng. Để so sánh, bài báo trích dẫn quy mô (3/2) log₂ n do Bayer và Diaconis xác lập cho kiểu xào riffle — khoảng 8,6 với 52 lá bài, kèm cùng lưu ý ấy. Khoảng cách giữa n² log n và log n chính là điều khiến kiểu xào overhand chậm đến vậy.

Bậc nhất, những bàn tay lý tưởng hóa

Kết quả này ở bậc nhất: nó không cho biết độ rộng của khoảng chuyển tiếp hay hình dạng chính xác của nó. Xác suất cắt được giữ cố định, và các nhát cắt được giả định là độc lập, một sự lý tưởng hóa những bàn tay thật. Trong một chú thích, tác giả cho biết hệ thống AI GPT-6 Astra đã “được dùng để phát triển lập luận, kiểm tra tính toán và chuẩn bị phần trình bày”, và tác giả chịu trách nhiệm về nội dung toán học. Bài báo là một bản tiền ấn phẩm.