متى تنسى أوراق اللعب ترتيبها عند الخلط باليد؟

خلط أوراق اللعب صورة ملموسة لسؤال أساسي في الاحتمالات: كم من الوقت تستغرق عملية عشوائية لتنسى من أين بدأت؟ الرزمة المفتوحة حديثًا مرتبة. وكل خلطة تبعثرها أكثر قليلًا، إلى أن لا يبقى أي أثر يمكن رصده من الترتيب الأصلي.

يميّز الرياضيون بين مستويين من الإجابة. زمن الخلط يعطي رتبة المقدار. أما القطع الحاد (cutoff) فيقول أكثر بكثير: حول لحظة دقيقة، تنتقل الرزمة من «غير مخلوطة بوضوح» إلى «مخلوطة تمامًا» دفعة واحدة تقريبًا. اخلط أقل من ذلك بقليل فيظل بإمكانك أن تميّز؛ واخلط أكثر بقليل فلن تستطيع.

الخلط كما يراه الرياضي

في الخلط باليد، تمسك الرزمة بيد وتُسقط حزمًا صغيرة من الأوراق في اليد الأخرى. وتنمذج الورقة ذلك هكذا: كل فجوة من الفجوات الـn − 1 بين الأوراق المتجاورة تُقطع باستقلال باحتمال p، ويُعكس ترتيب الحزم الناتجة. والمرور الكامل على الرزمة يُحسب خلطة واحدة.

ووفقًا للورقة، كانت أعمال سابقة قد حددت رتبة المقدار. فقد حصر بيمانتل (Pemantle) زمن الخلط بين n² وn² log n؛ ثم بيّن يوناسون (Jonasson) أن n² log n هي الرتبة الصحيحة. لكن الثابت الدقيق، وهل يحدث قطع حاد أصلًا، بقيا مفتوحين: فقد أدرج دياكونيس (Diaconis) وبال (Pal) القطع الحاد للخلط باليد مسألةً مفتوحة في 2022.

النتيجة

يبرهن يونجيانغ جيانغ أن القطع الحاد موجود ويحدد موضعه.

مبرهنة. لاحتمال قطع ثابت p، يُخلط الخلط باليد، في الرتبة الأولى، عند

p² / (2(1 − p)π²) × n² log n

خلطة. قبل ذلك بقليل، تبقى الرزمة بعيدة عن العشوائية؛ وبعده بقليل، تكون قريبة منها.

ولـp = 1/2 — أي قطع نصف الفجوات في المتوسط — تصبح الصيغة n² log n / (4π²).

كيف يعمل البرهان

يتكون البرهان من ثلاثة أجزاء مستقلة.

1. الحد الأدنى يتتبّع ورقة واحدة. يتطور موقعها بطريقة نظيفة على نحو لافت: أنماط دقيقة على شكل جيب التمام تضمحل بمعدل معروف، حتى لرزمة محدودة. وعند جمعها على الرزمة كلها، تحتفظ بأثر قابل للرصد من الترتيب الأولي حتى اللحظة المتوقعة.
2. الحد الأعلى يقارن رزمتين لا تختلفان إلا بتبادل ورقتين. وعند تشغيلهما بالقطوع العشوائية نفسها، يتصرف الفرق كموضعين مُعلَّمين يتجولان في الرزمة حتى يصبحا متجاورين ويمكن دمجهما. والمعدل الذي يحدث به ذلك يطابق الحد الأدنى.
3. متباينة ساكنة حول التباديل، لا علاقة لها بالخلط، تحوّل هذه المقارنة إلى عبارة عن الرزمة كلها. وهي الجزء الأكثر تقنية في الورقة، مبنية بالاستدعاء الذاتي على جداول تعدّ كيف تتوزع الأوراق على الكتل.

وتبرهن الورقة أيضًا وجود قطع حاد لطريقة أخرى لقياس الفوضى، هي الإنتروبيا النسبية، من دون تحديد موضعه الدقيق.

ما تقوله الصيغة عن رزمة حقيقية

بإدخال رزمة من 52 ورقة في الصيغة مع p = 1/2 نحصل على 52² × ln 52 / (4π²)، أي نحو 270 خلطة. هذا حسابنا نحن، لا رقم من الورقة، وينبغي قراءته مؤشرًا تقريبيًا: فالمبرهنة تصف سلوك الرزم الكبيرة جدًا، وحدّ التصحيح غير محدد كميًا. وللمقارنة، تذكر الورقة المقياس (3/2) log₂ n الذي أثبته باير (Bayer) ودياكونيس للخلط المتداخل (riffle shuffle) — نحو 8.6 لـ52 ورقة، مع التحفظ نفسه. والفجوة بين n² log n وlog n هي ما يجعل الخلط باليد بهذا البطء.

رتبة أولى، وأيدٍ مثالية

النتيجة من الرتبة الأولى: لا تعطي عرض نافذة الانتقال ولا شكلها الدقيق. واحتمال القطع مُثبت، والقطوع مفترضة مستقلة، وهذا تبسيط مثالي للأيدي الحقيقية. وفي حاشية، يذكر المؤلف أن نظام الذكاء الاصطناعي GPT-6 Astra «استُخدم في تطوير الحجج، والتحقق من الحسابات، وإعداد العرض»، وأن المؤلف مسؤول عن المحتوى الرياضي. والورقة نسخة أولية (preprint).