Algorithms, Complexity, and Entropy of the Bernard-Letac Fair-Sampling Construction

تخيل عالماً تكون فيه كل عملة تقلبها مائلة، ربما تسقط على الوجه (Heads) أكثر من الظهر (Tails)، أو ربما تميل لجانب واحد بشدة تجعل الجانب الآخر يبدو وكأنه لا يظهر أبداً. لعقود من الزمن، تساءل علماء الرياضيات وعلوم الحاسوب سؤالاً بسيطاً في ظاهره: إذا كان لديك فقط وصول إلى مصدر عشوائي مكسور ومنحاز كهذا، فهل يمكنك مع ذلك توليد نتيجة عادلة تماماً؟ هل يمكنك فرض قلب عملة عادلة، أو اختيار عادل من بين خيارات عديدة، باستخدام لا شيء سوى هذه الإشارات المنحازة وغير المتوقعة؟ الإجابة هي نعم، لكن الطريق إلى العدالة ليس مباشراً. فهو يتطلب طريقة لا تعرف شيئاً عن الانحياز، وتعمل مع أي نوع من أنواع الانحياز، وتتوقف في اللحظة المناسبة تماماً لضمان أن تكون النتيجة عشوائية حقاً. هذا هو مشكل العينات العادلة، وهو تحدٍ يقع عند تقاطع الاحتمالات، ونظرية الأعداد، وجوهر المعلومات.

في دراسة حديثة، تعمق كلود غرافيل، الباحث في جامعة تورنتو متروبوليتان، في حل محدد لهذه المشكلة، اقترحه برنارد وليتاك في عام 1971. وبينما قدم العمل الأصلي وصفة رياضية ذكية للعدالة، إلا أنه ترك العديد من الأسئلة العملية دون إجابة. قام بحث غرافيل بتحويل تلك الوصفة المجردة إلى مجموعة من الخوارزميات الملموسة والفعالة، مثبتاً بدقة أنها تعمل ومحللاً بالضبط مقدار الجهد الذي تتطلبه. وتكشف الدراسة أن تكلفة توليد نتيجة عادلة ليست مجرد رقم بسيط، بل ترتبط ارتباطاً وثيقاً بالبنية الخفية للمصدر المنحاز نفسه. ومن خلال معالجة المشكلة من منظور نظرية المعلومات الحديثة، كشف البحث عن صيغ دقيقة للمدة التي تستغرقها العملية، وأظهر أن الطريقة الأكثر كفاءة لاستخدام هذه الإشارات المنحازة تعتمد على نوع محدد من "درجة الحرارة" الرياضية المعروفة باسم الإنتروبيا (الاعتلاج).

جوهر طريقة برنارد-ليتاك هو عملية تراكم. تخيل مسافراً يسير عبر شبكة، يتخذ خطوات بناءً على الرموز المستخرجة من المصدر المنحاز. إذا كان المصدر عملة، يتحرك المسافر يميناً للوجه (Heads) ولأعلى للظهر (Tails). يستمر المسافر في السير، مسجلاً إجمالي عدد الخطوات في كل اتجاه، حتى يصل إلى نقطة توقف محددة. نقطة التوقف هذه لا تُختار عشوائياً؛ بل هي موقع حيث تؤدي قاعدة عد معقدة، تتضمن عدد الطرق المختلفة التي كان بإمكان المسافر الوصول بها إلى هناك، إلى رقم يقبل القسمة تماماً على عدد النتائج التي تريد توليدها. على سبيل المثال، إذا كنت تريد اختياراً عادلاً بين خمسة خيارات، فإن العملية تتوقف في اللحظة التي يكون فيها عدد المسارات المؤدية إلى الموقع الحالي مضاعفاً لخمسة. وسحر هذه الطريقة يكمن في أنه بغض النظر عن وزن العملة، يمكن تقسيم المسارات المؤدية إلى نقطة التوقف هذه إلى خمس مجموعات متساوية الحجم تماماً. وهذا يضمن أنه عندما تتوقف العملية، تكون النتيجة النهائية عادلة تماماً، رغم أن المدخلات كانت منحازة بشدة.

