السهام والنرد والعملات المعدنية: خوارزميات التوزيع المنفصلة

سألت ذات مرة Stack Overflow سؤالًا عن بنية البيانات للنرد الغش . على وجه الخصوص ، كنت مهتمًا بالإجابة على هذا السؤال: "إذا كان لدينا عظم ذو وجه n ، قد يكون وجهه عرضة للسقوط p _i . ما هي بنية البيانات الأكثر فعالية لمحاكاة لفات مثل هذا العظم؟ "

يمكن استخدام هيكل البيانات هذا في العديد من المهام. على سبيل المثال ، يمكنك استخدامه لمحاكاة لفات عرافة صادقة ، وتعيين الاحتمالية $$$\ frac {1} {6}$ كل جانب من العظام ، أو لمحاكاة عملة عادلة عن طريق تقليد عظم ثنائي ، واحتمال السقوط من كل جانب يساوي $$$\ frac {1} {2}$ . يمكنك أيضًا استخدام بنية البيانات هذه لمحاكاة مجموع عظام سداسية عشرية مباشرة عن طريق إنشاء عظم مكون من 11 جانبًا (مع الوجوه 2 ، 3 ، 4 ، ... ، 12) ، لكل وجه وزن احتمالي يتوافق مع لفات عظامين صادقتين. ومع ذلك ، يمكنك أيضًا استخدام بنية البيانات هذه لمحاكاة عظام الغش. على سبيل المثال ، إذا كنت تلعب الكرابس مع عظم ، وهو ، كما تعلمون ، ليس صادقًا تمامًا ، فيمكنك استخدام بنية البيانات هذه لمحاكاة الكثير من لفات العظام وتحليل الاستراتيجية المثلى. يمكنك أيضًا محاولة محاكاة عجلة روليت غير كاملة بالمثل.

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

أعجبني الجواب الذي تلقيته على Stack Overflow لسببين. أولاً ، في الحل ، تم نصحني باستخدام تقنية قوية تسمى طريقة الاسم المستعار ، والتي ، مع بعض الافتراضات المعقولة حول نموذج الآلة ، قادرة ، بعد مرحلة بسيطة من التحضير الأولي ، لمحاكاة لفات العظام بمرور الوقت $$$O (1)$ . ثانيًا ، لقد فوجئت أكثر بأن هذه الخوارزمية معروفة منذ عقود ، لكنني لم ألتق بها أبدًا! بالنظر إلى مقدار الوقت الحسابي الذي يتم إنفاقه على المحاكاة ، يتوقع المرء أن هذه التقنية معروفة على نطاق أوسع. أعطتني بعض الاستفسارات على Google الكثير من المعلومات حول هذه التقنية ، لكنني لم أجد موقعًا واحدًا اجتمع فيه فهم وتفسير بديهي لهذه التقنية.

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

الدخول

قبل الانتقال إلى التفاصيل المحددة للتقنيات المختلفة ، لنقم أولاً بتوحيد المصطلحات والتدوين.

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

لوصف التوزيع الاحتمالي المنفصل (عظم الغشاش) ، سنفترض أن لدينا مجموعة من الاحتمالات $$$p_0 ، p_1 ، ... ، p_ {n - 1}$ المتعلقة بالنتائج $$$0 ، 1 ، ... ، n - 1$ . على الرغم من أن النتائج يمكن أن تكون أي (نسر / ذيول ، أرقام على العظام ، والألوان ، وما إلى ذلك) ، من أجل البساطة ، سأعتبر النتيجة نوعًا من الرقم الحقيقي الإيجابي المطابق لمؤشر معين.

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

بعد ذلك ، سأفترض أنه يمكن إجراء جميع العمليات التالية في وقت ثابت:

• إضافة. الطرح والضرب والقسمة والمقارنة بين الأرقام الحقيقية التعسفية . سنحتاج إلى القيام بذلك للتلاعب بالاحتمالات. قد يبدو هذا افتراضًا جريئًا ، ولكن إذا افترضنا أن دقة أي رقم حقيقي محدودة ببعض حدود حجم كلمة الآلة (على سبيل المثال ، ضعف 64 بت على جهاز 32 بت) ، لكنني لا أعتقد أنه غير معقول للغاية.
• توليد رقم حقيقي موحد في الفترة [0 ، 1). لمحاكاة العشوائية ، نحتاج إلى بعض مصادر القيم العشوائية. أفترض أنه يمكننا توليد عدد حقيقي من الدقة التعسفية في وقت ثابت. هذا يتجاوز بكثير قدرات الكمبيوتر الحقيقي ، ولكن يبدو لي أن هذا لأغراض مقبولة من هذا النقاش. إذا اتفقنا على التضحية بجزء بسيط من الدقة من خلال القول بأن ضعف IEEE-754 مزدوج في الفاصل الزمني [0 ، 1] ، فسوف نفقد الدقة بالفعل ، ولكن من المحتمل أن تكون النتيجة دقيقة بما يكفي لمعظم التطبيقات.
• حساب العدد الصحيح (التقريب للأسفل) لعدد حقيقي. هذا مقبول إذا افترضنا أننا نعمل مع IEEE-754 double ، ولكن بشكل عام ، مثل هذا الشرط لجهاز الكمبيوتر غير ممكن.

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

محاكاة العظام صادقة

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

لهذه الحالة الخاصة ، هناك خوارزمية بسيطة وأنيقة وفعالة لمحاكاة النتيجة. تستند الخوارزمية إلى الفكرة التالية: لنفترض أنه يمكننا إنشاء أرقام حقيقية عشوائية وموزعة بشكل منتظم في الفاصل الزمني $$$[0، 1)$ . يمكن توضيح هذا الفاصل الزمني على النحو التالي:


الآن إذا أردنا الإقلاع عن التدخين $$$n$ عظم الأوجه ، ثم طريقة واحدة هي تقسيم الفاصل الزمني $$$[0، 1)$ على $$$n$ مناطق متساوية الحجم ، لكل منها طول $$$\ frac {1} {n}$ . يبدو هذا:


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


ثم يمكننا القول أن 2 سقطت على العظم (إذا افترضنا أن حواف العظم مفهرسة من الصفر).

من السهل بيانيًا رؤية المنطقة التي لها قيمة عشوائية ، ولكن كيف يمكننا ترميزها في خوارزمية؟ وهنا نستفيد من حقيقة أن هذه عظمة صادقة. لأن جميع الفترات متساوية الحجم ، وهي $$$\ frac {1} {n}$ ، ثم يمكننا أن نرى ما هو أعظم قيمة $$$i$ مثل هذا $$$\ frac {i} {n}$ ليس أكثر من قيمة تم إنشاؤها عشوائيًا (دعنا نسمي هذه القيمة س). قد تلاحظ أنه إذا أردنا العثور على القيمة القصوى ، مثل ذلك $$$\ frac {i} {n} \ le x$ ، فهذا يشبه إيجاد القيمة القصوى $$$n$ مثل هذا $$$i \ le xn$ . ولكن هذا بحكم التعريف يعني ذلك $$$i = \ lfloor xn \ rfloor$ ، أكبر عدد صحيح موجب ليس أكبر من xn. لذلك ، يقودنا هذا إلى خوارزمية محاكاة عظام نقية (بسيطة جدًا) للعظام:

خوارزمية: محاكاة العظام صادقة

1. توليد قيمة عشوائية موزعة بشكل موحد $$$x$ في النطاق $$$[0، 1)$ .
2. العودة $$$\ lfloor xn \ rfloor$ .

بالنظر إلى افتراضاتنا أعلاه حول الحسابات ، يتم تشغيل هذه الخوارزمية في الوقت المناسب $$$O (1)$ .

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

محاكاة عظم الغش مع عظام صادقة

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

من القسم السابق ، من الواضح بشكل بديهي أنه لمحاكاة رمي عظم الغش ، يكفي لتقسيم الفاصل الزمني $$$[0، 1)$ إلى قطع ، ثم تحديد أي جزء نصل إليه. ومع ذلك ، في الحالة العامة ، يمكن أن يكون هذا أكثر تعقيدًا مما يبدو. لنفترض أن لدينا رباعي الأسطح مع احتمالات الوجه $$$\ frac {1} {2}$ ، $$$\ frac {1} {3}$ ، $$$\ frac {1} {12}$ و $$$\ frac {1} {12}$ (يمكننا التأكد من أن هذا هو التوزيع الاحتمالي الصحيح ، لأن $$$\ frac {1} {2} + \ frac {1} {3} + \ frac {1} {12} + \ frac {1} {12} = \ frac {6} {12} + \ frac {4 } {12} + \ frac {1} {12} + \ frac {1} {12} = \ frac {12} {12}$ ) إذا قسمنا الفاصل الزمني $$$[0، 1)$ إلى أربعة أجزاء من هذه الأحجام ، ثم نحصل على ما يلي:


للأسف ، نحن عالقون في هذه الخطوة. حتى لو كنا نعرف رقمًا عشوائيًا في الفاصل الزمني $$$[0، 1)$ ، ثم لا توجد حيل رياضية بسيطة لتحديد الجزء الذي وقع فيه هذا الرقم تلقائيًا. لا أريد أن أقول أن هذا مستحيل - كما سترى ، يمكننا استخدام العديد من الحيل الممتازة - ولكن لا يوجد لدى أي منها البساطة الرياضية لخوارزمية رمي العظام الصادقة.

ومع ذلك ، يمكننا تكييف التقنية المستخدمة لعظام صادقة للعمل في هذه الحالة أيضًا. لنأخذ العظم الذي نوقش أعلاه كمثال. احتمال سقوط الحواف $$$\ frac {1} {2}$ ، $$$\ frac {1} {3}$ ، $$$\ frac {1} {12}$ و $$$\ frac {1} {12}$ . إذا أعدنا كتابة ذلك بحيث يكون لجميع الأعضاء قاسم مشترك ، نحصل على القيم $$$\ frac {6} {12}$ ، $$$\ frac {4} {12}$ ، $$$\ frac {1} {12}$ و $$$\ frac {1} {12}$ . لذلك ، يمكننا إدراك هذه المهمة على النحو التالي: بدلاً من رمي عظم رباعي السطوح مع احتمالات مرجحة ، لماذا لا ترمي عظمة صادقة من 12 جانبًا ، على حوافها قيم مكررة؟ نظرًا لأننا نعرف كيفية محاكاة العظام الصادقة ، فسيكون هذا مشابهًا للفصل الزمني $$$[0، 1)$ إلى قطع بهذه الطريقة:


ثم نقوم بتعيينها لنتائج مختلفة كما يلي:


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


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

في مرحلة التهيئة ، نبدأ بالبحث عن المضاعف المشترك الأقل بين جميع الاحتمالات المعطاة لحواف العظام (في مثالنا ، LCL هو 12). NOC مفيد هنا لأنه يتوافق مع أصغر القاسم المشترك الذي يمكننا استخدامه لجميع الكسور ، وبالتالي عدد وجوه العظم النظيف الجديد الذي سنقوم بتدحرجه. بعد تلقي شهادة عدم الممانعة هذه (نشير إليها بواسطة L) ، يجب علينا تحديد عدد الوجوه للعظم الجديد الذي سيتم توزيعه على كل وجه من عظام الغشاش الأصلية. في مثالنا ، الوجه ذو الاحتمال $$$\ frac {1} {2}$ يحصل على ستة جوانب للعظم الجديد منذ ذلك الحين $$$\ frac {1} {2} \ ضرب 12 = 6$ . وبالمثل ، الحزب مع احتمال $$$\ frac {1} {3}$ 4 وجوه منذ ذلك الحين $$$\ frac {1} {3} \ ضرب 12 = 4$ . في شكل أكثر عمومية ، إذا كان L هو LCL من الاحتمالات ، و $$$p_i$ هو احتمال الوجه $$$i$ العظام ، ثم نسلط الضوء على الوجوه $$$i$ عظم شربي الأصلي $$$L \ cdot p_i$ جوانب العظام الصادقة.

