c++ - لماذا راند()٪ 6 متحيز؟




random std (4)

لست من مستخدمي C ++ ذوي الخبرة بأي وسيلة ، لكنني كنت مهتمًا بمعرفة ما إذا كانت الإجابات الأخرى المتعلقة std::rand()/((RAND_MAX + 1u)/6) أقل تحيزًا من 1+std::rand()%6 يحمل حقيقة. لذلك كتبت برنامج اختبار لجدولة النتائج لكلتا الطريقتين (لم أكتب C ++ في الأعمار ، يرجى التحقق من ذلك). يوجد رابط لتشغيل الكود here . مستنسخة أيضا على النحو التالي:

// Example program
#include <cstdlib>
#include <iostream>
#include <ctime>
#include <string>

int main()
{
    std::srand(std::time(nullptr)); // use current time as seed for random generator

    // Roll the die 6000000 times using the supposedly unbiased method and keep track of the results

    int results[6] = {0,0,0,0,0,0};

    // roll a 6-sided die 20 times
    for (int n=0; n != 6000000; ++n) {
        int x = 7;
        while(x > 6) 
            x = 1 + std::rand()/((RAND_MAX + 1u)/6);  // Note: 1+rand()%6 is biased

        results[x-1]++;
    }

    for (int n=0; n !=6; n++) {
        std::cout << results[n] << ' ';
    }

    std::cout << "\n";


    // Roll the die 6000000 times using the supposedly biased method and keep track of the results

    int results_bias[6] = {0,0,0,0,0,0};

    // roll a 6-sided die 20 times
    for (int n=0; n != 6000000; ++n) {
        int x = 7;
        while(x > 6) 
            x = 1 + std::rand()%6;

        results_bias[x-1]++;
    }

    for (int n=0; n !=6; n++) {
        std::cout << results_bias[n] << ' ';
    }
}

ثم أخذت إخراج هذا واستخدمت الدالة chisq.test في R لإجراء اختبار Chi-square لمعرفة ما إذا كانت النتائج مختلفة بشكل كبير عن المتوقع. يذهب سؤال stackexchange هذا إلى مزيد من التفاصيل حول استخدام اختبار chi-square لاختبار عدالة الموت: كيف يمكنني اختبار ما إذا كانت وفاة عادلة؟ . فيما يلي النتائج لبضع مرات:

> ?chisq.test
> unbias <- c(100150, 99658, 100319, 99342, 100418, 100113)
> bias <- c(100049, 100040, 100091, 99966, 100188, 99666 )

> chisq.test(unbias)

Chi-squared test for given probabilities

data:  unbias
X-squared = 8.6168, df = 5, p-value = 0.1254

> chisq.test(bias)

Chi-squared test for given probabilities

data:  bias
X-squared = 1.6034, df = 5, p-value = 0.9008

> unbias <- c(998630, 1001188, 998932, 1001048, 1000968, 999234 )
> bias <- c(1000071, 1000910, 999078, 1000080, 998786, 1001075   )
> chisq.test(unbias)

Chi-squared test for given probabilities

data:  unbias
X-squared = 7.051, df = 5, p-value = 0.2169

> chisq.test(bias)

Chi-squared test for given probabilities

data:  bias
X-squared = 4.319, df = 5, p-value = 0.5045

> unbias <- c(998630, 999010, 1000736, 999142, 1000631, 1001851)
> bias <- c(999803, 998651, 1000639, 1000735, 1000064,1000108)
> chisq.test(unbias)

Chi-squared test for given probabilities

data:  unbias
X-squared = 7.9592, df = 5, p-value = 0.1585

> chisq.test(bias)

Chi-squared test for given probabilities

data:  bias
X-squared = 2.8229, df = 5, p-value = 0.7273

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

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

في الأساس ، باختصار ، حصل على البذرة الصحيحة وعدد التجارب التي قد يحصل عليها نتيجة زائفة.

عند قراءة كيفية استخدام std :: rand ، وجدت هذا الكود على cppreference.com

int x = 7;
while(x > 6) 
    x = 1 + std::rand()/((RAND_MAX + 1u)/6);  // Note: 1+rand()%6 is biased

ما هو الخطأ في التعبير على اليمين؟ حاول ذلك ويعمل تماما.