يبدأ عمل غرافيل بتحويل هذه الفكرة الرياضية الأنيقة إلى خمس خوارزميات حاسوبية متميزة وخطوة بخطوة. تم تصميم كل خوارما لتعالج المهمة بضمانات رسمية من الصحة. تقدم الدراسة تعليمات مفصلة حول كيفية حساب الأعداد اللازمة بكفاءة، مما يوضح أن العملية يمكن تنفيذها دون الحاجة لمعرفة الانحياز مسبقاً. أحد أهم المساهمات هو تحليل المدة التي تستغرقها هذه العملية. وجد الباحثون أن متوسط عدد السحبات المطلوبة للتوقف ليس قيمة ثابتة، بل يعتمد على التوزيع المحدد للمصدر المنحاز. لقد اشتقوا صيغة دقيقة لهذا المتوسط الزمني، تتضمن جداءً لانهائياً من الحدود المتعلقة باحتمالات المصدر. وتكشف هذه الصيغة أن التكلفة محكومة بعائلة من المقاييس تسمى "إنتروبيات ريني" (Rényi entropies)، والتي تلتقط جوانب مختلفة من عشوائية المصدر.

ثمة نتيجة مفاجئة في الورقة البحثية وهي أن التخمين البديهي البسيط لتكلفة العملية يكون دائماً خاطئاً. قد يفترض الكثيرون أن التكلفة تتحدد تقريباً بالمقياس الأساسي للعشوائية، المعروف باسم "إنتروبي شانون". ومع ذلك، تثبت الدراسة أن هذا التقريب البسيط يبالغ باستمرار في تقدير التكلفة الحقيقية. التكلفة الفعلية دائماً أقل من التخمين البسيط، لكن الفرق ليس ضئيلاً. أظهر الباحثون أنه مع نمو عدد النتائج المرغوبة بشكل كبير جداً، فإن التكلفة لا تنخفض إلى الحد الأدنى النظري الذي تتنبأ به نظرية المعلومات الأساسية. بدلاً من ذلك، تستقر عند قيمة أعلى صراحة من الحد النظري. وهذا يعني أنه بينما تكون طريقة برنارد-ليتاك عادلة، إلا أنها ليست كفؤة تماماً؛ فهي تهدر حتماً بعض العشوائية المتاحة في المصدر. ويعتمد مقدار الهدر هذا على التوزيع الكامل للمصدر، وليس فقط على الإنتروبي الإجمالي له.

كما تتناول الورقة البحثية مسألة كيفية جعل العملية أسرع على الحاسوب. تتطلب الطريقة الأصلية قدراً كبيراً من الحساب لتحديد المجموعة التي ينتمي إليها مسار معين، وهي خطوة قد تصبح بطيئة جداً مع زيادة عدد السحبات. بالنسبة للحالة الخاصة بتوليد بت (bit) عادل واحد (اختيار بين خيارين) من مصدر ثنائي، اكتشف غرافيل طريقة لتجاوز الحسابات الثقيلة تماماً. من خلال تحليل بنية المسارات، صمم الباحث آلة بسيطة تتكون من سبع حالات فقط يمكنها تحديد النتيجة عن طريق قراءة الأرقام الثنائية لإحداثيات المسار. تقلل هذه الآلة الجهد الحسابي من النمو التربيعي، الذي يصبح غير قابل للإدارة مع الأعداد الكبيرة، إلى نمو شبه خطي، مما يجعل العملية أكثر عملية للتطبيقات الواقعية.

تستكشف الدراسة أيضاً ما يحدث عندما لا يكون عدد النتائج عدداً أولياً بل عدداً مركباً، مثل ستة أو عشرة. في هذه الحالات، تصبح البنية الرياضية أكثر اضطراباً. وجد الباحثون أنه بالنسبة للأعداد المركبة، يمكن أن تتعثر العملية في مواقف تكون فيها نقاط التوقف معينة غير قابلة للوصول، كما أن مجموعات المسارات ليست دائماً متساوية الحجم. هذا الاضطراب يمنع الباحثين من إيجاد صيغة بسيطة مغلقة التكلفة لهذه الحالات، مما يترك الأمر كمسألة مفتوحة للعمل المستقبلي. وتقترح الورقة أنه لأغراض عملية، قد يكون من الأفضل التقريب إلى أقرب عدد أولي لتجنب هذه التعقيدات، رغم أن هذا لم يتم إثباته بصرامة.

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