هنا هو الكود الزائف للخوارزمية أعلاه:

الخوارزمية: محاكاة عظم الغش بعظمة صادقة

• التهيئة :
  
  1. أوجد شهادة عدم الممانعة لمقام الاحتمالات $$$p_0 ، p_1 ، ... ، p_ {n-1}$ ؛ تدل عليه $$$L$
  2. حدد مصفوفة $$$A$ الحجم $$$L$ لمقارنة نتائج لفات العظام الصادقة مع لفات العظام الأصلية.
  3. لكل وجه $$$i$ من العظم الأولي ، نقوم بما يلي بأي ترتيب:
     
     1. نحن نعين ما يلي $$$L \ cdot p_i$ العناصر $$$A$ القيمة $$$i$ .
• الجيل :
  
  1. نحن نولد رميًا صادقًا للعظم $$$L$ - عظم الوجه اتصل بالوجه $$$S$ .
  2. العودة $$$A [S]$ .

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

ومع ذلك ، يمكن أن تكون خطوة التهيئة مكلفة للغاية. لكي تعمل هذه الخوارزمية ، نحتاج إلى تخصيص مساحة لصفيف بحجم NLC من مقامات جميع كسور الإدخال. في مثالنا ( $$$\ frac {1} {2}$ ، $$$\ frac {1} {3}$ ، $$$\ frac {1} {12}$ ، $$$\ frac {1} {12}$ ) ، فهو 12 ، بالنسبة لقيم الإدخال الأخرى ، يمكن أن تكون القيم سيئة بشكل مرضي. على سبيل المثال ، دعنا ننظر إلى الكسور $$$\ frac {999999} {1،000،000}$ و $$$\ frac {1} {1000000}$ . شهادة عدم الممانعة من القواسم تساوي مليون ، لذا يجب أن يكون هناك مليون عنصر في جدولنا!

لسوء الحظ ، يمكن أن تكون الأمور أسوأ. في المثال السابق ، يمكننا على الأقل أن "نتوقع" أن الخوارزمية تستهلك الكثير من الذاكرة ، لأن كلا مقام الكسور يساوي مليون. ومع ذلك ، قد يكون لدينا العديد من الاحتمالات التي تكون شهادة عدم الممانعة لها أكبر بكثير من كل قاسم فردي. على سبيل المثال ، دعونا نلقي نظرة على الاحتمالات $$$\ frac {1} {15}$ ، $$$\ frac {1} {10}$ ، $$$\ frac {5} {6}$ . هنا تكون شهادة عدم الممانعة من القواسم 30 ، أي أكثر من أي قاسم. يعمل التصميم هنا بسبب $$ ، $$ و $$ ؛ بمعنى آخر ، كل قاسم هو نتاج أساسيتين يتم اختيارهما من مجموعة من ثلاث قيم. لذلك ، فإن شهادة عدم الممانعة الخاصة بهم هي نتاج كل هذه الأعداد الأولية ، حيث يجب أن يكون كل قاسم مقسومًا على شهادة عدم الممانعة. إذا قمنا بتعميم هذا البناء والنظر في أي مجموعة من $$$k$ الأعداد الأولية وتأخذ كسرًا واحدًا لكل من المنتجات الزوجية لهذه الأعداد الأولية ، فإن شهادة عدم الممانعة ستكون أكثر بكثير من كل قاسم فردي. في الواقع ، أحد أفضل الحدود العليا التي يمكننا الحصول عليها لشهادة عدم الممانعة ستكون $$$O (\ prod_ {i = 0} ^ n {d_i})$ أين $$$d_i$ هو المقام $$$i$ هذا الاحتمال. هذا لا يسمح باستخدام مثل هذه الخوارزمية في الظروف الحقيقية ، عندما تكون الاحتمالات غير معروفة مقدمًا ، لأن الذاكرة المطلوبة لتخزين جدول الحجم $$$O (\ prod_ {i = 0} ^ n {d_i})$ ، يمكن أن يتحول بسهولة إلى أكثر من الحجم الذي يمكن أن يتناسب مع ذاكرة الوصول العشوائي.

وبعبارة أخرى ، في كثير من الحالات ، تعمل هذه الخوارزمية بشكل جيد. إذا كانت جميع الاحتمالات متشابهة ، فإن جميع الاحتمالات التي تم الحصول عليها عند المدخلات متساوية $$$\ frac {1} {n}$ بالنسبة للبعض $$$n$ . ثم يساوي مقام NOC $$$n$ ، ونتيجة لذلك ، فإن العظام النزيهة ستلقى $$$n$ الوجوه ، وكل وجه من العظم الأصلي سوف يتوافق مع جانب واحد من العظم الصادق. لذلك ، وقت التهيئة $$$O (n)$ . يمكن تصوير هذا بيانياً على النحو التالي:


هذا يعطينا المعلومات التالية حول الخوارزمية:

خوارزمية	وقت التهيئة		وقت الجيل		احتلت الذاكرة
	الأفضل	الأسوأ	الأفضل	الأسوأ	الأفضل	الأسوأ
الصدق العظام شارلر العظام	$$$\ ثيتا (ن)$	$$$O (\ prod_ {i = 0} ^ n {d_i})$	$$$\ Theta (1)$		$$$\ ثيتا (ن)$	$$$O (\ prod_ {i = 0} ^ n {d_i})$

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

محاكاة عملة غير متماثلة

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

مهمة بسيطة ولكنها مفيدة بشكل مدهش هي محاكاة عملة غير متماثلة باستخدام مولد رقم عشوائي. إذا كان لدينا عملة مع احتمال وجود نسر $$$p_ {heads}$ ثم كيف يمكننا محاكاة رمي هذه العملة غير المتماثلة؟

في وقت سابق ، قمنا بتطوير نهج بديهي واحد: التقسيم الفاصل $$$[0، 1)$ على تسلسل من هذه المناطق التي تظهر عند اختيار قيمة عشوائية في الفاصل الزمني في بعض المناطق باحتمال يساوي حجم المنطقة. لمحاكاة عملة غير متماثلة باستخدام قيمة عشوائية موزعة بشكل موحد في الفاصل الزمني $$$[0، 1)$ يجب علينا كسر الفاصل الزمني $$$[0، 1)$ كما يلي:


ثم قم بتوليد قيمة عشوائية موزعة بشكل منتظم في الفاصل الزمني $$$[0، 1)$ لمعرفة المنطقة التي توجد فيها. لحسن الحظ ، لدينا نقطة تقسيم واحدة فقط ، لذلك من السهل جدًا تحديد المنطقة التي تكون فيها النقطة ؛ إذا كانت القيمة أقل $$$p_ {heads}$ ، ثم سقط النسر على العملة ، وإلا - ذيول. الرمز الزائف:

الخوارزمية: محاكاة عملة غير متماثلة

1. توليد قيمة عشوائية موزعة بشكل منتظم في الفاصل الزمني $$$[0، 1)$ .
2. إذا $$$x <p_ {heads}$ ، أرجع "النسر".
3. إذا $$$x \ ge p_ {heads}$ ، الذيول العودة.

نظرًا لأنه يمكننا إنشاء قيمة عشوائية موزعة بشكل منتظم في الفاصل الزمني $$$[0، 1)$ في الوقت المناسب $$$O (1)$ ، ويمكننا أيضًا مقارنة الأرقام الحقيقية لـ $$$O (1)$ ، ثم تعمل هذه الخوارزمية في الوقت المناسب $$$O (1)$ .

محاكاة عظام صادقة باستخدام عملات غير متماثلة

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

تصميم لمحاكاة عملة غير متماثلة يقسم الفاصل الزمني$$[ 0 ، 1 ) إلى منطقتين - منطقة "النسور" ومنطقة "ذيول" بناءً على احتمال سقوط النسور على العظام. لقد رأينا بالفعل خدعة مماثلة تستخدم لمحاكاة صادقة$[0, 1)$$$ن- عظم الأوجه: الفاصل$n$$$[ 0 ، 1 ) تم تقسيمها إلى$[0, 1)$$$n المساحات المتساوية. على سبيل المثال ، عند رمي عظم رباعي السطوح ، حصلنا على الفصل التالي:$n$


لنفترض الآن أننا مهتمون بمحاكاة لفة من هذا العظم النزيه باستخدام مجموعة من العملات غير المتماثلة. أحد الحلول هو كما يلي: تخيل أننا نتجول في هذه المناطق من اليسار إلى اليمين ، في كل مرة نسأل عما إذا كنا نريد التوقف في المنطقة الحالية ، أو إذا كنا سننتقل. على سبيل المثال ، لنفترض أننا نريد تحديد إحدى هذه المناطق عشوائيًا. بدءًا من أقصى اليسار ، سنقلب عملة غير متماثلة ، تخبرنا ما إذا كان يجب أن نتوقف في هذه المنطقة ، أم نستمر في المضي قدمًا. نظرًا لأننا نحتاج إلى الاختيار من كل هذه المجالات بشكل موحد مع الاحتمالية$$14 ، ثم يمكننا القيام بذلك عن طريق رمي عملة غير متماثلة ، والنسور التي تسقط باحتمال$\frac{1}{4}$$$$\frac{1}{4}$ .إذا سقط نسر ، فإننا نتوقف في المنطقة الحالية. خلاف ذلك ، ننتقل إلى المنطقة التالية.

إذا هبطت العملات المعدنية ، نجد أنفسنا في المنطقة الثانية ونطلب مرة أخرى ما إذا كان يجب علينا تحديد هذه المنطقة مرة أخرى أو الاستمرار في التحرك. قد تعتقد أنه لهذا السبب يجب علينا رمي عملة أخرى باحتمال وجود نسر$$14 ، ولكن في الواقع هذا ليس صحيحا! لرؤية الخلل في هذا المنطق ، يجب أن نصل إلى وضع شديد - إذا قمنا في كل منطقة برمي عملة يسقط عليها النسر باحتمال$\frac{1}{4}$$$14 ، أي أن هناك فرصة ضئيلة بأن العملة في كل منطقة سوف تسقط ذيول ، أي أنه سيتعين علينا التخلي عن جميع المناطق. عند التحرك عبر المناطق ، نحتاج إلى حد ما الاستمرار في زيادة احتمال سقوط النسر على عملة معدنية. في المواقف الشديدة ، إذا وجدنا أنفسنا في المنطقة الأخيرة ، فيجب أن يكون للنسر نسر مع احتمال$\frac{1}{4}$$$1 ، لأنه إذا رفضنا جميع المجالات السابقة ، فسيكون القرار الصحيح هو التوقف في المنطقة الأخيرة. لتحديد الاحتمالية التي يجب أن تقوم بها عملتنا غير المتماثلة برمي نسر بعد تخطي المنطقة الأولى ، نحتاج إلى ملاحظة أنه بعد تخطي المنطقة الأولى لم يتبق سوى ثلاثة. بينما ندير عظمة صادقة ، نحتاج إلى اختيار كل من هذه المجالات الثلاثة باحتمال$1$

