مسألة جامع القسائم
المحتويات
على سبيل التعريف، تشير مسألة جامع القسائم في نظرية الاحتمال إلى التحليل الرياضي لمسابقات «اجمع جميع القسائم وفز»، إذ تطرح المسألة السؤال الآتي:
وفي السياق ذاته، يمكن كذلك صياغة هذه المسألة صياغة أخرى وهي: «إذا توفر عدد محدد (فرضًا ) من أنواع القسائم، فما القيمة المتوقعة للقسائم الواجب سحبها مع إعادة القسائم إلى المجموعة قبل أن تسحب كل قسيمة مرة واحدة على الأقل؟»
من جهة ثانية، يُظهِر التحليل الرياضي للمسألة أن القيمة المتوقعة لعدد المحاولات المطلوبة تزداد بمعدل . تستلزم العملية مثلاً عند توفر 50 نوعًا مختلفًا نحو 225 محاولة، لجمع جميع القسائم الخمسين. وأحيانًا تُعبر عن المشكلة بدلاً من ذلك باستخدام نرد متعدد الأوجه (ذو n وجهًا).
الدوال المولدة
لذلك، فمن من أجل :
من جهة ثانية، وبإعادة كتابة معامل التحويل الثنائي عبر دالة غاما وتوسيعه على هيئة لمتسلسلة (بدلالة الأعداد التوافقية المعممة)، نجد أنَّ:
وفي السياق ذاته، يُنتج تعويض ب في الدالة المولدة الاحتمالية دالة مولدة عادية ل. وباستخدام تحليل الكسور الجزئية ، يمكن أخذ التوسع:
كذلك، ويمكن الحصول على العزوم الخام للتوزيع من العزوم الهابطة عبر تحويل ستيرلنغ؛ واستناداً إلى المتطابقة:
ينتج:
علاوةً على ذلك، بالنسبة إلى دالة مولدة عادية ، ولأن ، فإن تغييرًا من التحويل الثنائي ينتج . (وتحديداً، إذا كان, .)
إضافةً إلى ذلك، ويمكن كذلك كتابة هذه الصيغة بدلالة الحدوديات الهابطة وعدد لاه على النحو الآتي:
ومن ثَمَّ:
وصف المسألة
ومن ناحية أخرى، لدراسة هذه الظاهرة بمزيد من الدقة، نعرف متغيرًا عشوائيًا ، الذي يمثل عدد علب حبوب الإفطار التي تُشترى قبل الحصول على نوعًا من القسائم من بين أنواع القسائم في المجموعة. ففي المثال، ، لأنه بعد عملية شراء واحدة حتمًا سيمتلك الجامع قسيمة واحدة؛ و، و، و. ومن ثم فإن زمن اللازم للحصول على المجموعة الكاملة هو . ويمكن اعتبار هو وقت التوقف، إذ تُشترى علبة من حبوب الإفطار في كل خطوة زمنية.
الحل
ومن ناحية أخرى، لتكن الزمن الإضافي اللازم للحصول على القسيمة الجديدة رقم ، مع العلم أنَّ الجامع لديه بالفعل قسيمة مختلفة. ومن ثم . وفي مثال الشكل أعلاه، لدينا (ويكون مساويًا دائمًا 1)، و، و، و. وهنا لدينا إذ اشترى الجامع في المثال 10 علب للحصول على المجموعة الكاملة المكوّنة من القسائم الأربع.
ومن جهة أخرى، يهدف الجامع للحصول على قسيمة واحدة من كل نوع من أنواع القسائم وعددها . لتحقيق ذلك، يشتري علبًا من حبوب الإفطار. وكما يوضح الشكل أدناه، تحتوي كل علبة على قسيمة واحدة. في المثال، يشتري العلبة الأولى ويحصل فيها على القسيمة 1. ثم يشتري العلبة الثانية ويحصل على القسيمة 4. وفي عملية الشراء الثالثة، يحصل على القسيمة 1 مرة أخرى، ولذلك لا تتغير مجموعته؛ إذ يظل يمتلك القسيمتين 1 و4. ويواصل شراء علب حبوب الإفطار حتى يحصل على قسيمة من كل نوع. ونفترض أن جميع القسائم متساوية الاحتمال، أي إن احتمال الحصول على أي نوع من أنواع القسائم عند شراء علبة هو .
وعلى صعيد آخر، نرمز إلى بعدد العلب اللازم شراؤها لجمع القسائم كلها. ففي المثال أعلاه، ، لأن الجامع اشترى 10 علب من حبوب الإفطار قبل أن يحصل على القسائم الأربع. ومن البديهي أن يكون الحصول على القسائم الأخيرة أصعب من الحصول على القسائم الأولى.
أعداد ستيرلنغ
وفي هذا السياق، تُعرَّف القوة الجزئية بالعلاقة ،حيث هو عدد ستيرلنغ من النوع الثاني.
ومن ناحية أخرى، تتقابل تسلسلات من رميات النرد مع الدوال التي يبلغ عددها ، في حين يبلغ عدد الدوال الشاملة (التي تصيب كل وجه مرةً على الأقل) ، ومن ثَمَّ يكون احتمال ظهور جميع الوجوه في غضون رميات هو . وبتطبيق علاقة التكرار لأعداد ستيرلنغ، يكون احتمال أن تكفي رميات بالضبط هو
وفي هذا السياق، ليكن المتغير العشوائي عدد مرات رمي النرد قبل ظهور جميع الوجوه.
حساب القيمة المتوقعة
هو ثابت أويلر.
من جانب آخر، حيث هو العدد التوافقي من الرتبة . وباستخدام التحليل المقارب للأعداد التوافقية نحصل على:
وعند نستعيد النتيجة الأصلية
في هذا الإطار، وباستخدام متباينة ماركوف للحصول على حد أعلى للاحتمال المطلوب:
ومن جهة أخرى، ليكن الزمن هو الزمن اللازم لجمع جميع قسائم، وليكن الزمنَ اللازم لجمع القسيمة بعد جمع قسيمة. عندئذٍ . يُعدّ كلٌّ من و متغيرين عشوائيين. ويُلاحَظ أن احتمال الحصول على القسيمة الجديدة هو . ومن ثَمَّ يتبع التوزيعَ الهندسي بقيمة متوقعة . وبتطبيق خطية القيمة المتوقعة نحصل على:
إضافةً إلى ذلك، يمكن تعديل ما سبق تعديلًا طفيفًا لمعالجة الحالة التي جُمعت فيها بعض القسائم مسبقًا. ليكن عدد قسائم المجموعة مسبقًا، عندئذٍ:
تقديرات الذيل
وفي السياق ذاته، يمكن الحصول على تقدير أقوى لذيل من الجهة العليا على النحو الآتي، نرمز بالرمز للحدث الذي يعني عدم اختيار القسيمة في أول سحبات. عندئذٍ:
، يصبح .
ولذلك، من أجل: , we have
- وباستخدام متباينة بول على قسيمة، نحصل على:
- انظر كذلك
- معضلة يوم الميلاد
- الهوامش
- المراجع
- المراجع العربية
حساب التباين
- باستخدام استقلالية المتغيرات العشوائية نحصل على:
- إذ إن (راجع معضلة بازل).
- وللحصول على حد أعلى للاحتمال المطلوب باستخدام متباينة تشيبيشيف:
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