Simulating Keystroke and Computing the Theoretical Probability of Infinite Monkey Theorem with Markov Process
Yi, Zhou, Jiang
The Infinite Monkey Theorem states that if one monkey randomly hits the keys in front of a typewriter keyboard during an infinite amount of time, any works written by William Shakespeare will almost surely be typed out at the end of the total text. Due to the seemingly low chance of typing the exact literature works, our group are motivated to find out the expected time the Hamlet, our target text, being typed out by simulated random typing on a standard keyboard. For finding the answer, 30 users randomly typed characters into a file. Then, the frequency of each characters occurred following the previous character is calculated. This conditional probability is used to build the Markov matrix by considering all 128 times 128 cases. Finally, the expected time we estimated is about 10 to the power of 34 (min), which is surprisingly lower than the theoretical computation, and not achievable at all even in the cosmic time.
academic
محاكاة ضغطات لوحة المفاتيح وحساب الاحتمالية النظرية لنظرية القرد اللانهائي باستخدام عملية ماركوف
تنص نظرية القرد اللانهائي على أنه إذا قام قرد بضغط عشوائي على مفاتيح الآلة الكاتبة لفترة زمنية لانهائية، فسيكتب حتماً أي عمل من أعمال شكسبير. تقدر هذه الدراسة من خلال الطرق التجريبية الوقت المتوقع اللازم لإنتاج نص "هاملت" عن طريق الكتابة العشوائية. جمع الباحثون بيانات الكتابة العشوائية من 30 متطوعاً، وحسبوا الاحتمالية الشرطية بين الأحرف، وبنوا مصفوفة ماركوف بحجم 128×128. وجدت الدراسة أن الوقت المتوقع لكتابة أول 78 حرفاً من "هاملت" بشكل صحيح يبلغ حوالي 10^134 دقيقة (حوالي 1.41533×10^117 مرة من عمر الكون)، وهذه النتيجة أقل قليلاً من نتائج الحساب بناءً على الافتراض النظري للاستقلالية، لكنها تبقى غير قابلة للتحقق عملياً بشكل كامل.
تهدف هذه الدراسة إلى تحديد كمي لمسألة محددة في نظرية القرد اللانهائي: ما هي احتمالية وقت الانتظار المتوقع لإنتاج نص "هاملت" الكامل لشكسبير عن طريق الكتابة العشوائية؟
القيمة النظرية: نظرية القرد اللانهائي هي تجربة فكرية كلاسيكية في نظرية الاحتمالات، لكنها تفتقر إلى تقديرات تجريبية قائمة على سلوك الكتابة البشري الفعلي
القيمة التعليمية: تساعد الجمهور على فهم الأحداث ذات الاحتمالية الضئيلة جداً والمعنى العملي للاحتمالية الرياضية
الابتكار المنهجي: استكشاف جدوى تطبيق سلاسل ماركوف على حساب احتمالية توليد تسلسلات الأحرف
افتراض الاستقلالية والاحتمالية المتساوية: تفترض الطرق التقليدية أن كل حرف مستقل واحتمالية متساوية، وهذا لا ينطبق على سلوك الكتابة الفعلي
غياب البيانات التجريبية: أظهرت تجربة القرد الحقيقية بجامعة بليموث عام 2002 أن الواقع أكثر تعقيداً بكثير (كتب القرد عدداً كبيراً من الحرف "S" وأتلف لوحة المفاتيح)
تجاهل الاعتماد بين الأحرف: لم تأخذ الطرق المحاكاة الموجودة في الاعتبار بشكل كافٍ العلاقات بين الأحرف الناجمة عن تخطيط لوحة المفاتيح وعادات الكتابة
استلهم الباحثون من طريقة احتمالية الرسم البياني (graph likelihood approach)، معتقدين أن الأحرف على لوحة المفاتيح لها اعتماد مكاني - بعد كتابة حرف معين، من المرجح أن يتم كتابة الحرف المجاور له. لذلك اقترحوا استخدام نموذج سلسلة ماركوف لمحاكاة عملية الكتابة العشوائية بشكل أكثر واقعية.
بناء مصفوفة انتقال ماركوف بناءً على بيانات الكتابة الحقيقية: جمع عينات كتابة عشوائية من 30 متطوعاً (حوالي 100,000 حرف)، وحساب احتمالية الانتقال الشرطية بين الأحرف، وبناء مصفوفة ماركوف بحجم 128×128
اقتراح خطة تخزين الأعداد النسبية: بسبب قيود دقة الفاصلة العائمة في Python (حوالي 10^-16)، تم استخدام طريقة الأعداد النسبية بفصل البسط والمقام، مما يسمح بحساب احتمالية ضئيلة جداً (تصل إلى 10^-134)
تحقيق التصور الجغرافي لتكرار ضغطات لوحة المفاتيح: استخدام ArcGIS و GeoPandas لإنشاء خريطة حرارية للوحة المفاتيح، مما يوضح بصرياً نمط التوزيع المكاني للكتابة العشوائية البشرية
توفير إثبات نظري لتقارب سلسلة ماركوف: بناءً على نظرية Bolzano-Weierstrass ومبدأ Banach للانكماش، تم إثبات تقارب مصفوفة ماركوف
تقدير كمي للنتائج: تم حساب احتمالية كتابة أول 78 حرفاً من "هاملت" بشكل صحيح بـ 10^-134، مع وقت انتظار متوقع يبلغ 10^134 دقيقة
الإدخال: تسلسل كتابة عشوائي على لوحة مفاتيح آلة كاتبة قياسية (LG Rog Strix Flare) الإخراج: احتمالية وقت الانتظار المتوقع لكتابة نص "هاملت" الكامل لشكسبير بشكل صحيح القيود:
استخدام لوحة مفاتيح موحدة (إزالة المفاتيح الوظيفية، الاحتفاظ بمفاتيح الأحرف)
بناءً على بيانات سلوك الكتابة البشري الحقيقي
الأخذ في الاعتبار علاقات ماركوف الاعتمادية بين الأحرف
الحرف الأولي: اختيار عشوائي موحد من 26 حرفاً صغيراً (احتمالية 1/26)
توليد الأحرف اللاحقة (الكود الزائف):
بناءً على الحرف السابق v (قيمة ASCII):
1. تحديد موقع الصف v من مصفوفة الانتقال
2. استخدام دالة Python randint() لتوليد عدد صحيح عشوائي k ∈ [1, 10^18]
3. البحث عن أصغر فهرس عمود m بحيث S[m,v] ≥ k/10^18
4. إرجاع الحرف ذو قيمة ASCII m
التحدي: احتمالية كلمة من 5 أحرف قد تصل بالفعل إلى 10^-7، وأكثر من 10 أحرف ستتجاوز دقة الفاصلة العائمة في Python الابتكار: استخدام العمليات الحسابية بالأعداد النسبية طوال الوقت، مما يحافظ على القدرة على الحساب الدقيق
ArcGIS/ArcMap: إنشاء ملفات شكل لوحة المفاتيح (.shp)
GeoPandas: دمج بيانات التكرار مع الأشكال الجغرافية
حساب مصفوفة ماركوف:
# مثال الكود الزائف
for each sample file:
for i in range(1, len(text)):
prev_char = text[i-1]
curr_char = text[i]
transition_count[prev_char][curr_char] += 1
# تطبيع إلى احتمالية
for v in all_chars:
total = sum(transition_count[v])
for u in all_chars:
P[u][v] = transition_count[v][u] / total
التعبير المضلل عن "أقل": يقول الملخص أن النتيجة "أقل بشكل مفاجئ من الحساب النظري"، لكن 10^134 لا يزال رقماً فلكياً، وبسبب الخفة لا يمكن المقارنة الفعلية مع القيمة النظرية
قيمة عملية محدودة: احتمالية أول 78 حرفاً لها فائدة محدودة في فهم النظرية الكاملة
هذه ورقة طموحة في الهدف لكن بها عيب أساسي في التنفيذ. حاول الباحثون تحسين تقدير احتمالية نظرية القرد اللانهائي من خلال البيانات الحقيقية ونموذج ماركوف، وهذه الفكرة بحد ذاتها مبتكرة. ومع ذلك، حجم العينة البالغ 100,000 حرف بعيد جداً عن كفايته لنمذجة مصفوفة انتقال 128×128، مما أدى إلى عدم تحقيق الهدف الأساسي (حساب احتمالية "هاملت" الكاملة)، واضطروا إلى الاكتفاء بنتيجة أول 78 حرفاً فقط.
أكبر قيمة للورقة تكمن في الكشف الصادق عن الصعوبات التي واجهتها أثناء البحث، بما في ذلك مشكلة المصفوفة الخفيفة وتحديات دقة الأرقام، وهذا له قيمة تحذيرية للباحثين اللاحقين. خريطة حرارية لوحة المفاتيح وحل الأعداد النسبية هما نقاط مضيئة، لكن لا يمكنهما تعويض المشكلة الأساسية في المنهجية.
لجعل البحث ذا قيمة حقيقية، يتطلب:
توسيع حجم العينة بمئات المرات على الأقل (الوصول إلى مستوى عشرات الملايين من الأحرف)
استخدام تقنيات تمويه لمعالجة الاحتمالية الصفرية
إجراء مقارنة كمية صارمة مع نموذج الاستقلالية
توضيح نطاق تطبيق الطريقة (التسلسلات القصيرة)
بشكل عام، هذه محاولة استكشافية مفيدة، لكنها بعيدة عن مستوى النضج الأكاديمي الكامل.