$$$\frac{1}{3}$ . لذلك ، يبدو أنه يجب أن يكون لدينا عظمًا ثانيًا يسقط عليه النسر باحتمال $$$\frac{1}{3}$ . باستخدام منطق مماثل ، يمكن أن نفهم أنه عندما تظهر ذيول في المنطقة الثانية من الشبكة في المنطقة الثالثة ، يجب أن تسقط العملة مع $$12 ، وفي المنطقة الأخيرة - مع احتمال$\frac{1}{2}$$$$1$ .

يقودنا هذا الفهم البديهي إلى الخوارزمية التالية. لاحظ أننا لم نناقش صحة أو خاطئ هذه الخوارزمية. قريبا سنفعل ذلك.

الخوارزمية: محاكاة العظام الصادقة باستخدام العملات المعدنية غير المتماثلة

1. ل $$أنا = 0 إلى$i = 0$$$$n - 1$ :
   
   1. رمي عملة غير متماثلة مع احتمال وجود نسر $$$\frac{1}{n - i}$ .
   2. إذا سقط النسر ، فارجع $$$i$ .

هذه الخوارزمية بسيطة ، وفي أسوأ الحالات ، يتم تشغيلها في الوقت المناسب. $$$O(n)$ .ولكن كيف نتحقق مما إذا كانت صحيحة؟ لمعرفة ذلك ، نحتاج إلى النظرية التالية:

نظرية: الخوارزمية أعلاه ترجع الجانب$$أنا مع الاحتمال$i$$$1ن لأي اختيار$\frac{1}{n}$$$$i$ .

الدليل: ضع في اعتبارك أي ثابت$$$n \ge 0$ . باستخدام الحث القوي ، نثبت أن كل من $$ن الوجوه لها احتمال الاختيار$n$$$$\frac{1}{n}$ .

على سبيل المثال ، نظهر أن الوجه $$0 النرد لديه احتمال الاختيار$0$$$$\frac{1}{n}$ . لكن هذا يتبع مباشرة من الخوارزمية نفسها - نختار وجه 0 إذا كان على عملة غير متماثلة مع احتمال وجود نسر $$$\frac{1}{n}$ , $$$\frac{1}{n}$ .

$$$0, 1, 2, ..., k - 1$ , $$$\frac{1}{n}$ $$$k$ . $$$k$ , $$$k$ , $$$\frac{1}{n - k}$ . $$$k$ $$$\frac{1}{n}$ , , $$ك يعرف بأنه$k$$$$\frac{k}{n}$ . هذا يعني أن احتمال أن الخوارزمية لا تحدد واحدة من الأولى $$يواجه k يساوي$k$$$$1 - \frac{k}{n} = \frac{n}{n} - \frac{k}{n} = \frac{n - k}{n}$ . أي احتمال اختيار وجه $$ك يعرف بأنه$k$$$ن - كرقم 1ن - ك =1ن ، الذي سيظهر. وهكذا ، يتم اختيار كل وجه من العظام بالتساوي وبشكل عشوائي.$\frac{n - k}{n} \frac{1}{n - k} = \frac{1}{n}$

بالطبع ، الخوارزمية غير فعالة تمامًا - باستخدام التقنية الأولى ، يمكننا محاكاة لفة من النرد النزيه في الوقت المناسب $$يا ( 1 ) ! ولكن يمكن استخدام هذه الخوارزمية كنقطة انطلاق لخوارزمية فعالة بما فيه الكفاية لمحاكاة عظم الغش باستخدام عملات غير متماثلة.$O(1)$

محاكاة عظم Shuler باستخدام العملات غير المتماثلة

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

دعونا نرى كيف يمكنك استخدام هذه التقنية لمحاكاة رمي عظم الغش. نستخدم مثالنا مع الاحتمالات$$$\frac{1}{2}$ ، $$$\frac{1}{3}$ ، $$$\frac{1}{12}$ ، $$$\frac{1}{12}$ . هو ، إذا كنت لا تتذكر ، يقسم الفاصل الزمني $$[ 0 ، 1 ) على النحو التالي:$[0, 1)$


الآن دعونا نفكر في كيفية محاكاة مثل عظم الغش باستخدام عملات معدنية غير متماثلة. يمكننا البدء برمي قطعة نقدية باحتمال وجود نسر$$12 لتحديد ما إذا كان يجب أن نرجع الوجه 0. إذا وقع نسر على هذه العملة ، فلا بأس! لقد انتهينا. خلاف ذلك ، نحن بحاجة إلى رمي عملة أخرى لتحديد ما إذا كان سيتم اختيار الوجه التالي. كما كان من قبل ، على الرغم من حقيقة أن الوجه التالي لديه احتمال الاختيار$\frac{1}{2}$$$13 ، نحن لا نريد أن نرمي قطعة نقدية يسقط عليها النسر باحتمال$\frac{1}{3}$$$13 ، لأنه تم تجاهل نصف "كتلة" الاحتمالات عندما لم نحدد خطًا$\frac{1}{3}$$$$\frac{1}{2}$ . في الواقع ، بما أن نصف كتلة الاحتمالات قد اختفت ، فعندما نعيد تطبيع الاحتمالات المتبقية ، سنحصل على احتمالات محدثة: $$$\frac{2}{3}$ ، $$$\frac{1}{6}$ ، $$$\frac{1}{6}$ . لذلك ، يجب طرح العملة الثانية باحتمال $$$\frac{2}{3}$ . إذا كانت هذه العملة أيضًا ذات ذيل ، فيجب أن نختار بين وجهين $$$\frac{1}{12}$ . منذ هذه المرحلة سنتخلص منها $$56 كتل من الاحتمالات ، ثم يمكننا تطبيع احتمالات الأطراف مرة أخرى$\frac{5}{6}$$$112 بحيث يكون لكل شخص فرصة$\frac{1}{12}$$$12 فقدان النسر، وهذا هو، من عملة الثالثة من المرجح أن$\frac{1}{2}$$$$\frac{1}{2}$ . العملة الأخيرة ، إذا وصلت إليها ، يجب أن ترمي النسر باحتمال $$1 لأن هذه هي أحدث منطقة. للتلخيص ، ستكون احتمالات العملات المعدنية كما يلي:$1$

1. اللفة الأولى: $$$\frac{1}{2}$
2. اللفة الثانية: $$$\frac{2}{3}$
3. اللفة الثالثة: $$$\frac{1}{2}$
4. الدور الرابع: $$$1$

قد يكون الأمر بديهيًا من حيث تأتي هذه الأرقام ، ولكن من أجل تحويل التحديد إلى خوارزمية ، يتعين علينا إنشاء بنية رسمية لاختيار الاحتمالات. ستكون الفكرة التالية - في كل مرحلة نتذكر ما تبقى من كتلة الاحتمالات. في البداية ، قبل إلقاء العملة الأولى ، تساوي$$$1$ . بعد رمي العملة الأولى $$$1 - p_0$ . بعد رمي عملة ثانية $$$1 - p_0 - p_1$ . بشكل عام بعد الرمية $$ك ما تبقى من كتلة الاحتمال$k$$$$1 - \sum_{i = 0}^{k - 1}{p_i}$ . في كل مرة نقلب فيها عملة معدنية لتحديد ما إذا كان سيتم تحديد منطقة أم لا $$k ، ونتيجة لذلك نرمي عملة معدنية ، فإن احتمال سقوط النسر الذي يساوي جزء الاحتمال المتبقي الذي يشغله الاحتمال$k$$$ص ك ، الذي يعرف بأنه$p_k$$$$\frac{p_k}{1 - \sum_{i = 0}^{k - 1}{p_i}}$ . هذا يعطينا الخوارزمية التالية لغش محاكاة العظام مع مجموعة من العملات غير المتماثلة (سنثبت صحتها ووقت التشغيل أدناه):

الخوارزمية: عظم شولر من العملات غير المتماثلة

• التهيئة :
  
  1. نحافظ على الاحتمالات $$ص ط للاستخدام في المستقبل.$p_i$
• جيل :
  تعيين$$m a s s = 1 لـ$mass = 1$
  $$أنا = 0 إلى$i = 0$$$$n - 1$ :
  
  1. رمي عملة غير متماثلة مع احتمال وجود نسر $$$\frac{p_i}{mass}$ .
  2. إذا سقط النسر ، فارجع $$$i$ .
  3. خلاف ذلك ، قمنا بتعيين $$$mass = mass - p_i$

من وجهة نظر بديهية ، هذا منطقي ، ولكن هل هذا صحيح من الناحية الرياضية؟ لحسن الحظ ، الإجابة هي نعم بفضل تعميم البرهان أعلاه:

النظرية: ترجع الخوارزمية الموضحة أعلاه وجهًا$$أنا مع الاحتمال$i$$$ص ط لأي مختارة$p_i$$$$i$ .

الدليل: ضع في اعتبارك أي ثابت$$$n \ge 0$ . , $$$n$ $$$p_i$ .

, $$$0$ $$$p_0$ . $$$0$ , , $$$\frac{p_0}{mass}$ . $$$mass$ $$$1$ , $$$\frac{p_0}{1} = p_0$ , 0 $$$p_0$ , .

, $$$0, 1, ..., k - 1$ $$$p_0, p_1, ..., p_{k-1}$ $$$k$ . $$$k$ , $$$k$ , $$$\frac{p_k}{mass}$ . $$$k$ , , $$$k$ $$$\sum_{i = 0}^{k - 1}{p_i}$ . , $$$k$ $$$1 - \sum_{i = 0}^{k - 1}{p_i}$ . , $$$k$ , $$$\frac{p_k}{mass}$ $$$k$ , $$$mass = 1 - \sum_{i = 0}^{k - 1}{p_i}$ . , $$$k$ $$( 1 - ∑ ك - 1 ط = 0 ص ط ) ص ك1 - ∑ k - 1 i = 0 p i =pk، حسب الحاجة.$(1 - \sum_{i = 0}^{k - 1}{p_i})\frac{p_k}{1 - \sum_{i = 0}^{k - 1}{p_i}} = p_k$

الآن دعونا نقيم التعقيد الزمني لهذه الخوارزمية. نحن نعلم أن وقت التهيئة قد يكون$$Θ ( 1 ) إذا احتفظنا بنسخة سطحية من صفيف احتمال الإدخال ، ولكن قد يكون هناك$\Theta(1)$$$ثيتا ( ن ) ، حتى نتمكن من الحفاظ إصدار مجموعة الخاصة (في حال كان الطالب يريد تغييره لاحقا). قد يتطلب توليد نتيجة رمي العظام في أسوأ الحالات$\Theta(n)$$$Θ ( ن ) رمية، ولفة واحدة فقط في أحسن الأحوال.ومع ذلك ، بعد التفكير ، يصبح من الواضح أن عدد رميات العملات الضرورية يتأثر بشكل كبير بالتوزيع الوارد. في أفضل الأحوال ، سيكون لدينا توزيع احتمالي تتركز فيه كتلة الاحتمالات بالكامل على الحافة الأولى للعظم ، وتكون جميع الاحتمالات الأخرى صفرًا. في هذه الحالة ، يكفي رمي عملة واحدة بالنسبة لنا. في أسوأ الحالات ، تتركز الكتلة الكاملة للاحتمالات في الوجه الأخير للعظم ، وعلى جميع الوجوه الأخرى تساوي الصفر. في هذه الحالة ، علينا أن نرمي$\Theta(n)$

