משפט הקוף המקליד

אם נמתין די הצורך, גם שימפנזה המקליד באקראי יקליד לבסוף את כל יצירות שייקספיר

משפט הקוף המקליד הוא טענה מתמטית פשוטה, לפיה אם נבחר טקסט באורך סופי, אז הוא יופיע ברצף אינסופי של תווים אקראיים המוגרלים מהתפלגות אחידה (אך לאו דווקא מהתפלגות זו) בהסתברות של 100%. בניסוח פופולרי, ברוח מאמרו של המתמטיקאי הצרפתי אמיל בורל, בו הופיע המשפט לראשונה, אפשר לומר שאם קוף מקליד תווים אקראיים במכונת כתיבה במשך זמן הולך וגדל ללא מגבלה - לבסוף יעבור מספיק זמן כך שיופיעו בטקסט כל כתבי ויליאם שייקספיר.

הוכחת הטענה

ההסתברות שיתרחשו שני מאורעות בלתי־תלויים שווה למכפלת ההסתברויות שלהם; לדוגמה, אם ההסתברות שפרוסת לחם תיפול על הצד המרוח בחמאה היא $0.5$, וההסתברות שהכסא יפול על צד המשענת היא $0.7$, הרי שההסתברות ששני המאורעות יתרחשו היא $0.35$, זאת בהנחה שאין תלות בין המאורעות.

נניח כעת שברשותנו מקלדת בעלת חמישים תווים, ונאמר שעל הקוף להקליד את המילה "אנציקלופדיה". ההסתברות שהאות הראשונה שיקליד תהיה אל"ף היא אחת לחמישים, דהיינו, 0.02. ההסתברות שיקליד את האות אל"ף ואחריה את האות נו"ן היא אחת לחמישים כפול אחת לחמישים, לשון אחר, 0.0004. הסיכוי שאחת־עשרה אותיות רצופות שיקליד יאייתו את המילה "אנציקלופדיה" הוא נמוך מאוד: אחת לחמישים בחזקת 11, שהן 0.0000000000000000002048.

ההסתברות, $p$, לכך שאחת-עשרה האותיות הראשונות לא ייצרו את המילה "אנציקלופדיה" היא כמעט ודאית:

$p=1-0.0000000000000000002048=99.99999999999999997952\,\%$.

ניתן לקוף להדפיס עוד 11 אותיות. אם עדיין לא מופיעה המילה "אנציקלופדיה", הרי שהיא אינה מופיעה במקטע בן אחת-עשרה האותיות הראשונות, וגם לא באחת-עשרה האותיות האחרונות. מכיוון שאלו מקטעים זרים, האותיות נבחרות באופן בלתי-תלוי בכל אחד מהם בנפרד, ולכן גם המאורעות המילה אינה מופיעה במקטע הראשון והמילה אינה מופיעה במקטע השני בלתי-תלויים. לכן ההסתברות שהמילה לא תופיע בשני המקטעים שווה ל- $p^{2}$. מכאן נובע שההסתברות לכך שהמילה אינה מופיעה בשום מקום ברצף בן עשרים ושתיים האותיות, קטנה מ-$p^{2}$.

באופן דומה, עבור n מקטעים של 11 אותיות למקטע, ההסתברות שהמילה לא תופיע היא לכל היותר $p^{n}$. היות ש־$p<1$, כאשר n גדל לאינסוף, ההסתברות שהמילה לא תופיע בכלל שואפת לאפס, וההסתברות שההפך הוא הנכון שואפת לאחת, כלומר, המילה תופיע כמעט בוודאות.

אותו טיעון אפשר להחיל על טקסט בכל אורך סופי - כמו כל כתביו של שייקספיר לדוגמה.

תוחלת הזמן להופעת קטע מסוים

אפשר להראות שעבור קטע נתון (כגון המילה "אנציקלופדיה"), לא רק שההסתברות להופעתה בסופו של דבר בסדרת התווים שהקוף מדפיס שווה ל-1, אלא אף תוחלת זמן ההמתנה למאורע זה היא סופית. תוחלת הזמן עד להופעת קטע בן n אותיות המורכב מ-M סוגי תווים, בהנחה שכל תו נבחר בהסתברות אחידה, אינה עולה על $\ nM^{n}$.

סדרות ארוכות במתמטיקה

על-פי המשפט שהוצג לעיל, טקסט סופי נתון וקבוע יופיע בהסתברות אחד בסדרה אקראית אינסופית. אפשר להוכיח יותר מזה: בהינתן סדרה אקראית אינסופית (שבה האותיות מוגרלות מאלפבית סופי, באופן אחיד ובלתי תלוי), כל טקסט סופי יופיע (שוב, בהסתברות 1). יתרה מזו, כל טקסט מקרי מופיע בשכיחות השווה להסתברות שלו להופיע בכל מקום בסדרה. להרחבה בנושא זה, ראו מספר נורמלי.

התוצאה האינטואיטיבית שלפיה אפשר לצפות לתופעות מוזרות בסדרה, בתנאי שהיא ארוכה מספיק, מופיעה פעמים רבות בקומבינטוריקה. הלמה של שירשוב היא דוגמה לא פשוטה לכך, שהיא בעלת השלכות חשובות בתורת החוגים.

קוף מקוק - חזרות על האות האנגלית "S"

בשנת 2003 נערך "ניסוי" בגן החיות של פייתון, שבמהלכו ניתנו שש מכונות כתיבה לקופי מקוק. במשך חודש הפיקו הקופים חמישה עמודים בלבד, ואלה הורכבו בעיקר מחזרות על האות האנגלית "S". יתרה מכך, הקופים השחיתו את המקלדות במגוון אופנים. משך זמן הניסוי זניח לחלוטין ביחס לפרק הזמן הדרוש בתוחלת כדי להפיק יצירה בעלת משמעות, וכן תנאי הניסוי הושפעו ממשתנים מפריעים נוספים, וכך למשל הקופים הרסו חלק ממכונות הכתיבה במקום להקיש בהן אותיות.

דרך מלאכותית לעריכת הניסוי מספק האתר "סימולטור הקופים של שייקספיר", המכיל תוכנית Java, המדמה הקלדות אקראיות של קופים רבים. עד היום נתקבלו בסימולציה זו תוצאות המכילות בסך הכל עשרים וארבעה תווים רצופים מתוך מחזהו של שייקספיר - הנרי הרביעי..

ראו גם

• הלמה של בורל-קנטלי
• מיון אקראי

קישורים חיצוניים

• Terry R. McConnell, The Expected Time to Find a String in a Random Binary Sequence, על התוחלת של זמן ההמתנה לסדרה נתונה.