✨Định lý con khỉ vô hạn

Giả sử cho một con khỉ cái gõ liên tục trên một máy đánh chữ hay máy tính, sau một thời gian đủ dài, trong văn bản con khỉ gõ ra ta có thể tìm thấy tất cả các kịch bản của [[William Shakespeare|Shakespeare. Trong hình là một con tinh tinh và máy đánh chữ.]] Định lý con khỉ vô hạn nói rằng nếu cho một con khỉ gõ lên một bàn phím trong một thời gian vô hạn, một phần văn bản khỉ gõ ra gần như chắc chắn sẽ có nghĩa, ví dụ tất cả các tác phẩm của William Shakespeare. Trong bài này, "gần như chắc chắn" là thuật ngữ toán học có nghĩa rõ ràng, và "con khỉ" là một ẩn dụ về một thiết bị trừu tượng có thể tạo ra các chuỗi ngẫu nhiên ký tự và ký hiệu dài vô tận. Xác suất con khỉ gõ ra các tác phẩm của Shakespeare như Hamlet trong thời gian bằng tuổi vũ trụ thực ra rất nhỏ, nhưng vẫn khác 0.

Các biến thể của định lý bao gồm nhiều con khỉ gõ vô hạn, và văn bản mục tiêu thay đổi từ một mục từ điển đến một câu đơn. Lịch sử của nguyên lý bắt nguồn từ xa xưa, trong tác phẩm Luận về sinh diệt của Aristotle, Về bản tính thần minh của Cicero, các quan điểm của Blaise Pascal và Jonathan Swift, cho đến phiên bản hiện đại với máy đánh chữ. Trong những năm đầu thế kỷ 20, Émile Borel và Arthur Eddington sử dụng nguyên lý để minh họa cho thang thời gian ẩn giấu trong cơ sở của cơ học thống kê.

Chứng minh

Chứng minh trực tiếp

Có một chứng minh dễ hiểu cho định lý: Nếu hai sự kiện không phụ thuộc trạng thái, xác suất hai sự kiện cùng xảy ra là tích xác suất mỗi sự kiện. Ví dụ, khả năng mưa ở Hà Nội trong một ngày cụ thể là 0.3, khả năng có động đất ở Thành phố Hồ Chí Minh trong cùng ngày là 0.008, vậy xác suất hai sự kiện cùng xảy ra trong ngày đó là  0.3 × 0.008 = 0.0024, giả sử nó thực sự độc lập. Cho một máy đánh chữ có 50 phím, và từ cần gõ là banana. Giả sử các phím được gõ ngẫu nhiên (xác suất được gõ của các phím bằng nhau) và không phụ thuộc vào nhau, xác suất ký tự đầu tiên là 'b' là 1/50, xác suất ký tự thứ hai là 'a' là 1/50... vì các sự kiện không phụ thuộc lẫn nhau. Từ đó, xác suất sáu ký tự đầu tiên khớp với banana là:(1/50) × (1/50) × (1/50) × (1/50) × (1/50) × (1/50) = (1/50)⁶ = 1/15 625 000 000 , nhỏ hơn một phần mười lăm tỉ. Tương tự, xác suất 6 ký tự tiếp theo khớp với banana cũng là (1/50)⁶, và 6 ký tự tiếp sau đó.... Từ đó, xác suất không gõ ra từ banana trong một khối 6 ký tự là 1 − (1/50)⁶. Vì mỗi khối được gõ không phụ thuộc lẫn nhau, xác suất X_n để không gõ ra từ banana trong n khối 6 ký tự là:

:$X\_n=\backslash left(1-\backslash frac\{1\}\{50^6\}\backslash right)^n.$

Khi n tăng, X_n giảm. Với n bằng một triệu, X_n khoảng 0.9999, nhưng với n bằng mười tỉ X_n chỉ còn khoảng 0.53, và với n là 100 tỉ con số đó là 0.0017. Khi n tiến tới vô cực, X_n tiến tới không; nghĩa là bằng cách cho n đủ lớn, ta có thể có X_n nhỏ như mong muốn, và khi đó xác suất có một khối "banana" trong chuỗi gõ ra tiến tới 1. Hơn nữa vì từ có thể xuất hiện giữa hai khối, khả năng xuất hiện từ banana còn lớn hơn tính toán trên.

Lập luận tương tự chỉ ra tại sao có ít nhất một trong số các con khỉ vô hạn sẽ gõ ra từ cần thiết bằng với tốc độ của một người đánh máy bình thường. trong trường hợp này X_n = (1 − (1/50)⁶)ⁿ khi X_n biểu diễn xác suất n con khỉ đầu tiên không gõ đúng banana trong 6 ký tự đầu tiên. Khi xét 100 tỉ con khỉ, xác suất này là 0.17%, và khi số khỉ tăng lên, xác suất này tiến về không. Dù sao, nếu cho một số khỉ có nghĩa thực hiện gõ trong một khoảng thời gian có nghĩa, kết quả là ngược lại: Nếu có đủ nhiều khỉ và chúng gõ trong vũ trụ quan sát được (10⁸⁰), và mỗi con khỉ gõ 1,000 ký tự trong một giây, liên tục gõ trong thời gian bằng 100 lần tuổi vũ trụ (10²⁰ giây), xác suất bọn khỉ tái tạo lại một tác phẩm văn học ngắn là gần bằng 0.

Xâu vô hạn

Định lý này có thể được phát biểu tổng quát hơn với định nghĩa về xâu, với đây là các ký tự được chọn từ bảng chữ cái hữu hạn:

• Cho một xâu vô hạn mà tất cả các ký tự đều được chọn ngẫu nhiên với xác suất đều nhau, bất kỳ xâu hữu hạn nào đó sẽ phải xuất hiện trong xâu vô hạn đó như là xâu con ở bất kỳ vị trí nào.

Xác suất

Gần như chắc chắn