$$ن النقود. يمكننا أن نميز بشكل واضح ورياضي العدد المتوقع لرمي العملة في هذه الخوارزمية. دعونا نتخيل متغير عشوائي$n$

$$X ، يشير إلى عدد رميات العملات المعدنية لأي تنفيذ لهذه الخوارزمية لتوزيع معين. هذا هو$X$$$P [ X = 1 ] هو احتمال أن يكمل الخوارزمية رمي عملة واحدة ،$\mathbb{P}[X = 1]$$$P [ X = 2 ] - احتمال أن تقوم الخوارزمية برمي عملتين ، إلخ. في هذه الحالة ، يتم تحديد العدد المتوقع لرمي العملة لخوارزمية لدينا من خلالالتوقع الرياضي$\mathbb{P}[X = 2]$ $$X يُشار إليه بـ$X$$$$\mathbb{E}[X]$ . بحكم التعريف ، نحصل على ذلك

$$

$$\mathbb{E}[X] = \sum_{i = 1}^n{i \cdot \mathbb{P}[X = i]}$$

ما المعنى $$P [ X = i ] ؟ تنتهي الخوارزمية بعد تحديد حافة العظم. إذا اختار وجها$\mathbb{P}[X = i]$$$0 ، ثم إرم عملة واحدة. إذا اختار وجها$0$$$1 ، ثم يرمي عملتين - واحدة لفهم أنه لا يريد اختيار وجه$1$$$0 ، آخر لفهم أنه يريد اختيار وجه$0$$$$1$ . إذا كان أكثر عمومية ، فعندئذٍ إذا حددت الخوارزمية وجهًا $$ط ، ثم قال انه سوف رمي$i$$$عملات i + 1 :$i + 1$$$أنا عملات معدنية ليقرر أنه لا يريد اختيار السابق$i$$$ط - 1 وجوه وواحد لتحديد ما يختار الوجه$i - 1$$$$i$ . إلى جانب حقيقة أننا نعرف عن اختيار وجه $$أنا مع الاحتمال$i$$$ص أنا ، وهذا يعني ذلك$p_i$

$$

$$\mathbb{E}[X] = \sum_{i = 1}^n{i \cdot \mathbb{P}[X = i]} = \sum_{i = 1}^n{i \cdot p_{i - 1}} = \sum_{i = 1}^n{((i - 1) p_{i - 1} + p_{i - 1})} = \sum_{i = 1}^n{((i - 1) p_{i - 1})} + \sum_{i = 1}^n{p_{i - 1}}$$

لاحظ أنه في التبسيط الأخير ، فإن المصطلح الأول مكافئ $$$\ sum_ {i = 0} ^ {n-1} {i \ cdot p_i}$ وهو ما يعادل $$$\ mathbb {E} [p]$ ، النتيجة المتوقعة من لفة النرد! علاوة على ذلك ، المصطلح الثاني يساوي $$$1$ لأن هذا هو مجموع كل الاحتمالات. هذا يعني ذلك $$$\ mathbb {E} [X] = \ mathbb {E} [p] + 1$ . أي أن العدد المتوقع لفات العملات المعدنية يساوي واحدًا بالإضافة إلى التوقعات الرياضية لفة القالب!

خوارزمية	وقت التهيئة		وقت الجيل		ذاكرة مشغولة
	الأفضل	الأسوأ	الأفضل	الأسوأ	الأفضل	الأسوأ
الصدق العظام شارلر العظام	$$$\ ثيتا (ن)$	$$$O (\ prod_ {i = 0} ^ n {d_i})$	$$$\ Theta (1)$		$$$\ ثيتا (ن)$	$$$O (\ prod_ {i = 0} ^ n {d_i})$
عظم شولر من العملات غير المتماثلة	$$$\ ثيتا (ن)$		$$$\ Theta (1)$	$$$\ ثيتا (ن)$	$$$\ ثيتا (ن)$

تعميم العملات غير المتماثلة: محاكاة عظم الغش

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

كما ترون ، العملة غير المتماثلة هي عظم الغش ، مع وجهين فقط. لذلك ، يمكننا أن ندرك عملة غير متماثلة ببساطة كحالة خاصة لمشكلة أكثر عمومية نريد حلها. عند حل مشكلة العملة غير المتماثلة ، نقسم الفاصل الزمني $$$[0، 1)$ إلى منطقتين - واحدة للنسر ، والثانية للذيول - ثم للعثور على المنطقة ، نستخدم حقيقة أن هناك نقطة تقسيم واحدة فقط. إذا كان لدينا عظم ذو وجه n ، فسيكون هناك المزيد من المناطق ، وبالتالي العديد من نقاط التقسيم. لنفترض ، على سبيل المثال ، أن لدينا عظمة من سبعة جوانب مع احتمالات $$$\ frac {1} {4}$ ، $$$\ frac {1} {5}$ ، $$$\ frac {1} {8}$ ، $$$\ frac {1} {8}$ ، $$$\ frac {1} {10}$ ، $$$\ frac {1} {10}$ ، $$$\ frac {1} {10}$ . إذا أردنا تقسيم الفاصل الزمني $$$[0، 1)$ إلى سبعة أجزاء ، ثم نقوم بذلك على النحو التالي:


لاحظ مكان وجود هذه المناطق. تبدأ المنطقة الأولى بـ $$$0$ وينتهي $$$\ frac {1} {4}$ . تبدأ المنطقة الثانية بـ $$$\ frac {1} {4}$ وينتهي في $$$\ frac {1} {4} + \ frac {1} {5} = \ frac {9} {20}$ . بشكل أعم ، إذا كانت الاحتمالات متساوية $$$p_0 ، p_1 ، ... ، p_ {n - 1}$ ، ثم ستكون المناطق فترات $$$[0، p_0)$ ، $$$[p_0 ، p_0 + p_1)$ ، $$$[p_0 + p_1 ، p_0 + p_1 + p_2)$ الخ. هذه هي المنطقة $$$i$ محدودة بفاصل زمني

$$

$$[\ sum_ {j = 0} ^ {i - 1} {p_j} ، \ sum_ {j = 0} ^ {i} {p_j})$$

لاحظ أن الفرق بين هاتين القيمتين هو $$$p_i$ ، أي أن المساحة الإجمالية للمنطقة هي $$$p_i$ كما هو مطلوب.

الآن نحن نعلم مكان المناطق. إذا أردنا اختيار قيمة عشوائية موزعة بشكل موحد $$$x$ في النطاق $$$[0، 1)$ ، فكيف نحدد في أي فاصل يسقط؟ إذا استخدمنا خوارزمية العملة غير المتماثلة كنقطة انطلاق ، فستكون الفكرة على النحو التالي: بدءًا من نقطة نهاية المنطقة الأولى ، انتقل باستمرار للأعلى عبر جميع المناطق حتى نجد نقطة نهاية تزيد قيمتها عن القيمة $$$x$ . إذا فعلنا ذلك ، فسوف نجد المنطقة الأولى التي تحتوي على النقطة $$$x$ وبالتالي قيمتنا. على سبيل المثال ، إذا اخترنا قيمة عشوائية $$$x = \ frac {27} {40}$ ثم قم بإجراء البحث التالي:


يمكننا من خلالها استنتاج أن الوجه 3 سقط على الزهر مع الفهرسة من الصفر.

سوف تعطينا خوارزمية المسح الخطي خوارزمية زمنية $$$O (n)$ للعثور على الحافة المقذوفة للعظم. ومع ذلك ، يمكننا تحسين وقت التنفيذ بشكل كبير باستخدام الملاحظة التالية: تشكل سلسلة من نقاط النهاية للمناطق تسلسلاً متزايدًا (نظرًا لأننا نضيف دائمًا المزيد والمزيد من الاحتمالات ، لا يمكن أن يكون أي منها أقل من الصفر). لذلك ، نريد الإجابة على السؤال التالي: وجود تسلسل متزايد من القيم وبعض نقاط التفتيش ، نحتاج إلى العثور على القيمة الأولى في الفاصل الزمني بدقة أكبر من نقطة التفتيش. هذا هو الوقت المثالي لاستخدام البحث الثنائي ! على سبيل المثال ، إليك بحثًا ثنائيًا على الصفيف أعلاه للعثور على المنطقة التي ينتمي إليها $$$x = \ frac {39} {40}$ :


هذا يعطينا خوارزمية بمرور الوقت. $$$\ Theta (\ تسجيل n)$ لربط قيمة عشوائية موزعة بشكل منتظم في الفاصل الزمني $$$[0، 1)$ إلى حافة عظم مهجور. علاوة على ذلك ، يكفي وقت المعالجة المسبقة لبناء جدول نقطة النهاية $$$\ ثيتا (ن)$ ؛ نحن ببساطة نحسب مبالغ جزئية من الاحتمالات بينما نتحرك للأعلى.

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

خوارزمية: اختيار عجلة الروليت

• التهيئة :
  
  1. حدد مصفوفة $$$A$ الحجم $$$n$
  2. وضعنا $$$A [0] = p_0$ .
  3. لكل الاحتمالات $$$i$ من $$$1$ من قبل $$$n - 1$ :
     
     1. وضعنا $$$A [i] = A [i - 1] + p_i$
  
  
• الجيل :
  
  1. توليد قيمة عشوائية موزعة بشكل موحد $$$x$ في النطاق $$$[0، 1)$
  2. باستخدام البحث الثنائي ، نجد الفهرس $$$i$ أصغر عنصر $$$A$ وهو أقل $$$x$ .
  3. العودة $$$i$ .

تبدو المقارنة بين هذه الخوارزمية والخوارزمية السابقة رائعة للغاية:

خوارزمية	وقت التهيئة		وقت الجيل		ذاكرة مشغولة
	الأفضل	الأسوأ	الأفضل	الأسوأ	الأفضل	الأسوأ
الصدق العظام شارلر العظام	$$$\ ثيتا (ن)$	$$$O (\ prod_ {i = 0} ^ n {d_i})$	$$$\ Theta (1)$		$$$\ ثيتا (ن)$	$$$O (\ prod_ {i = 0} ^ n {d_i})$
عظم شولر من العملات غير المتماثلة	$$$\ ثيتا (ن)$		$$$\ Theta (1)$	$$$\ ثيتا (ن)$	$$$\ ثيتا (ن)$
اختيار عجلة الروليت	$$$\ ثيتا (ن)$		$$$\ Theta (\ تسجيل n)$		$$$\ ثيتا (ن)$

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

من التفاصيل المثيرة للاهتمام لهذه الخوارزمية أنه على الرغم من أن استخدام البحث الثنائي يضمن أسوأ وقت لتوليد أرقام عشوائية $$$O (\ تسجيل n)$ كما أنه لا يسمح ببحث أسرع ؛ أي أن وقت الجيل سيكون متساويًا أيضًا $$$\ أوميغا (\ تسجيل ن)$ . هل يمكن تحسينها؟ اتضح أنه يمكنك ذلك.

