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

Đị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)6 = 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)6, 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)6. 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à:
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)6)"n" 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 (1080), 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ụ (1020 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: