SanBonne:
| name = مسألة جامع القسائم
| type = منفصل
| parameters = <math>ninmathbb N</math> – عدد أوجه النرد
| support = <math>kinmathbb N</math> – الأدوار اللازمة لتظهر الأوجه جميعها
<!– | pdf = <math>frac{(n-1)^{{k-1}}}{n^{k-1}}</math> –>
| cdf = <math>frac{n^{{k}}}{n^k}</math>
| mean = <math>nH_n</math>
<!– | variance = <math>n^2H^{(2)}_n-nH_n</math> –>
| التفرطح = <math>frac{2n^3H^{(3)}_n-3n^2H^{(2)}_n+nH_n}{left(n^2H^{(2)}_n-nH_nright)^{3/2}} underset nsim 6^{3/2}2frac{zeta(3)}{pi^3}</math>
| kurtosis = <math>frac{6n^4H^{(4)}_n-12n^3H^{(3)}_n+7n^2H^{(2)}_n-nH_n}{(n^2H^{(2)}_n-nH_n)^2}simfrac65</math>
| pgf = <math>G(z) = {frac nzchoose n}^{-1}</math>
| mgf = <math>{frac n{e^t}choose n}^{-1}</math>
| char = <math>{frac n{e^{it}}choose n}^{-1}</math>
}}
[[File:Coupon collector problem.svg|thumb|400px|رسم بياني لعدد القسائم {{تعبير رياضي مائل|n}} مقابل عدد الدورات (مثل الزمن) اللازمة لجمعهم جميعًا {{تعبير رياضي|”E”(”T”)}}]]
تشير ”’مسألة جامع القسائم”’ {{إنج|Coupon collector’s problem}} في [[نظرية الاحتمال]] إلى التحليل الرياضي لمسابقات “اجمع جميع [[قسيمة|القسائم]] وفز”، إذ تطرح المسألة السؤال الآتي: إذا احتوت كل علبة منتج معين (مثل حبوب الإفطار) قسيمةً، وتوفرت أنواع متعددة من القسائم، فما احتمال شراء أكثر من عدد معين من العلب لجمع القسائم المتنوعة كُلَّها؟
أيضًا، يمكن صياغة هذه المسألة صياغة أخرى وهي: إذا توفر عدد محدد (فرضًا {{تعبير رياضي مائل|n}}) من أنواع القسائم، فما [[قيمة متوقعة|القيمة المتوقعة]] للقسائم الواجب سحبها مع [[اعتيان|إعادة القسائم إلى المجموعة]] قبل أن تسحب كل قسيمة مرة واحدة على الأقل؟
يُظهر التحليل الرياضي للمسألة أن [[قيمة متوقعة|القيمة المتوقعة]] لعدد المحاولات المطلوبة تزداد بمعدل <math>Theta(nlog(n))</math>. {{ملا|تشير [[لوغاريتم|اللوغارتم]] هنا وفي المقالة ككل إلى [[لغارتم طبيعي|اللوغارتم الطبيعي]] لا إلى لوغارتم لأساس آخر. ويستدعي استعمال الرمز Θ هنا [[تمثيل O الكبرى]].}} تستلزم العملية مثلاً عند توفر 50 نوعًا مختلفًا نحو 225 محاولة،{{ملا|1= <math>E(50) = 50(1 + 1/2 + 1/3 + … + 1/50) = 224.9603</math> هو العدد المتوقع من المحاولات اللازمة لجمع جميع القسائم الخمسين. التقدير التقريبي: <math>nlog n+gamma n+1/2</math><br> ويُعطي التقدير التقريبي لهذا العدد المتوقع في هذه الحالة:<br><math>50log 50+50gamma+1/2 approx 195.6011+28.8608+0.5approx 224.9619</math>.}} لجمع جميع القسائم الخمسين. وأحيانًا تُعبر عن المشكلة بدلاً من ذلك باستخدام نرد متعدد الأوجه (ذو n وجهًا).
== وصف المسألة ==
يهدف الجامع للحصول على قسيمة واحدة من كل نوع من أنواع القسائم وعددها {{تعبير رياضي مائل|n}}. لتحقيق ذلك، يشتري علبًا من حبوب الإفطار. وكما يوضح الشكل أدناه، تحتوي كل علبة على قسيمة واحدة. في المثال، يشتري العلبة الأولى ويحصل فيها على القسيمة 1. ثم يشتري العلبة الثانية ويحصل على القسيمة 4. وفي عملية الشراء الثالثة، يحصل على القسيمة 1 مرة أخرى، ولذلك لا تتغير مجموعته؛ إذ يظل يمتلك القسيمةين 1 و4. ويواصل شراء علب حبوب الإفطار حتى يحصل على ملصق من كل نوع. ونفترض أن جميع القسائم متساوية الاحتمال، أي إن احتمال الحصول على أي نوع من أنواع القسائم عند شراء علبة هو {{كسر|1|”n”}}.
نرمز إلى {{تعبير رياضي مائل|T<sub>n</sub>}} بعدد العلب اللازم شراؤها لجمع القسائم كاملةً. ففي المثال أعلاه، <math>T_4=10</math>، لأن الجامع اشترى 10 علب من حبوب الإفطار قبل أن يحصل على القسائم الأربع. ومن البديهي أن الحصول على القسائم الأخيرة أصعب من الحصول على القسائم الأولى. ولدراسة هذه الظاهرة بمزيد من الدقة، نعرّف أيضًا [[المتغير العشوائي]] {{تعبير رياضي مائل|T<sub>n,k</sub>}}، الذي يمثل عدد علب حبوب الإفطار التي تُشترى قبل الحصول على {{تعبير رياضي مائل|k}} أنواع من القسائم من بين أنواع القسائم {{تعبير رياضي مائل|n}} في المجموعة. ففي المثال، <math>T_{4, 1}=1</math>، لأنه بعد عملية شراء واحدة نمتلك بالضرورة قسيمة واحدة؛ و<math>T_{4, 2}=2</math>، و<math>T_{4, 3}=5</math>، و<math>T_{4,4}=10</math>. ومن ثم فإن زمن {{تعبير رياضي مائل|T<sub>n</sub>}} اللازم للحصول على المجموعة الكاملة هو {{تعبير رياضي مائل|T_n,n}}. ويمكن اعتبار {{تعبير رياضي مائل|T<sub>n,k</sub>}} [[زمن توقف]]، إذ تُشترى علبة من حبوب الإفطار في كل خطوة زمنية.
[[ملف:Coupon collectors problem example.svg|مركز|إطار|1000 بك|مثال على مجموعة من 4 قسائم ممكنة: 1، 2، 3، 4. في المثال، نحصل في الخطوة 1 على القسيمة 1، وفي الخطوة 2 على القسيمة 4، وفي الخطوة 3 على القسيمة 1 مرة أخرى، وهكذا.]]
لتكن {{تعبير رياضي مائل|t<sub>n,i</sub>}} الزمن الإضافي اللازم للحصول على القسيمة الجديدة رقم {{تعبير رياضي مائل|i}}، مع العلم أننا نمتلك بالفعل {{تعبير رياضي|”i” – 1}} قسيمة مختلفة. ومن ثم <math>T_{n,k}=sum_{i=1}^k t_{n,i}</math>. وفي مثال الشكل أعلاه، لدينا <math>t_{4,1} = 1</math> (ويكون <math>t_{n,1}</math> مساويًا دائمًا لـ1)، و<math>t_{4,2} = 1</math>، و<math>t_{4,3} = 3</math>، و<math>t_{4,4} = 5</math>. وهنا لدينا <math>T_{4}=10</math> إذ اشترى الجامع في المثال 10 علب للحصول على المجموعة الكاملة المكوّنة من القسائم الأربع.
==الحل==
===حساب القيمة المتوقعة===
ليكن الزمن {{تعبير رياضي مائل|T}} هو الزمن اللازم لجمع جميع {{تعبير رياضي مائل|n}} قسائم، وليكن {{تعبير رياضي|”t”<sub>”i”</sub>}} الزمنَ اللازم لجمع القسيمة {{تعبير رياضي مائل|i}} بعد جمع {{تعبير رياضي|”i” − 1}} قسيمة. عندئذٍ <math>T=t_1 + cdots + t_n</math>. يُعدّ كلٌّ من {{تعبير رياضي مائل|T}} و{{تعبير رياضي|”t”<sub>”i”</sub>}} [[متغير عشوائي|متغيرين عشوائيين]]. ويُلاحَظ أن احتمال الحصول على القسيمة {{تعبير رياضي مائل|i}} ”’الجديدة”’ هو <math>p_i = frac{n – (i – 1)}{n} = frac{n – i + 1}n</math>. ومن ثَمَّ يتبع {{تعبير رياضي|”t”<sub>”i”</sub>}} [[توزيع هندسي|التوزيعَ الهندسي]] بقيمة متوقعة <math>frac{1}{p_i} = frac n{n – i + 1}</math>. وبتطبيق [[قيمة متوقعة|خطية القيمة المتوقعة]] نحصل على:
: <math>
begin{align}
operatorname{E}(T) & {}= operatorname{E}(t_1 + t_2 + cdots + t_n) \
& {}= operatorname{E}(t_1) + operatorname{E}(t_2) + cdots + operatorname{E}(t_n) \
& {}= frac{1}{p_1} + frac{1}{p_2} + cdots + frac{1}{p_n} \
& {}= frac{n}{n} + frac{n}{n-1} + cdots + frac{n}{1} \
& {}= n cdot left(frac{1}{1} + frac{1}{2} + cdots + frac{1}{n}right) \
& {}= n cdot H_n.
end{align}
</math>
حيث {{تعبير رياضي|”H”<sub>”n”</sub>}} هو [[عدد توافقي|العدد التوافقي]] من الرتبة {{تعبير رياضي مائل|n}}. وباستخدام [[تحليل مقارب|التحليل المقارب]] للأعداد التوافقية نحصل على:
: <math>
operatorname{E}(T) = n cdot H_n = n log n + gamma n + frac{1}{2} + O(1/n),
</math>
هو <math>gamma approx 0.5772156649</math> [[ثابت أويلر]].
وباستخدام [[متباينة ماركوف]] للحصول على حد أعلى للاحتمال المطلوب:
: <math>operatorname{P}(T geq cn H_n) le frac{1}{c}.</math>
يمكن تعديل ما سبق تعديلًا طفيفًا لمعالجة الحالة التي جُمعت فيها بعض القسائم مسبقًا. ليكن {{تعبير رياضي مائل|k}} عدد قسائم المجموعة مسبقًا، عندئذٍ:
: <math>
begin{align}
operatorname{E}(T_k) & {}= operatorname{E}(t_{k+1} + t_{k+2} + cdots + t_n) \
& {}= n cdot left(frac{1}{1} + frac{1}{2} + cdots + frac{1}{n-k}right) \
& {}= n cdot H_{n-k}
end{align}
</math>
وعند <math>k=0</math> نستعيد النتيجة الأصلية (<math>operatorname{E}(T) = n cdot H_n</math>)
===حساب التباين===
باستخدام استقلالية المتغيرات العشوائية {{تعبير رياضي|”t”<sub>”i”</sub>}} نحصل على:
:<math>
begin{align}
operatorname{Var}(T)& {}= operatorname{Var}(t_1 + cdots + t_n) \
& {} = operatorname{Var}(t_1) + operatorname{Var}(t_2) + cdots + operatorname{Var}(t_n) \
& {} = frac{1-p_1}{p_1^2} + frac{1-p_2}{p_2^2} + cdots + frac{1-p_n}{p_n^2} \
& {} = left(frac{n^2}{n^2} + frac{n^2}{(n-1)^2} + cdots + frac{n^2}{1^2}right) – left(frac{n}{n} + frac{n}{n-1} + cdots + frac{n}{1}right) \
& {} = n^2 cdot left(frac{1}{1^2} + frac{1}{2^2} + cdots + frac{1}{n^2} right) – n cdot left(frac{1}{1} + frac{1}{2} + cdots + frac{1}{n} right)\
& {} < frac{pi^2}{6} n^2
end{align}
</math>
إذ إن <math>frac{pi^2}6=frac{1}{1^2}+frac{1}{2^2}+cdots+frac{1}{n^2}+cdots</math> (راجع [[معضلة بازل]]).
وللحصول على حد أعلى للاحتمال المطلوب باستخدام [[متباينة تشيبيشيف]]:
:<math>operatorname{P}left(|T- n H_n| geq cnright) le frac{pi^2}{6c^2}.</math>
=== أعداد ستيرلنغ ===
ليكن المتغير العشوائي {{تعبير رياضي مائل|X}} عدد مرات رمي النرد قبل ظهور جميع الوجوه.
تُعرَّف القوة الجزئية بالعلاقة <math>a^{{b}}=a!left{{batop a}right}</math> ،حيث <math>left{{batop a}right}</math> هو [[عدد ستيرلينغ|عدد ستيرلنغ من النوع الثاني]].<ref>{{استشهاد بدورية محكمة | الأخير = Rus | الأول = Mircea Dan | عنوان = Yet another note on notation | صحيفة = International Journal of Mathematical Education in Science and Technology | ناشر = Informa UK Limited | تاريخ = 3 Aug 2026 | issn = 0020-739X | دوي = 10.1080/0020739x.2026.2701739 | صفحات = 1–17}}</ref>
تتقابل تسلسلات {{تعبير رياضي مائل|k}} من رميات النرد مع الدوال <math>krightarrow n</math> التي يبلغ عددها <math>n^k</math>، في حين يبلغ عدد الدوال الشاملة (التي تصيب كل وجه مرةً على الأقل) <math>n^{{k}}</math>، ومن ثَمَّ يكون احتمال ظهور جميع الوجوه في غضون {{تعبير رياضي مائل|k}} رميات هو <math>P(Xle k)=frac{n^{{k}}}{n^k}</math>. وبتطبيق علاقة التكرار لأعداد ستيرلنغ، يكون احتمال أن تكفي {{تعبير رياضي مائل|k}} رميات بالضبط هو <math>P(X=k)=frac{n^{{k}}}{n^k}-frac{n^{{k-1}}}{n^{k-1}}=frac{(n-1)^{{k-1}}}{n^{k-1}}</math>
===الدوال المولدة===
يُنتج تعويض <math>z</math> ب<math>1+z</math> في الدالة المولدة الاحتمالية{{ملا|({{اللغة|en|Probability generating function}})}} دالة مولدة عادية{{ملا|({{اللغة|en|ordinary generating function}}) <ref group=”عر”>{{استشهاد بويكي بيانات|Q108593221|ص=495}}</ref>}} ل<math>Eleft[{Xchoose k}right]</math>. وباستخدام [[تحليل الكسور الجزئية]] <math>{frac1x-1choose n}^{-1}=sum_{k=0}^n{nchoose k}frac{(-1)^{n-k}}{1-kx}</math>، يمكن أخذ التوسع:
:<math>begin{aligned}&{frac n{x+1}choose n}^{-1}\
=&sum_{i=0}^n{nchoose i}frac{(-1)^{n-i}}{1-i(1-frac n{x+1+n})}\
=&sum_{i=0}^n{nchoose i}(-1)^{n-i}left(frac{1+n}{1+n-i}+insum_{k=1}^inftyfrac{(i-1)^{k-1}}{(n+1-i)^{k+1}}x^kright)end{aligned}</math>
لذلك، فمن من أجل <math>k>0</math>:
:<math>Eleft[{Xchoose k}right]=nsum_{i=0}^n{nchoose i}(-1)^{n-i}ifrac{(i-1)^{k-1}}{(n+1-i)^{k+1}}</math>
بالنسبة إلى دالة مولدة عادية {{تعبير رياضي مائل|f}}، ولأن <math>left(frac x{1-x}right)^i=sum_{n=0}^infty{k-1choose i-1}x^k</math>، فإن تغييرًا{{ملا|({{اللغة|en|variation}})}} من [[تحويل ثنائي|التحويل الثنائي]] ينتج <math>[x^k]fleft(frac x{1+x}right)=sum_{i=0}^k{k-1choose i-1}(-1)^{k-i}[x^i]f(x)</math>. (وتحديداً، إذا كان<math>{frac n{x+1}choose n}^{-1}=fleft(frac x{1+x}right)</math>, <math>f(x)={n-nxchoose n}^{-1}</math>.)
وبإعادة كتابة معامل التحويل الثنائي عبر [[دالة غاما]] وتوسيعه على هيئة <math>exp</math> لمتسلسلة {{وإو|دالة غاما المتعددة|Polygamma function}} (بدلالة [[عدد توافقي|الأعداد التوافقية المعممة]])، نجد أنَّ:
:<math>left[frac{x^i}{i!}right]{n-xchoose n}^{-1}=sum_{Pinmathrm{perms}(i)}prod_{cin P}H^{(|c|)}_n</math>
ومن ثَمَّ:
:<math>Eleft[{Xchoose k}right]=sum_{i=0}^k{k-1choose i-1}(-1)^{k-i}frac{n^i}{i!}sum_{Pinmathrm{perms}(i)}prod_{cin P}H^{(|c|)}_n</math>
ويمكن أيضاً كتابة هذه الصيغة بدلالة الحدوديات الهابطة وعدد لاه{{ملا|({{اللغة|en|Lah number}}) (أي الأعداد المؤشرة وغير المؤشرة)}} على النحو الآتي:
:<math>E[x^underline k]=sum_{i=0}^kL(k,i)(-1)^{k-i}n^isum_{Pinmathrm{perms}(i)}prod_{cin P}H^{(|c|)}_n</math>
ويمكن الحصول على [[عزم (رياضيات)|العزوم الخام]] للتوزيع من العزوم الهابطة عبر تحويل ستيرلنغ{{ملا|({{اللغة|en|Stirling transform}})}}؛ واستناداً إلى المتطابقة:
: <math>left{{Katop i}right}(-1)^K=sum_{k=0}^Kleft{{Katop k}right}L(k,i)(-1)^k</math>
ينتج:
:<math>E[x^k]=sum_{i=0}^kleft{{katop i}right}(-1)^{k-i}n^i!!sum_{Pinmathrm{perms}(i)}prod_{cin P}H^{(|c|)}_n</math>
==تقديرات الذيل==
يمكن الحصول على تقدير أقوى لذيل من الجهة العليا على النحو الآتي، نرمز بالرمز <math>{Z}_i^r</math> [[حدث (نظرية الاحتمالات)|للحدث]] الذي يعني عدم اختيار القسيمة <math>i</math> في أول <math>r</math> سحبات. عندئذٍ:
<math>r = beta n log n</math>، يصبح <math>Pleft [ {Z}_i^r right ] le e^{(-beta n log n ) / n} = n^{-beta}</math>.
ولذلك، من أجل: <math>r = beta n log n</math>, we have <math>Pleft [ {Z}_i^r right ] le e^{(-beta n log n ) / n} = n^{-beta}</math>
وباستخدام متباينة بول {{ملا|({{اللغة|en|Boole’s inequality}})}} على <math>n</math> قسيمة، نحصل على:
:<math>
begin{align}
Pleft [ T > beta n log n right ] = P left [ bigcup_i {Z}_i^{beta n log n} right ] le n cdot P [ {Z}_1^{beta n log n} ] le n^{-beta + 1}.
end{align}
</math>
== انظر أيضًا ==
* [[معضلة يوم الميلاد]]
==الهوامش ==
{{ملاحظات}}
==المراجع==
===الاستشهاد===
; المراجع العربية
{{مراجع|مجموعة=عر|2}}
; المراجع الأجنبية
{{مراجع|30em|2}}
{{شريط سفلي مسائل الاحتمالات}}
{{شريط بوابات|إحصاء|الاحصاء والاحتمال|تحليل رياضي|رياضيات}}
[[تصنيف:مسائل رياضيات]]
[[تصنيف:مبرهنات في الاحتمالات]]