لنفترض أننا انتقلنا من بحث ثنائي في قائمة الاحتمالات التراكمية إلى استخدام شجرة بحث ثنائية . على سبيل المثال ، باستخدام مجموعة الاحتمالات الواردة أعلاه ، يمكننا إنشاء شجرة البحث الثنائية التالية لتوزيعها التراكمي:


الآن ، إذا أردنا محاكاة لفة عظم ، يمكننا إنشاء رقم موزع بشكل منتظم في الفاصل الزمني $$$[0، 1)$ ثم انظر إلى الفاصل الزمني الذي تكمن فيه شجرة البحث الثنائية هذه (BST). نظرًا لأن هذه شجرة بحث ثنائية متوازنة ، فإن أفضل وقت للبحث هو $$$O (1)$ والأسوأ $$$O (\ تسجيل n)$ .

ومع ذلك ، بافتراض أننا نعرف المزيد عن التوزيع الاحتمالي ، يمكننا أن نفعل أفضل بكثير. على سبيل المثال ، لنفترض أن احتمالاتنا متساوية $$$\ frac {99} {100}$ ، $$$\ frac {1} {600}$ ، $$$\ frac {1} {600}$ ، $$$\ frac {1} {600}$ ، $$$\ frac {1} {600}$ ، $$$\ frac {1} {600}$ ، $$$\ frac {1} {600}$ . أي أن توزيع الاحتمالات منحرف للغاية ، وتتركز الكتلة الاحتمالية بأكملها تقريبًا على وجه واحد. يمكننا بناء BST متوازن لهذه الاحتمالات:


على الرغم من أن شجرة البحث الثنائية هذه متوازنة تمامًا ، إلا أنها ليست مناسبة جدًا لمهامنا. نظرًا لأننا نعلم أنه في 99 من 100 حالة ، ستكون القيمة العشوائية في النطاق $$$[0، \ frac {99} {100})$ ، فلا فائدة من تخزين العقدة لهذا الفاصل الزمني حيث توجد الآن. في الواقع ، هذا سيعني أنه في جميع الأوقات تقريبًا ، سنجري مقارنتين غير ضروريتين مع المناطق الزرقاء والصفراء. نظرًا لأنه مع احتمالية عالية جدًا ، يجب أن نكون أول من يتحقق من أكبر فترة زمنية ، سيكون من المنطقي عدم توازن الشجرة لجعل الحالة المتوسطة أفضل بكثير بسبب الحالات المتبقية. هذا موضح هنا:


الآن سنكمل البحث على الأرجح من خلال إيجاد المنطقة المطلوبة فورًا بعد المحاولة الأولى. في حالة من غير المرجح أن تكون المنطقة المطلوبة في الباقي $$$(\ frac {99} {100} ، 1]$ نذهب بهدوء إلى نهاية الشجرة ، وهي في الواقع متوازنة بشكل جيد.

في شكل عام ، نريد حل المشكلة التالية:

بالنظر إلى مجموعة معينة من الاحتمالات ، ابحث عن شجرة بحث ثنائية لهذه الاحتمالات تقلل وقت البحث المتوقع.

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

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

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

خوارزمية	وقت التهيئة		وقت الجيل		ذاكرة مشغولة
	الأفضل	الأسوأ	الأفضل	الأسوأ	الأفضل	الأسوأ
الصدق العظام شارلر العظام	$$$\ ثيتا (ن)$	$$$O (\ prod_ {i = 0} ^ n {d_i})$	$$$\ Theta (1)$		$$$\ ثيتا (ن)$	$$$O (\ prod_ {i = 0} ^ n {d_i})$
عظم شولر من العملات غير المتماثلة	$$$\ ثيتا (ن)$		$$$\ Theta (1)$	$$$\ ثيتا (ن)$	$$$\ ثيتا (ن)$
اختيار عجلة الروليت	$$$\ ثيتا (ن)$		$$$\ Theta (\ تسجيل n)$		$$$\ ثيتا (ن)$
الاختيار الأمثل لعجلة الروليت	$$$O (n ^ 2)$		$$$\ Theta (1)$	$$$O (\ تسجيل n)$	$$$\ ثيتا (ن)$

رمي السهام

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

حتى هذه اللحظة ، تصورنا الفاصل الزمني $$$[0، 1)$ واحتمالات الوجوه العظمية كفاصل أحادي البعد. كل من هذه الخوارزميات حدد نقطة ما في الفاصل الزمني $$$[0، 1)$ ووضعها على قطعة خط مستقيم ، يطابق طولها نوعًا من الاحتمال. كلما طالت الأجزاء التي أنشأناها ، زاد احتمال اختيار هذه الشريحة. ولكن ماذا لو حاولت ألا تفكر في أحد بل بعدين؟ ماذا لو أخذنا الاحتمال $$$p_i$ ليس طول قطعة مستقيمة ، ولكن مساحة المستطيل؟

لنبدأ بالعودة إلى مثالنا السابق باحتمالات $$$\ frac {1} {2}$ ، $$$\ frac {1} {3}$ ، $$$\ frac {1} {12}$ ، $$$\ frac {1} {12}$ . نحن نمثل هذه الاحتمالات في شكل مستطيلات بعرض $$$w$ (مع بعض التعسفي $$$w> 0$ ) والارتفاع $$$p_i$ (وبذلك تكون مساحة المستطيل مساوية لـ $$$w \ cdot p_i$ ):


لاحظ أن المساحة الإجمالية لهذه المستطيلات هي $$$w$ منذ المنطقة

$$

$$\ sum_ {i = 0} ^ {n - 1} {w p_i} = w \ sum_ {i = 0} ^ {n - 1} {p_i} = w$$

لنفترض الآن أننا نرسم مستطيلًا محيطًا حول هذه المستطيلات التي يكون عرضها $$$4w$ (بما أن هناك أربعة زوايا) ، والارتفاع $$$\ frac {1} {2}$ (بما أن أطول مستطيل له ارتفاع $$$\ frac {1} {2}$ ):


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

$$

$$\ mathbb {P} [\ mbox {hit rectangle للجانب i} | \ mbox {ضرب بعض المستطيل}] = \ frac {\ mbox {مساحة المستطيل لـ i}} {\ mbox {إجمالي مساحة المستطيل}} = \ frac {w p_i} {w} = p_i$$

بعبارة أخرى ، عندما نقع أخيرًا في نوع من المستطيل مع السهام الموزعة بالتساوي ، نختار مستطيل الوجه $$$i$ عظم الغشاش مع احتمال $$$p_i$ ، مع احتمال أننا بحاجة! أي أنه إذا تمكنا من إيجاد طريقة فعالة لمحاكاة رمي السهام العشوائية في هذا المستطيل ، فستكون لدينا طريقة فعالة لمحاكاة رمي النرد العشوائي.

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

الملاحظة الأولى: أظهرنا أنه يمكن اختيار عرض هذه المستطيلات بشكل تعسفي ، لأن جميعها متساوية العرض. المرتفعات ، بالطبع ، تعتمد على احتمالات وجوه العظام. ومع ذلك ، إذا قمنا بموازنة جميع الارتفاعات بالتساوي من خلال عدد حقيقي موجب $$$h$ ، فإن المساحات النسبية لجميع المستطيلات ستكون هي نفسها. في الواقع ، لأي رقم حقيقي إيجابي $$$h$ المساحة الكلية لجميع المستطيلات بعد قياس ارتفاعاتها $$$h$ تحسب على أنها

$$

$$\ sum_ {i = 0} ^ {n - 1} {w h p_i} = w h \ sum_ {i = 0} ^ {n - 1} {p_i} = w h$$

الآن سنأخذ في الاعتبار احتمال اختيار أي مستطيل فردي ، ونقتصر على شرط أننا ضربنا نوعًا معينًا من المستطيل. باستخدام نفس الحسابات ، نحصل على ما يلي:

$$

$$\ mathbb {P} [\ mbox {hit rectangle للجانب i} | \ mbox {ضرب بعض المستطيل}] = \ frac {\ mbox {مساحة المستطيل لـ i}} {\ mbox {إجمالي مساحة المستطيل}} = \ frac {w h p_i} {w h} = p_i$$

هذا ، في الواقع ، لا يتغير احتمال اختيار أي مستطيل واحد إذا قمنا بقياسها بشكل خطي وبالتساوي.

نظرًا لأنه يمكننا اختيار أي عامل قياس مناسب ، فلماذا لا نقوم بقياس هذه المستطيلات بحيث يكون ارتفاع المربع المحيط دائمًا 1؟ نظرًا لأن ارتفاع الصندوق المحيط يتحدد بالقيمة القصوى $$$p_i$ احتمالات الإدخال ، يمكننا بعد ذلك البدء بقياس كل من المستطيلات بعامل $$$\ frac {1} {p_ {max}}$ أين $$$p_ {max}$ هو أقصى احتمال لجميع احتمالات الإدخال. وبفضل هذا ، نحصل على ارتفاع المستطيل 1. وبالمثل ، نظرًا لأنه يمكننا اختيار أي عرض عشوائي للمستطيلات ، فلنأخذ العرض 1. هذا يعني أنه $$$n$ احتمالات العرض الكلي للصندوق المحيط هي $$$n$ ، والارتفاع الكلي هو 1. وهذا موضح في الشكل:


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


لاحظ كيف يتشكل هذا المستطيل. لكل وجه من عظم الغشاش ، لدينا عمود واحد بعرض 1 وارتفاع 1 ، مقسم إلى مسافتين - نصف مسافة "نعم" تقابل مستطيل من هذا الحجم ، ونصف مسافة "لا" تقابل الجزء المتبقي من العمود.

الآن دعونا نفكر في كيفية رمي السهام. ستحتوي رمي السهام المنتظم تمامًا في هذا المستطيل على مكونات $$$x$ و $$$y$ . مكون هنا $$$x$ الذي يجب أن يكون في الفاصل الزمني $$$[0، 1)$ ، يتوافق مع العمود الذي يضربه السهام. مكون $$$y$ الذي يجب أن يكون في الفاصل الزمني $$$[0، 1)$ ، يتوافق مع مدى ارتفاعنا في العمود. اختيار المكون $$$x$ يؤثر على وجه عظم الغشاش الذي نفكر فيه ، واختيار المكون $$$y$ يتوافق مع ما إذا كنا قد اخترنا هذا الوجه أم لا. ولكن انتظر - نحن نعلم بالفعل هذين الفكرتين! اختيار الإحداثيات $$$x$ المقابلة للعمود ، على غرار رمي عظمة صادقة لاتخاذ قرار بشأن اختيار العمود. اختيار الإحداثيات $$$y$ يتوافق مع رمي عملة غير متماثلة لتحديد ما إذا كنت تريد تحديد وجه أو رمي مرة أخرى! هذه الملاحظة مهمة للغاية لدرجة أننا جعلناها مفهومة تمامًا:

يشبه اختيار نقطة عشوائية في هذا الفاصل رمي عظمة صادقة ورمي عملة غير متماثلة.

في الواقع ، يمكن اعتبار هذه النتيجة فرصة أقوى بكثير. لمحاكاة عظم الغش ، نقوم ببناء مجموعة من العملات غير المتماثلة ، واحدة لكل وجه من العظام ، ثم نلف عظمة صادقة لتحديد أي عملة يجب رميها. , , , , .

. -, — «» $$$\frac{p_i}{p_{max}}$ , «» $$$\frac{p_{max} - p_i}{p_{max}}$ . , 1. -, $$$1$ , . , : - , , ( , ). . , , . .

