باستخدام احتمال واحد تعيين لتوليد آخر [مكررة

Question

هذا السؤال لديه بالفعل إجابة هنا:

• توسيع نطاق عشوائي من 1-5 إلى 1-7 77 إجابات

كيف يمكنني إنشاء احتمال أكبر مجموعة من مجموعة احتمالية أصغر؟
هذا من دليل تصميم الخوارزمية -Steven Seaiena
س:

استخدم مولد أرقام عشوائي (RNG04) الذي يولد أرقاما من {0،1،2،3،4} مع احتمال متساو لكتابة مولد أرقام عشوائي يولد أرقاما من 0 إلى 7 (RNG07) مع احتمال متساو؟

حاولت حوالي 3 ساعات الآن، معظمها على أساس تلخيص اثنين rng04 المخرجات. المشكلة هي أنه في هذه الحالة، فإن احتمال كل قيمة مختلفة - 4 يمكن أن تأتي مع احتمال 5/24 بينما 0 يحدث 0 1/24. حاولت بعض الطرق لإخفاءها، ولكن لا أستطيع ذلك.

يمكن أن يحل شخص ما هذا؟

Answer 1

عليك أن تجد طريقة للجمع بين المجموعتين من أرقام عشوائية (عشوائية الأولى والثانية {0,1,2,3,4} ) وإجراء n*n إمكانيات متميزة. في الأساس المشكلة هي أنه مع إضافة شيء مثل هذا

        X
      0 1 2 3 4

  0   0 1 2 3 4
Y 1   1 2 3 4 5
  2   2 3 4 5 6
  3   3 4 5 6 7
  4   4 5 6 7 8

الذي يحتوي على التكرارات، وهو ليس ما تريد. طريقة واحدة ممكنة للجمع بين المجموعتين ستكون Z = X + Y*5 أين X و Y هي الأرقام العشوائية. من شأنه أن يمنحك مجموعة من النتائج مثل هذا

        X
       0  1  2  3  4

  0    0  1  2  3  4
Y 1    5  6  7  8  9
  2   10 11 12 13 14
  3   15 16 17 18 19
  4   20 21 22 23 24

حتى الآن أن لديك مجموعة أكبر من أرقام عشوائية، تحتاج إلى القيام بالعكس وجعلها أصغر. هذه المجموعة لديها 25 القيم المميزة (لأنك بدأت مع 5، واستخدمت رقمين عشوائيين، لذلك 5*5=25). المجموعة التي تريدها لديها 8 قيم مميزة. وسيل وسيلة للقيام بذلك سيكون

x = rnd(5)  // {0,1,2,3,4}
y = rnd(5)  // {0,1,2,3,4}
z = x+y*5   // {0-24}
random07 = x mod 8

هذا سيكون بالفعل مجموعة من {0,7}. وبعد لكن القيم {1,7} سوف تظهر 3/25 مرات، والقيمة 0 سوف تظهر 4/25 مرات. هذا بسبب 0 mod 8 = 0, 8 mod 8 = 0, 16 mod 8 = 0 و 24 mod 8 = 0.

لإصلاح هذا، يمكنك تعديل التعليمات البرمجية أعلاه إلى هذا.

do {
  x = rnd(5)  // {0,1,2,3,4}
  y = rnd(5)  // {0,1,2,3,4}
  z = x+y*5   // {0-24}
while (z != 24)

random07 = z mod 8

هذا سوف يستغرق قيمة واحدة (24) يلقي الاحتمالات الخاصة بك وتجاهله. إنشاء رقم عشوائي جديد إذا كنت تحصل على قيمة "سيئة" مثل هذا سيجعل خوارزميةك تعمل لفترة أطول قليلا (في هذه الحالة 1/25 من الوقت، فسوف يستغرق الأمر 2x طالما يجب تشغيله، 1/625 سوف يستغرق 3x طويلة، إلخ). لكنها ستمنحك الاحتمالات الصحيحة.

Answer 2

المشكلة الحقيقية، بالطبع، هي حقيقة أن الأرقام الموجودة في منتصف المجموع (4 في هذه الحالة) تحدث في العديد من المجموعات (0 + 4، 1 + 3، إلخ)، في حين أن 0 و 8 لديهم طريقة واحدة بالضبط أن تنتج.

لا أعرف كيفية حل هذه المشكلة، لكنني سأحاول تقليلها قليلا بالنسبة لك. بعض النقاط التي يجب مراعاتها:

• يحتوي النطاق 0-7 على 8 قيم محتملة، لذلك في نهاية المطاف إجمالي العدد الإجمالي للحالات المحتملة التي يجب أن تهدف إلى أن تكون مضاعفة 8. بهذه الطريقة يمكن أن يكون لديك عدد لا يتجزأ من التوزيعات لكل قيمة في هذا الشموفين.
• عندما تأخذ مجموع وظائف كثافة كثافة، فإن عدد المواقف المحتملة (ليس بالضرورة مميزة بالضرورة عند تقييم المبلغ، فقط من حيث التباديل المختلفة للمدخلات) يساوي نتاج حجم كل مجموعة من مجموعات الإدخال.
• وهكذا، تم تخصيص مجموعات اثنين {0،1،2،3،4} معا، لديك 5 * 5 = 25 إمكانيات.
• لن يكون من الممكن الحصول على مضاعف من ثمانية (انظر النقطة الأولى) من صلاحيات 5 (انظر النقطة الثانية، ولكن استقرها إلى أي عدد من المجموعات> 1)، لذلك ستحتاج إلى فائض من المواقف المحتملة في وظيفة وتجاهل بعض منهم إذا حدثت.
• أبسط طريقة للقيام بذلك، بقدر ما أستطيع أن أرى في هذه المرحلة، هي استخدام مجموع 2 {0،1،2،3،4} مجموعات (25 إمكانيات) وتجاهل 1 (لمغادرة 24، متعددة من 8).
• وبالتالي تم تخفيض التحدي الآن إلى هذا: ابحث عن طريقة لتوزيع الاحتمالات ال 24 المتبقية بين قيم الإخراج الثمانية. لذلك، ربما لن ترغب في استخدام المجموع، بل مجرد قيم الإدخال.

إحدى طرق القيام بذلك، تخيل رقم في قاعدة 5 شيدت من مدخلاتك. تجاهل 44 (هذا هو القيمة الخامسة والعشرون 25، إذا حصلت عليه، توليف مجموعة جديدة من المدخلات) وأخذ الآخرين، Modulo 8، وستحصل على 0-7 عبر 24 مجموعات مدخل مختلفة (3 لكل منهما)، والتي هو توزيع متساو.

Answer 3

سيكون منطقي هذا:

rn07 = 0;
do {
  num = rng04;
}
while(num == 4);

rn07 = num * 2;
do {
  num = rng04;
}
while(num == 4);

rn07 += num % 2