Hai Loại Ngẫu Nhiên: Tại Sao π Nén Được Còn Nhiễu Thì Không

Đây là một câu đố trông như một mâu thuẫn: hai tệp, mỗi tệp dài một triệu chữ số, đều vượt qua mọi kiểm tra tính ngẫu nhiên thống kê và có biểu đồ tần suất giống hệt nhau. Thế nhưng một tệp có thể nén thành một chương trình nhỏ (các chữ số của π) và tệp kia thì không (nhiễu thuần túy). Câu trả lời cho thấy một sự phân chia cơ bản trong cách chúng ta nghĩ về khả năng nén.

Nén thống kê chạm tường

Công cụ tiêu chuẩn là entropy Shannon, đo lường mức độ bất ngờ trung bình của một ký hiệu dựa trên tần suất của nó. Đối với phân phối đều trên mười chữ số, entropy đạt cực đại khoảng 3,32 bit mỗi chữ số. Cả hai tệp đều đồng đều, vì vậy entropy nói rằng cả hai đều không nén được. Điều đó đúng với tệp nhiễu, nhưng sai với π — vì entropy chỉ nhìn vào tần suất, không nhìn vào cấu trúc. Nó bỏ qua trật tự.

Entropy là một thuộc tính của một nguồn, không phải của một chuỗi đơn lẻ. Khi bạn tính toán nó từ số đếm chữ số của một chuỗi, bạn đang giả vờ rằng các chữ số là các lần rút độc lập từ phân phối đó. Giả định đó loại bỏ bất kỳ mẫu nào kéo dài qua nhiều vị trí — chính xác là mẫu mà π có.

Độ phức tạp Kolmogorov nhìn thấy chương trình

Giải pháp thay thế là độ phức tạp Kolmogorov: độ dài của chương trình ngắn nhất xuất ra chuỗi. Một tỷ số không có độ phức tạp rất nhỏ; một chuỗi thực sự ngẫu nhiên có độ phức tạp xấp xỉ bằng độ dài của nó. Độ phức tạp của π là rất nhỏ — một chương trình ngắn có thể tạo ra nó. Tệp nhiễu có độ phức tạp bằng độ dài của nó, vì không có mô tả ngắn hơn.

Điều này giải quyết câu đố: hai tệp giống hệt nhau về mặt thống kê nhưng khác nhau về mặt thuật toán. Một tệp có quy tắc sinh ngắn; tệp kia thì không. Vấn đề là độ phức tạp Kolmogorov không thể tính toán được — bạn không bao giờ có thể chắc chắn rằng mình đã tìm thấy chương trình ngắn nhất. Bạn có thể xác nhận khả năng nén khi tìm thấy một chương trình ngắn, nhưng bạn không bao giờ có thể loại trừ nó.

Vậy hai loại ngẫu nhiên là: ngẫu nhiên thống kê (entropy cao, không thiên lệch tần suất) và ngẫu nhiên thuật toán (độ phức tạp Kolmogorov cao, không có chương trình sinh ngắn). Chúng đồng ý về nhiễu, nhưng bất đồng về π. Sự bất đồng đó là toàn bộ câu chuyện.