: /

• :
  
  1. $$$p_i$ ; $$$p_{max}$ .
  2. $$$Coins$ $$$n$ , «» .
  3. $$$i$ من $$$0$ من قبل $$$n - 1$ :
     
     1. $$$Coins[i] = \frac{p_i}{p_{max}}$
  
  
• :
  
  1. :
     
     1. n- $$$i$ $$$[0, n)$ .
     2. , $$$Coins[i]$ .
     3. , $$$i$ .

. $$$O(n)$ , $$$O(n)$ $$$Coins$ , $$$O(n)$ . , $$$O(1)$ . ? , , - . , . , ( $$$\frac{1}{n}$ ), . , , , , - , . , $$$i$ $$$\frac{p_i}{p_{max}}$ , -

$$

$$\sum_{i = 0}^{n - 1}{(\frac{1}{n} \frac{p_i}{p_{max}})} = \frac{1}{n}\sum_{i = 0}^{n - 1}{\frac{p_i}{p_{max}}} = \frac{1}{n \cdot p_{max}}\sum_{i = 0}^{n - 1}{p_i} = \frac{1}{n \cdot p_{max}}$$

- , , , , , $$$n \cdot p_{max}$ . ? $$$p_{max}$ . $$$p_{max}$ $$$1$ ( ). $$$n$ , $$$n$ . , , , , . , $$$p_{max}$ $$$\frac{1}{n}$ , , . $$$p_{max} = \frac{1}{n}$ , 1. . $$$p_{max} = \frac{1}{n}$ , ( $$$\frac{1}{n}$ ), 1, , 1. , , .

, $$$p_{max}$ , , , . , , $$$n$ , , 1. , , «» $$$\frac{1}{p_{max}}$ , 1, $$$\frac{1}{p_{max}}$ . , «» $$$\frac{1}{n \cdot p_{max}}$ . , , «», $$$p_{max}$ . , , .

:

	$$$\Theta(n)$	$$$O(\prod_{i = 0}^n{d_i})$	$$$\Theta(1)$		$$$\Theta(n)$	$$$O(\prod_{i = 0}^n{d_i})$
	$$$\Theta(n)$		$$$\Theta(1)$	$$$\Theta(n)$	$$$\Theta(n)$
	$$$\Theta(n)$		$$$\Theta(\log n)$		$$$\Theta(n)$
	$$$O(n^2)$		$$$\Theta(1)$	$$$O(\log n)$	$$$\Theta(n)$
/	$$$\Theta(n)$		$$$\Theta(1)$	$$$\Theta(n)$ ()	$$$\Theta(n)$

, . . ?

Alias-

, . , . , , «» , . , , , . - , , - , .

, , , . . $$$\frac{1}{2}$ ، $$$\frac{1}{3}$ ، $$$\frac{1}{12}$ ، $$$\frac{1}{12}$ . , $$$\frac{1}{4}$ . , $$$\frac{1}{4}$ , $$$\frac{1}{2}$ ? , . $$$1$ , :


, $$$\frac{1}{4}$ 1. , , :


$$$1 \times 4$ . , :


, , $$$\frac{1}{2}$ و $$$\frac{1}{3}$ . ? , $$$\frac{1}{2}$ $$$\frac{1}{12}$ ? , - , :


, , . , $$$\frac{1}{2}$ و $$$\frac{1}{3}$ , . $$$\frac{1}{2}$ , . , :


, , :


. -, . , ; . , , . -, , , - , , . , . — , . , — , , . , . , , , - ( ).

alias- . -, , . , , . , , , .

, , ? , , . , , , , , . , . , - , , , ( ) , - . (alias) , «» - . - «alias» «alias-».

, , . - ( !), () , , alias- : $$$Prob$ alias $$$Alias$ . $$$n$ . , alias , ( ). , . - - $$$i$ . $$$Prob[i]$ . , , $$$i$ , , $$$Alias[i]$ . alias :

Alias

, $$$Alias$ و $$$Prob$ موجود دائما. لإثبات أن هذا ممكن دائمًا ، نحتاج إلى إثبات أنه من الممكن دائمًا القيام بما يلي:

• إنشاء مستطيلات $$$(n \ cdot p_i) \ ضرب 1$ لكل الاحتمالات $$$p_i$ ،
• قطعها أفقيا إلى قطع أصغر و
• توزيعها على $$$n$ الأعمدة
  
  • بحيث يكون ارتفاع كل عمود متساويًا $$$1$ ،
  • لا يوجد عمود يحتوي على أكثر من مستطيلين و
  • المستطيل المقابل للوجه $$$i$ تقع في العمود $$$i$ .

قبل الانتقال إلى الدليل على أن هذا ممكن دائمًا ، دعنا نلقي نظرة على مثال. لنفترض أن لدينا أربعة احتمالات $$$\ frac {1} {2}$ ، $$$\ frac {1} {3}$ ، $$$\ frac {1} {12}$ ، $$$\ frac {1} {12}$ . هذه مجموعة من أربعة احتمالات ( $$$k = n = 4$ ) ، مجموعها يساوي $$$1 = \ frac {4} {4}$ . على الرغم من أننا أظهرنا تجريبيًا كيفية ملء جدول الاسم المستعار أعلاه ، فلنلقِ الآن نظرة على إنشائه بمزيد من التفاصيل ونبدأ بجدول فارغ تمامًا ، ثم نبدأ في ملؤه. نبدأ بقياس كل هذه الاحتمالات بعامل 4 ، مما يعطينا مثل هذه الاحتمالات وجدول فارغ مثل:


لاحظ أن اثنين من المستطيلات الأربعة التي نحتاج إلى توزيعها ( $$$\ frac {1} {3}$ ، $$$\ frac {1} {3}$ ) أقل من 1. هذا يعني أنهم لن يتمكنوا من ملء العمود بالكامل وملء الباقي نحتاج إلى بعض الاحتمالات الأخرى. لنأخذ أحد الاثنين (دعنا نقول أصفر) ونضعه في العمود المقابل:


الآن نحن بحاجة إلى تغطية الفرق بطريقة أو بأخرى في الجزء العلوي من العمود. للقيام بذلك ، نلاحظ أن مستطيلين لم يتم توزيعهما بعد لديهما ارتفاع أكبر من 1 (أي $$$2$ و $$$\ frac {4} {3}$ ) دعنا نختار واحد منهم بشكل عشوائي. فليكن $$$\ frac {4} {3}$ . ثم سنقوم بتوزيع جزء كاف من $$$\ frac {4} {3}$ في عمود لملئه بالكامل ؛ نتيجة نشارك $$$\ frac {2} {3}$ من $$$\ frac {4} {3}$ كما هو موضح أدناه:


الآن دعونا نرى كيف تبدو دائرتنا. لدينا ثلاثة مستطيلات مساحتها الإجمالية $$$3$ ، وثلاثة أعمدة مجانية ، يبدو أنه يمكنك توزيع هذه المستطيلات عبر هذه الأعمدة الثلاثة. للقيام بذلك ، سوف نستخدم نفس الحيلة كما كانت من قبل. لاحظ أن هناك مستطيلًا واحدًا على الأقل يقل ارتفاعه عن $$$1$ ، لذلك سنختار واحدة من طريقة تعسفية (على سبيل المثال ، مستطيل $$$\ frac {2} {3}$ ) ثم ضعها في عمودك:


الآن نحن بحاجة لملء العمود حتى النهاية ، لذلك نأخذ بعض الاحتمال ، الذي لا يقل عن 1 ، ونستخدمه لتكملة بقية العمود. هنا لدينا خيار واحد فقط (استخدم $$$2$ ) ، لذلك نأخذ $$$\ frac {1} {3}$ من $$$2$ ووضعها في أعلى العمود:


الآن يأتي إلى مستطيلين ، تبلغ مساحتهما الإجمالية اثنين. نكرر هذه العملية ، وإيجاد بعض المستطيل الذي لا يزيد ارتفاعه عن 1 (هنا هو $$$\ frac {1} {3}$ ) ووضعه في هذا العمود:


الآن سنجد بعض المستطيل لا يقل عن $$$1$ لتكملة العمود. الخيار الوحيد بالنسبة لنا $$$\ frac {5} {3}$ :


الآن لدينا مستطيل واحد فقط ، ومساحته هي 1. وبالتالي ، يمكننا ببساطة إكمال الإنشاء عن طريق وضع هذا المستطيل في العمود الخاص به:


وفويلا! ملأنا الجدول.

لاحظ أن تصميم هذا الجدول يعتمد على نمط شائع:

• نجد بعض المستطيل الذي لا يزيد ارتفاعه عن 1 ، ونضعه في العمود الخاص به ، مع ضبطه في الجدول $$$Prob$ ارتفاع هذا المستطيل.
• نجد بعض المستطيل الذي لا يقل ارتفاعه عن 1 ، نستخدمه لملء العمود ، الإعداد في الجدول $$$Alias ​​$ تطابق وجه العظم الذي يمثله هذا المستطيل.

هل من الممكن إثبات أن مثل هذا البناء ممكن دائمًا في الحالة العامة؟ أي أننا لسنا "عالقين" بتوزيع الاحتمالات بهذه الطريقة؟ لحسن الحظ ، هناك أدلة. يمكن تفسير ذلك على النحو التالي: قمنا بتدرج جميع الاحتمالات بحيث يكون متوسط ​​قيمة الاحتمالات الجديدة يساوي 1 (حيث كان في البداية يساوي $$$\ frac {1} {n}$ ، وضربنا كل شيء في $$$n$ ) نحن نعلم أن الحد الأدنى لجميع الاحتمالات المتدرجة يجب ألا يكون أكبر من المتوسط ​​، وأن الحد الأقصى لجميع الاحتمالات المتدرجة يجب ألا يقل عن المتوسط ​​، لذلك عندما نبدأ هنا لأول مرة ، يجب أن يكون لدينا دائمًا عنصر واحد على الأقل لا يزيد عن 1 (أي أصغر الاحتمالات المقيسة) وعنصر واحد على الأقل 1 (أي أكبر الاحتمالات المقيسة). لذلك ، يمكننا إقران هذه العناصر. ولكن ماذا يحدث إذا أزلناهما؟ عند القيام بذلك ، نتيجة لذلك ، نقوم بإزالة احتمال واحد من الإجمالي وتقليل المجموع الكلي للاحتمالات المقيسة بمقدار واحد. هذا يعني أن متوسط ​​القيمة الجديدة لم يتغير ، لأن متوسط ​​الاحتمال المتدرج يساوي. يمكننا تكرار هذا الإجراء مرارًا وتكرارًا حتى نقوم في النهاية بإقران جميع العناصر.

يمكننا إضفاء الطابع الرسمي على هذه الحجة في النظرية التالية:

النظرية: إن وجدت $$$k$ مستطيلات بعرض الوحدة بارتفاعات $$$h_0$ ، $$$h_1$ ، ... ، $$$h_ {k-1}$ مثل هذا $$$\ sum_ {i = 0} ^ {k-1} {h_i} = k$ ، هناك دائمًا طريقة لفصل المستطيلات وتوزيعها $$$k$ أعمدة ، لكل منها ارتفاع 1 ، بحيث لا يحتوي كل عمود على أكثر من مستطيلين مختلفين ، وفي $$$i$ سيحتوي هذا العمود على جزء واحد على الأقل $$$i$ المستطيل.