هناك rand() % 6 ( 1+ لا تؤثر على أي مشكلة).

أولاً ، كما أوضحت عدة إجابات ، إذا كانت البتات المنخفضة rand() غير منتظمة بشكل مناسب ، فإن نتيجة المشغل الباقي ليست موحدة أيضًا.

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

كمثال متطرف ، ادعي أن rand() ينتج قيمًا موزعة بشكل موحد في النطاق [0..6] . إذا نظرت إلى القيم المتبقية لتلك القيم ، عندما تُرجع rand() قيمة في النطاق [0..5] ، ينتج الباقي نتائج موزعة بشكل موحد في النطاق [0..5] . عندما ترجع rand() 6 ، ترجع rand() % 6 صفر ، تمامًا كما لو أن rand() قد أرجعت 0. لذا تحصل على توزيع يساوي ضعف عدد صفر مثل أي قيمة أخرى.

والثاني هو المشكلة الحقيقية مع rand() % 6 .

طريقة تجنب هذه المشكلة هي تجاهل القيم التي من شأنها أن تنتج تكرارات غير موحدة. تقوم بحساب أكبر مضاعفات من 6 أقل من RAND_MAX أو مساوية له ، وكلما عادت rand() قيمة أكبر من أو تساوي المضاعفات التي ترفضها وتدعو `rand () مرة أخرى ، عدة مرات عند الحاجة.

وبالتالي:

int max = 6 * ((RAND_MAX + 1u) / 6)
int value = rand();
while (value >= max)
    value = rand();

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


يمكن للمرء أن يفكر في مولد الأرقام العشوائية باعتباره يعمل على مجموعة من الأرقام الثنائية. يقوم المولد بتحويل التيار إلى أرقام عن طريق تقطيعه إلى أجزاء. إذا كانت الدالة std:rand تعمل مع RAND_MAX من 32767 ، RAND_MAX 15 بت في كل شريحة.

عندما يأخذ المرء الوحدات المكونة للرقم بين 0 و 32767 ضمنيًا ، نجد أن 5462 '0's و' 1's ولكن 5461 '2' و '3's' و '4's' و '5's فقط. وبالتالي فإن النتيجة متحيزة. كلما كانت قيمة RAND_MAX أكبر ، كلما كان هناك تحيز أقل ، لكنه لا مفر منه.

ما هو غير متحيز هو رقم في النطاق [0 .. (2 ^ n) -1]. يمكنك إنشاء رقم أفضل (نظريًا) في النطاق 0..5 عن طريق استخراج 3 بتات ، وتحويلها إلى عدد صحيح في النطاق 0..7 ورفض 6 و 7.

يأمل المرء أن يكون لكل بت في تدفق البت فرصة متساوية في أن يكون "0" أو "1" بغض النظر عن مكانه في الدفق أو قيم البتات الأخرى. هذا صعب للغاية في الممارسة. تقدم العديد من التطبيقات المختلفة لبرامج PRNG تنازلات مختلفة بين السرعة والجودة. يوفر المولد التطابق الخطي مثل std::rand أسرع سرعة بأقل جودة. يوفر مولد التشفير أعلى جودة لأدنى سرعة.


يوضح رمز المثال هذا أن std::rand هي حالة من حالات عبادة البضائع القديمة التي يجب أن تجعل حواجبك تثير كل مرة تراها.

هناك العديد من القضايا هنا:

عادة ما يفترض الناس المتعاقدون - حتى النفوس الفقيرة التعساء التي لا تعرف أفضل من ذلك ولن يفكروا في هذه الشروط بالتحديد - هي أن عينات rand من التوزيع الموحد على الأعداد الصحيحة في 0 ، 1 ، 2 ، ... ، RAND_MAX ، وكل مكالمة تعطي عينة مستقلة .

المشكلة الأولى هي أن العقد المفترض ، عينات عشوائية موحدة موحدة في كل مكالمة ، ليست في الواقع ما تقوله الوثائق - وفي الممارسة العملية ، فشلت التطبيقات تاريخياً في تقديم حتى أقرب مجاز للاستقلال. على سبيل المثال ، تقول C99 §7.20.2.1 "دالة rand " ، دون توضيح:

تحسب دالة rand سلسلة من الأعداد الصحيحة العشوائية الزائفة في النطاق من 0 إلى RAND_MAX .

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

تطبيق تاريخي نموذجي في C يعمل مثل هذا:

static unsigned int seed = 1;

static void
srand(unsigned int s)
{
    seed = s;
}

static unsigned int
rand(void)
{
    seed = (seed*1103515245 + 12345) % ((unsigned long)RAND_MAX + 1);
    return (int)seed;
}

هذا له خاصية مؤسفة أنه على الرغم من أنه يمكن توزيع عينة واحدة بشكل موحد تحت بذرة عشوائية موحدة (والتي تعتمد على القيمة المحددة لـ RAND_MAX ) ، فإنها تتناوب بين الأعداد الصحيحة الزوجية والغريبة في المكالمات المتتالية - بعد

int a = rand();
int b = rand();

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

المشكلة الثانية هي أنه حتى لو كانت كل مكالمة قد أخذت عينات بشكل مستقل عن توزيع عشوائي موحد على 0 ، 1 ، 2 ، ... ، RAND_MAX ، فلن يتم توزيع نتيجة rand() % 6 بشكل موحد في 0 ، 1 ، 2 ، 3 ، 4 ، 5 مثل لفافة يموت ، ما لم RAND_MAX مع -1 modulo 6. مثال مضاد بسيط: إذا كان RAND_MAX = 6 ، ثم من rand() ، فإن جميع النتائج لها احتمال متساوٍ 1/7 ، ولكن من rand() % 6 ، النتيجة 0 لها احتمال 2/7 بينما جميع النتائج الأخرى لها احتمال 1/7.

الطريقة الصحيحة للقيام بذلك هي مع أخذ عينات الرفض: ارسم بشكل متكرر عينة عشوائية موحدة s من 0 ، 1 ، 2 ، ... ، RAND_MAX ، ورفض (على سبيل المثال) النتائج 0 ، 1 ، 2 ، ... ، ((RAND_MAX + 1) % 6) - 1 إذا حصلت على واحدة منها ، فابدأ من جديد ؛ خلاف ذلك ، العائد s % 6 .

unsigned int s;
while ((s = rand()) < ((unsigned long)RAND_MAX + 1) % 6)
    continue;
return s % 6;

بهذه الطريقة ، تكون مجموعة النتائج من rand() التي نقبلها قابلة للقسمة بالتساوي على 6 ، ويتم الحصول على كل نتيجة ممكنة من s % 6 بنفس العدد من النتائج المقبولة من rand() ، لذلك إذا تم توزيع rand() بشكل موحد إذن هو كذلك لا يوجد عدد محدد من التجارب ، ولكن العدد المتوقع أقل من 2 ، واحتمال النجاح يزداد أضعافا مضاعفة مع عدد التجارب.

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

تمرين للقارئ: أثبت أن الشفرة في cppreference.com تعطي توزيعا موحدا على اللفافات إذا أسفرت rand() عن توزيع موحد في 0 ، 1 ، 2 ، ... ، RAND_MAX .

تمرين للقارئ: لماذا تفضل أن ترفض مجموعة أو مجموعات فرعية أخرى؟ ما هو الحساب المطلوب لكل تجربة في الحالتين؟

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

يمكنك الذهاب إلى المسار الهائل الذي يحتوي على هندسة رائعة وفئة C ++ 11 في الفئة std::uniform_int_distribution مع جهاز عشوائي مناسب ومحرك عشوائي مفضل لديك مثل std::mt19937 twister std::mt19937 للعب مع الزهر مع ابن عمك البالغ من العمر أربع سنوات ، لكن حتى هذا لن يكون مناسبًا لإنشاء مواد تشفير أساسية - و Mersenne الإعصار هو خنزير مساحة فظيعة للغاية مع حالة متعددة كيلوبايت تعيث فسادا على ذاكرة التخزين المؤقت وحدة المعالجة المركزية الخاصة بك مع وقت الإعداد فاحش ، لذلك فهو سيء حتى بالنسبة ، على سبيل المثال ، محاكاة مونت كارلو الموازية مع الأشجار القابلة للاستنساخ من الحوسبة الفرعية ؛ من المرجح أن تنشأ شعبيتها بشكل أساسي من اسمها الجذاب. ولكن يمكنك استخدامه في لعبة النرد المتداول مثل هذا المثال!

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





std