الدليل: عن طريق الحث. في حالة القاعدة ، إذا $$$k = 1$ ، ثم لدينا مستطيل واحد فقط ويجب أن يكون ارتفاعه يساوي 1. لذلك ، يمكننا وضعه $$$0$ العمود ال. لذلك ، لكل عمود ارتفاع 1 ، ولا يحتوي على أكثر من مستطيلين ، وفي $$$0$ - العمود الثالث يحتوي على جزء واحد على الأقل $$$0$ المستطيل.

بالنسبة لمرحلة الحث ، افترض أنه بالنسبة لعدد طبيعي $$$k$ النظرية صالحة وتعتبر أي $$$k + 1$ مستطيلات واسعة $$$1$ والارتفاعات $$$h_0$ ، $$$h_1$ ، ... ، $$$h_ {k}$ مثل هذا $$$\ sum_ {i = 0} ^ {k} {h_i} = k + 1$ . أولا ندعي أن هناك ارتفاع معين $$$h_l$ مثل هذا $$$h_l \ le 1$ وبعض الارتفاعات الأخرى $$$h_g$ (مثل ذلك $$$l \ ne g$ ) مثل ذلك $$$h_g \ ge 1$ . للتحقق من ذلك ، دعنا نذهب من العكس ونفترض أنه لا يوجد مثل هذا $$$h_l$ مع $$$h_l \ le 1$ ؛ سيعني ذلك $$$h_i> 1$ لجميع الأعداد الطبيعية $$$i$ في النطاق $$$0 \ le i \ le k$ . ولكن بعد ذلك نحصل على ذلك $$$k + 1 = \ sum_ {i = 0} ^ k {h_i}> \ sum_ {i = 0} ^ k {1} = k + 1$ وهو أمر مستحيل. لذلك ، هناك نوع من الفهرس $$$l$ مثل هذا $$$h_l \ le 1$ . الآن مرة أخرى ، دعنا نذهب من العكس ونفترض أنه لا يوجد ارتفاع آخر $$$h_g$ (مع $$$l \ ne g$ ) مثل ذلك $$$h_g \ ge 1$ . ثم اتضح أن بعضها البعض $$$h_g <1$ ، وهذا (من خلال منطق مماثل) $$$\ sum_ {i = 0} ^ {k} {h_i} <k + 1$ وقد وصلنا إلى تناقض. لذلك $$$h_l \ le 1$ و $$$h_g \ ge 1$ .

الآن فكر في البناء التالي. ضع $$$h_l$ في العمود $$$l$ واملأ المساحة المتبقية $$$1 - h_l$ في $$$l$ هذا العمود هو جزء من المستطيل $$$h_g$ (يجب أن توجد مثل هذه المساحة منذ ذلك الحين $$$0 \ le 1 - h_l \ le 1$ و $$$h_g \ ge 1$ ) لذلك سنملأ العمود بالكامل. الآن لدينا مجموعة $$$k$ أجزاء مختلفة من المستطيلات التي يساوي مجموعها $$$k$ بما أننا أزلنا المساحة الكلية من المستطيلات $$$1$ وكان الإجمالي الأولي $$$k + 1$ . علاوة على ذلك ، قمنا بملء العمود بالكامل $$$l$ ، أي أننا لم نعد بحاجة لوضع أجزاء أخرى من المستطيلات هناك. لذلك ، من خلال الفرضية الاستقرائية ، يمكننا توزيع الباقي $$$k$ في $$$k$ أعمدة بحيث تستوفي الشروط المذكورة أعلاه. إلى جانب حقيقة أننا ملأنا العمود الآن $$$l$ ، هذا يعني أن لدينا طريقة لملء جميع الأعمدة بحيث تلبي القيود. هذا يكمل الحث.

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

توليد طاولة الاسم المستعار

باستخدام ما سبق ، يمكننا الحصول على خوارزمية جيدة لمحاكاة رميات عظم الغش باستخدام طريقة الاسم المستعار. يتكون التهيئة من المسح المتكرر للاحتمالات الواردة للعثور على قيمة لا تزيد عن 1 وقيمة لا تقل عن 1 ، متبوعًا بدمجها في زوج لملء العمود:

الخوارزمية: طريقة اسم مستعار ساذج

• التهيئة :
  
  1. اضرب كل الاحتمالات $$$p_i$ على $$$n$ .
  2. إنشاء صفائف $$$Alias ​​$ و $$$Prob$ كل منها له حجم $$$n$ .
  3. ل $$$j = 1 \ mbox {to} n - 1$ :
     
     1. أوجد الاحتمال $$$p_l$ تلبية الشرط $$$p_l \ le 1$ .
     2. أوجد الاحتمال $$$p_g$ (مع $$$l \ ne g$ ) استيفاء الشرط $$$p_g \ ge 1$
     3. وضعنا $$$Prob [l] = p_l$ .
     4. وضعنا $$$Alias ​​[l] = g$ .
     5. حذف $$$p_l$ من قائمة الاحتمالات الأولية.
     6. وضعنا $$$p_g: = p_g - (1 - p_l)$ .
     
     
  4. دع $$$i$ سيكون الاحتمال الأخير المتبقي ، والذي يجب أن يكون ارتفاعه 1.
  5. وضعنا $$$Prob [i] = 1$ .
  
  
• الجيل :
  
  1. نقوم بتوليد لفة عظام صادقة من $$$n$ - عظم الوجه اتصل بالوجه $$$i$ .
  2. رمي عملة غير متماثلة تسقط من قبل نسر مع احتمال $$$Prob [i]$ .
  3. إذا سقط نسر على عملة معدنية ، عد $$$i$ .
  4. عودة خلاف ذلك $$ .

خطوة إنشاء هذه الخوارزمية هي تمامًا نفس الطريقة الموضحة أعلاه ، وتستغرق وقتًا $$$\ Theta (1)$ . تتطلب خطوة التهيئة التكرارات المتعددة الموضحة أعلاه. أولا ، نحن بحاجة لقضاء الوقت $$$\ ثيتا (ن)$ عن طريق قياس كل الاحتمال بعامل $$$n$ وقضاء الوقت $$$O (n)$ لتخصيص صفيفين. الحلقة الداخلية قيد التشغيل $$$\ ثيتا (ن)$ مرات ، وفي كل تكرار يقوم بالعمل $$$O (n)$ عن طريق مسح المصفوفة ، وإزالة أحد عناصر المصفوفة وتحديث الاحتمالات. يمنحنا الوقت $$$O (n ^ 2)$ التهيئة العامة. إذا أخذنا هذه الخوارزمية في الاعتبار ، نحصل على ما يلي:

خوارزمية	وقت التهيئة		وقت الجيل		ذاكرة مشغولة
	الأفضل	الأسوأ	الأفضل	الأسوأ	الأفضل	الأسوأ
الصدق العظام شارلر العظام	$$$\ ثيتا (ن)$	$$$O (\ prod_ {i = 0} ^ n {d_i})$	$$$\ Theta (1)$		$$$\ ثيتا (ن)$	$$$O (\ prod_ {i = 0} ^ n {d_i})$
عظم شولر من العملات غير المتماثلة	$$$\ ثيتا (ن)$		$$$\ Theta (1)$	$$$\ ثيتا (ن)$	$$$\ ثيتا (ن)$
اختيار عجلة الروليت	$$$\ ثيتا (ن)$		$$$\ Theta (\ تسجيل n)$		$$$\ ثيتا (ن)$
الاختيار الأمثل لعجلة الروليت	$$$O (n ^ 2)$		$$$\ Theta (1)$	$$$O (\ تسجيل n)$	$$$\ ثيتا (ن)$
الصدق العظام / عملات غير متناظرة	$$$\ ثيتا (ن)$		$$$\ Theta (1)$	$$$\ ثيتا (ن)$ (متوقع)	$$$\ ثيتا (ن)$
طريقة الاسم المستعار ساذجة	$$$O (n ^ 2)$		$$$\ Theta (1)$		$$$\ ثيتا (ن)$

بالمقارنة مع طرق المحاكاة الفعالة الأخرى ، فإن طريقة الاسم المستعار الساذجة هذه لديها تكاليف تهيئة عالية ، ولكن يمكنها بعد ذلك محاكاة لفات العظام بكفاءة عالية. إذا تمكنا بطريقة أو بأخرى من تقليل تكاليف التهيئة (دعنا نقول إلى $$$O (n)$ ) ، فإن هذه الطريقة ستكون بالتأكيد أفضل من جميع التقنيات المستخدمة هنا.

تتمثل إحدى الطرق البسيطة لخفض تكاليف التهيئة في استخدام بنية بيانات أكثر ملاءمة للحفاظ على الارتفاعات أثناء التنفيذ. في النسخة الساذجة ، نستخدم مصفوفة غير مصنفة لتخزين جميع الاحتمالات ، أي يستغرق الأمر وقتًا للعثور على الاحتمالين الضروريين $$$O (n)$ . البديل الأنسب لتخزين القيم هو شجرة بحث ثنائية متوازنة. في هذه الحالة ، يمكننا العثور على القيم $$$p_g$ و $$$p_l$ في الوقت المناسب $$$O (\ تسجيل n)$ من خلال البحث عن القيم القصوى والدنيا للشجرة. حذف $$$p_l$ يمكن القيام به في الوقت المناسب $$$O (\ تسجيل n)$ وتحديث الاحتمالات $$$p_g$ يمكن أن تؤدي أيضا في $$$O (\ تسجيل n)$ بسبب إزالتها البسيطة من الشجرة مع إعادة الإدخال اللاحقة. هذا يعطينا الخوارزمية التالية:

الخوارزمية: طريقة الاسم المستعار

• التهيئة :
  
  1. إنشاء صفائف $$$Alias ​​$ و $$$Prob$ كل حجم $$$n$ .
  2. إنشاء شجرة بحث ثنائية متوازنة $$$T$ .
  3. أدخل $$$n \ cdot p_i$ في $$$T$ لكل احتمال $$$i$ .
  4. ل $$$j = 1 \ mbox {to} n - 1$ :
     
     1. البحث عن أصغر قيمة وحذفها $$$T$ ؛ دعونا نتصل به $$$p_l$ .
     2. ابحث عن أعلى قيمة وحذفها في $$$T$ ؛ دعونا نتصل به $$$p_g$ .
     3. وضعنا $$$Prob [l] = p_l$ .
     4. وضعنا $$$Alias ​​[l] = g$ .
     5. وضعنا $$$p_g: = p_g - (1 - p_l)$ .
     6. أضف $$$p_g$ ل $$$T$ .
     
     
  5. دع $$$i$ سيكون الاحتمال الأخير المتبقي الذي يجب أن يكون وزنه 1.
  6. وضعنا $$$Prob [i] = 1$ .
  
  
• الجيل :
  
  1. نقوم بتوليد لفة عظام صادقة من $$$n$ - عظم الوجه اتصل بالوجه $$$i$ .
  2. نرمي عملة غير متماثلة يسقط عليها النسر باحتمال $$$Prob [i]$ .
  3. إذا سقط نسر على عملة معدنية ، عد $$$i$ .
  4. عودة خلاف ذلك $$ .

الآن تهيئة الخوارزمية لدينا أسرع بكثير. الخلق $$$Alias ​​$ و $$$Prob$ لا يزال يستغرق وقتا $$$O (n)$ على كل جدول ، وإضافة احتمالات إلى BST $$$T$ يستغرق وقتا $$$\ Theta (n \ log n)$ . بعد ذلك نؤدي $$$\ ثيتا (ن)$ تكرارات لملء الجدول ، كل منها يستغرق وقتًا $$$O (\ تسجيل n)$ . هذا يعطينا إجمالي وقت التهيئة. $$$O (n \ log n)$ :

خوارزمية	وقت التهيئة		وقت الجيل		ذاكرة مشغولة
	الأفضل	الأسوأ	الأفضل	الأسوأ	الأفضل	الأسوأ
الصدق العظام شارلر العظام	$$$\ ثيتا (ن)$	$$$O (\ prod_ {i = 0} ^ n {d_i})$	$$$\ Theta (1)$		$$$\ ثيتا (ن)$	$$$O (\ prod_ {i = 0} ^ n {d_i})$
عظم شولر من العملات غير المتماثلة	$$$\ ثيتا (ن)$		$$$\ Theta (1)$	$$$\ ثيتا (ن)$	$$$\ ثيتا (ن)$
اختيار عجلة الروليت	$$$\ ثيتا (ن)$		$$$\ Theta (\ تسجيل n)$		$$$\ ثيتا (ن)$
الاختيار الأمثل لعجلة الروليت	$$$O (n ^ 2)$		$$$\ Theta (1)$	$$$O (\ تسجيل n)$	$$$\ ثيتا (ن)$
الصدق العظام / عملات غير متناظرة	$$$\ ثيتا (ن)$		$$$\ Theta (1)$	$$$\ ثيتا (ن)$ (متوقع)	$$$\ ثيتا (ن)$
طريقة الاسم المستعار ساذجة	$$$O (n ^ 2)$		$$$\ Theta (1)$		$$$\ ثيتا (ن)$
طريقة الاسم المستعار	$$$O (n \ log n)$		$$$\ Theta (1)$		$$$\ ثيتا (ن)$

ومع ذلك ، هناك خوارزمية تعمل بشكل أسرع. إنها بسيطة بشكل مدهش ، وربما تكون أنظف خوارزمية لتطبيق طريقة الاسم المستعار. تم وصف هذه الخوارزمية لأول مرة في مقالة "خوارزمية خطية لتوليد أرقام عشوائية بتوزيع معين" بواسطة مايكل Woes ، وأصبحت الخوارزمية القياسية لتطبيق طريقة الاسم المستعار.

تعتمد خوارزمية Woese على استخدام قائمتين للعمل: إحداهما تحتوي على عناصر بارتفاع أقل من 1 ، والأخرى تحتوي على عناصر بارتفاع لا يقل عن 1. تزوج الخوارزمية باستمرار العناصر الأولى لكل قائمة عمل في أزواج. في كل تكرار ، نستهلك عنصرًا من قائمة القيم "الصغيرة" ، ومن المحتمل أن ننقل ما تبقى من العنصر من قائمة القيم "الكبيرة" إلى قائمة القيم "الصغيرة". تستخدم هذه الخوارزمية العديد من الثوابت:

• جميع العناصر في قائمة عمل صغيرة أقل من 1.
• جميع عناصر قائمة العمل "الكبيرة" على الأقل 1.
• مجموع العناصر في قائمة العمل يساوي دائمًا العدد الإجمالي للعناصر.

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

الخوارزمية: (أسلوب غير مستقر) Woes Alias

تحذير: هذه الخوارزمية عرضة لعدم الدقة العددية. يتم عرض خوارزمية أكثر استقرارًا رقميًا أدناه.

• التهيئة :
  
  1. إنشاء صفائف $$$Alias ​​$ و $$$Prob$ كل حجم $$$n$ .
  2. قم بإنشاء قائمتين عمل $$$$ صغي$ و $$$$ كبي$ .
  3. اضرب كل احتمال في $$$n$ .
  4. لكل احتمالية متدرجة $$$p_i$ :
     
     1. إذا $$$p_i <1$ أضف $$$i$ ل $$$$ صغي$ .
     2. خلاف ذلك ( $$$p_i \ ge 1$ ) إضافة $$$i$ ل $$$$ كبي$ .
     
     
  5. قائمة وداعا $$$$ صغي$ غير فارغ:
     
     1. حذف العنصر الأول من $$$$ صغي$ ؛ اتصل به $$$l$ .
     2. حذف العنصر الأول من $$$$ كبي$ ؛ اتصل به $$$g$ .
     3. وضعنا $$$Prob [l] = p_l$ .
     4. وضعنا $$$Alias ​​[l] = g$ .
     5. وضعنا $$$p_g: = p_g - (1 - p_l)$ .
     6. إذا $$$p_g <1$ أضف $$$g$ في $$$$ صغي$ .
     7. وإلا فإننا نضيف ($ p_g \ ge 1 $) $$$g$ في $$$$ كبي$ .
     
     
  6. قائمة وداعا $$$$ كبي$ غير فارغ:
     
     1. حذف العنصر الأول من $$$$ كبي$ ؛ اتصل به $$$g$ .
     2. وضعنا $$$Prob [g] = 1$ .
     
     
  
  
• الجيل :
  
  1. نقوم بتوليد لفة عظام صادقة من $$$n$ - عظم الوجه اتصل بالوجه $$$i$ .
  2. نرمي عملة غير متماثلة يسقط عليها النسر باحتمال $$$Prob [i]$ .
  3. إذا سقط نسر على عملة معدنية ، عد $$$i$ .
  4. عودة خلاف ذلك $$ .

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

في هذه الخوارزمية ، نوع قائمة العمل ليس مهمًا. في المقالة الأصلية لـ Woof ، يتم استخدام المكدسات كقائمة عمل ، لأنه يمكن تنفيذها بشكل فعال باستخدام المصفوفات ، ولكن إذا أردنا ، يمكننا استخدام قائمة الانتظار. ومع ذلك ، من أجل البساطة ، سنستخدم المكدس.

قبل متابعة تحليل الخوارزمية ، دعنا نحلل عملها باستخدام مثال. فكر في مثال باستخدام سبعة احتمالات $$$\ frac {1} {4}$ ، $$$\ frac {1} {5}$ ، $$$\ frac {1} {8}$ ، $$$\ frac {1} {8}$ ، $$$\ frac {1} {10}$ ، $$$\ frac {1} {10}$ ، $$$\ frac {1} {10}$ . للتأكيد على حقيقة أن الخوارزمية لا تقوم بفرز الاحتمالات ولا تتطلب فرزها ، فلنرتبها بترتيب عشوائي $$$\ frac {1} {8}$ ، $$$\ frac {1} {5}$ ، $$$\ frac {1} {10}$ ، $$$\ frac {1} {4}$ ، $$$\ frac {1} {10}$ ، $$$\ frac {1} {10}$ ، $$$\ frac {1} {8}$ . تبدأ الخوارزمية بإضافة هذه العناصر إلى مجموعتي عمل:


الآن سنضع الجزء العلوي من المكدس $$$$ صغي$ في وضعه عن طريق تحريك المستطيل الأرجواني إلى موقعه النهائي:


الآن نستخدم الجزء العلوي من المكدس $$$$ كبي$ (مستطيل فيروزي) لملء باقي العمود. منذ ذلك الحين $$$\ frac {7} {4} - \ frac {1} {8} = \ frac {13} {8} \ ge 1$ نترك الكتلة الفيروزية فوق المكدس $$$$ كبي$ :


ثم نكرر هذه العملية. انقل المستطيل من أعلى المكدس $$$$ صغي$ في العمود الخاص به ، ثم يكمل الجزء العلوي المفقود من المكدس $$$$ كبي$ :


ومرة أخرى:


في المرة التالية التي نكرر فيها هذه العملية ، نجد أنه على الرغم من أنه يمكننا استخدام كتلة الفيروز لملء المساحة الفارغة في الجدول ، ونتيجة لذلك ، سيصبح ارتفاع كتلة الفيروز أقل من واحد. لذلك ، سنحتاج إلى تحريك الكتلة الفيروزية إلى أعلى مجموعة القيم الصغيرة:


$$$Small$ , :


$$$Small$ , , :


, $$$Small$ , .


alias .

, . , , IEEE-754 double, . , , :

1. , $$$Small$ $$$Large$ , . , , $$$n$ , , $$$\frac{1}{n}$ , $$$1$ ( $$$Small$ , $$$Large$ ).
2. , , . , , $$$Large$ , $$$Small$ .

, $$$Small$ $$$Large$ . , , $$$Small$ , $$$Large$ .

, . , , , $$$Large$ . -, , $$$1$ , , $$$1$ . , . :

: Alias-

• :
  
  1. $$$Alias$ و $$$Prob$ , $$$n$ .
  2. , $$$Small$ و $$$Large$ .
  3. $$$n$ .
  4. $$$p_i$ :
     
     1. $$$p_i < 1$ , $$$i$ في $$$Small$ .
     2. ( $$$p_i \ge 1$ ) $$$i$ في $$$Large$ .
     
     
  5. $$$Small$ و $$$Large$ : ( $$$Large$ )
     
     1. $$$Small$ ; $$$l$ .
     2. $$$Large$ ; $$$g$ .
     3. $$$Prob[l] = p_l$ .
     4. $$$Alias[l] = g$ .
     5. $$$p_g := (p_g + p_l) - 1$ . ( . )
     6. $$$p_g < 1$ , $$$g$ في $$$Small$ .
     7. ( $$$p_g \ge 1$ ) $$$g$ في $$$Large$ .
     
     
  6. $$$Large$ :
     
     1. $$$Large$ ; $$$g$ .
     2. $$$Prob[g] = 1$ .
     
     
  7. $$$Small$ : - .
     
     1. $$$Small$ ; $$$l$ .
     2. $$$Prob[l] = 1$ .
     
     
  
  
• :
  
  1. $$$n$ - ; $$$i$ .
  2. , $$$Prob[i]$ .
  3. , $$$i$ .
  4. $$$Alias[i]$ .

, — . $$$\Theta(n)$ , . $$$\Theta(1)$ , , . $$$O(n)$ , () , . $$$O(n)$ , $$$Large$ و $$$Small$ $$$O(n)$ . $$$\Theta(n)$ , ( ) :

	$$$\Theta(n)$	$$$O(\prod_{i = 0}^n{d_i})$	$$$\Theta(1)$		$$$\Theta(n)$	$$$O(\prod_{i = 0}^n{d_i})$
	$$$\Theta(n)$		$$$\Theta(1)$	$$$\Theta(n)$	$$$\Theta(n)$
	$$$\Theta(n)$		$$$\Theta(\log n)$		$$$\Theta(n)$
	$$$O(n^2)$		$$$\Theta(1)$	$$$O(\log n)$	$$$\Theta(n)$
/	$$$\Theta(n)$		$$$\Theta(1)$	$$$\Theta(n)$ ()	$$$\Theta(n)$
Alias-	$$$O(n^2)$		$$$\Theta(1)$		$$$\Theta(n)$
Alias-	$$$O(n \log n)$		$$$\Theta(1)$		$$$\Theta(n)$
Alias-	$$$\Theta(n)$		$$$\Theta(1)$		$$$\Theta(n)$

! ! , . , (alias- ) , - .

alias- , , - , alias- Java , .

, !