كيفية اختبار العشوائية (مثال - خلط)

Question

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

افترض أن لديك خوارزمية أن يولد العشوائية.الآن كيف يمكنك اختبار ذلك ؟ أو أن تكون أكثر مباشرة - افترض أن لديك خوارزمية المراوغات مجموعة من البطاقات ، كيف يمكنك اختبار ذلك تماما عشوائية الخوارزمية ؟

لإضافة بعض نظرية المشكلة - مجموعة من البطاقات يمكن أن تكون تعديلا في 52!(52 مضروب) بطرق مختلفة.اتخاذ مجموعة من البطاقات, خلط ورق اللعب باليد وكتابة ترتيب جميع البطاقات.ما هو احتمال أن كنت قد حصلت بالضبط المراوغة ؟ الجواب:1 / 52!.

ما هي فرصة أن كنت بعد خلط ، سوف تحصل على A, K, Q, J ...من كل دعوى في سلسلة?الجواب 1 / 52!

هكذا, مجرد خلط مرة وتبحث في النتيجة سوف تعطيك اي معلومات عن خلط الخوارزميات العشوائية.مرتين و لديك المزيد من المعلومات ثلاثة أكثر...

كيف يمكنك اختبار الصندوق الأسود خلط خوارزمية عشوائية?

Answer 1

الإحصاءات.بحكم الواقع القياسية لاختبار RNGs هو اشداء جناح (أصلا متوفرة في http://stat.fsu.edu/pub/diehard).بدلا من ذلك ، Ent البرنامج يوفر الاختبارات التي هي أبسط تفسير ولكن أقل شمولا.

أما بالنسبة خلط الخوارزميات استخدام المعروفة خوارزمية مثل فيشر-ييتس (أ.ك.و "كانوث خلط").خلط ورق اللعب سيكون موحدا عشوائية طالما الأساسية RNG بشكل موحد عشوائي.إذا كنت تستخدم جافا, هذه الخوارزمية هو متوفر في المكتبة القياسية (انظر مجموعات.خلط ورق اللعب).

وربما لا يهم بالنسبة لمعظم التطبيقات, ولكن أن تكون على علم أن معظم RNGs لا توفر درجة كافية من الحرية لإنتاج كل ممكن التقليب من 52 بطاقة سطح السفينة (شرح هنا).

Answer 2

هنا واحد الاختيار بسيطة التي يمكنك القيام بها.ويستخدم توليد الأرقام العشوائية لتقدير بي.هذا ليس دليل على العشوائية ، ولكن الفقراء RNGs عادة لا تفعل جيدا على ذلك (أنهم سيعودون شيء مثل 3.8 2.5 أو بالأحرى ~3.14).

ومن الناحية المثالية سيكون هذا مجرد واحدة من العديد من الاختبارات التي سوف تعمل على التحقق من العشوائية.

شيء آخر يمكنك التحقق من الانحراف المعياري الإخراج.المتوقع الانحراف المعياري موحد توزيع السكان القيم في النطاق من 0..ن النهج n/الجذر التربيعي(12).

/**
 * This is a rudimentary check to ensure that the output of a given RNG
 * is approximately uniformly distributed.  If the RNG output is not
 * uniformly distributed, this method will return a poor estimate for the
 * value of pi.
 * @param rng The RNG to test.
 * @param iterations The number of random points to generate for use in the
 * calculation.  This value needs to be sufficiently large in order to
 * produce a reasonably accurate result (assuming the RNG is uniform).
 * Less than 10,000 is not particularly useful.  100,000 should be sufficient.
 * @return An approximation of pi generated using the provided RNG.
 */
public static double calculateMonteCarloValueForPi(Random rng,
                                                   int iterations)
{
    // Assumes a quadrant of a circle of radius 1, bounded by a box with
    // sides of length 1.  The area of the square is therefore 1 square unit
    // and the area of the quadrant is (pi * r^2) / 4.
    int totalInsideQuadrant = 0;
    // Generate the specified number of random points and count how many fall
    // within the quadrant and how many do not.  We expect the number of points
    // in the quadrant (expressed as a fraction of the total number of points)
    // to be pi/4.  Therefore pi = 4 * ratio.
    for (int i = 0; i < iterations; i++)
    {
        double x = rng.nextDouble();
        double y = rng.nextDouble();
        if (isInQuadrant(x, y))
        {
            ++totalInsideQuadrant;
        }
    }
    // From these figures we can deduce an approximate value for Pi.
    return 4 * ((double) totalInsideQuadrant / iterations);
}

/**
 * Uses Pythagoras' theorem to determine whether the specified coordinates
 * fall within the area of the quadrant of a circle of radius 1 that is
 * centered on the origin.
 * @param x The x-coordinate of the point (must be between 0 and 1).
 * @param y The y-coordinate of the point (must be between 0 and 1).
 * @return True if the point is within the quadrant, false otherwise.
 */
private static boolean isInQuadrant(double x, double y)
{
    double distance = Math.sqrt((x * x) + (y * y));
    return distance <= 1;
}

Answer 3

أولا من المستحيل أن نعرف على وجه اليقين إذا معينة محدودة الإنتاج "عشوائية حقا" كما ذكرتم ، أي إخراج من الممكن.

ما الذي يمكن القيام به هو اتخاذ سلسلة من النواتج و التحقق من قياسات مختلفة من هذا التسلسل ضد ما هو أكثر احتمالا.يمكنك استخلاص نوع من الثقة النتيجة أن توليد الخوارزمية هو القيام بعمل جيد.

على سبيل المثال ، يمكنك التحقق من إخراج 10 مختلفة المراوغات.تعيين عدد 0-51 لكل بطاقة متوسط البطاقة في موقف 6 عبر المراوغات.تلاقي المتوسط هو 25.5 لذا سوف يفاجأ أن نرى قيمة 1 هنا.هل يمكن استخدام نظرية الحد المركزي للحصول على تقدير مدى احتمال كل متوسط لموقف معين.

ولكن لا يجب أن تتوقف هنا!لأن هذه الخوارزمية يمكن أن ينخدع نظام فقط المناوبين بين اثنين من المراوغات التي تم تصميمها لإعطاء الدقيقة بمعدل 25.5 في كل موقف.كيف يمكننا أن نفعل ما هو أفضل ؟

ونحن نتوقع توزيع موحد (المساواة احتمال أي بطاقة) في كل موقف ، عبر مختلف المراوغات.حتى بين 10 المراوغات يمكننا محاولة للتحقق من أن الخيارات 'نظرة موحدة.' هذا هو في الأساس مجرد نسخة مخفضة من المشكلة الأصلية.هل يمكن أن تحقق ذلك الانحراف المعياري تبدو معقولة ، أن مين هو معقول, max قيمة كذلك.يمكنك أيضا التحقق من أن القيم الأخرى ، مثل أقرب اثنين من بطاقات (من قبل لدينا الأرقام المخصصة), أيضا معنى.

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

Answer 4

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

المجلد 2 من كانوث فن برمجة الكمبيوتر يعطي عددا من الاختبارات التي يمكن استخدامها في أقسام 3.3.2 (الاختبارات التجريبية) و 3.3.4 (الطيفية اختبار) ونظرية وراءها.

Answer 5

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

إذا كان هو حقا عشوائي على الرسم البياني سوف يكون في الغالب حتى.

Answer 6

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

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

Answer 7

أنا لست تماما التالية سؤالك.تقول

افترض أن لديك خوارزمية أن يولد العشوائية.الآن كيف يمكنك اختبار ذلك ؟

ماذا تعنين ؟ إذا كنت على افتراض انك يمكن أن تولد العشوائية ، هناك حاجة إلى اختبار.

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

السؤال الصعب هو ما إذا كان يمكن الوثوق بك RNG. هنا عينة ربط الناس في مناقشة هذه المسألة في سياق محدد.

Answer 8

اختبار 52!إمكانيات طبعا من المستحيل.بدلا من ذلك, حاول المراوغة على أعداد أقل من البطاقات ، 3 ، 5 ، 10.ثم يمكنك اختبار المليارات من المراوغات و استخدام الرسم البياني و مربع كاي الإحصائية اختبار لإثبات أن كل التقليب هو الخروج من "حتى" عدد من المرات.

Answer 9

أي مدونة حتى الآن, لذلك أنا نسخ ولصق اختبار جزء من جوابي إلى السؤال الأصلي.

  // ...
  int main() {
    typedef std::map<std::pair<size_t, Deck::value_type>, size_t> Map;
    Map freqs;    
    Deck d;
    const size_t ntests = 100000;

    // compute frequencies of events: card at position
    for (size_t i = 0; i < ntests; ++i) {
      d.shuffle();
      size_t pos = 0;
      for(Deck::const_iterator j = d.begin(); j != d.end(); ++j, ++pos) 
        ++freqs[std::make_pair(pos, *j)]; 
    }

    // if Deck.shuffle() is correct then all frequencies must be similar
    for (Map::const_iterator j = freqs.begin(); j != freqs.end(); ++j)
      std::cout << "pos=" << j->first.first << " card=" << j->first.second 
                << " freq=" << j->second << std::endl;    
  }

هذا الرمز لا اختبار العشوائية الكامنة المزيف عدد المولدات.اختبار PRNG العشوائية في كل فرع من فروع العلم.

Answer 10

من أجل اختبار سريع ، يمكنك دائما محاولة ضغط عليه.مرة واحدة أنها لا ضغط ، ثم يمكنك الانتقال إلى اختبارات أخرى.

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

Answer 11

التأمل بنفسي ما أود القيام به هو شيء من هذا القبيل:

الإعداد (البرمجية الزائفة)

// A card has a Number 0-51 and a position 0-51
int[][] StatMatrix = new int[52][52]; // Assume all are set to 0 as starting values
ShuffleCards();
ForEach (card in Cards) {
   StatMatrix[Card.Position][Card.Number]++;
}

هذا يعطينا مصفوفة 52x52 تشير إلى عدد المرات بطاقة قد انتهى في موقف معين.كرر هذا عدد كبير من المرات (وأود أن تبدأ مع 1000 ، ولكن الناس أفضل في الإحصاءات من لي قد تعطي أفضل رقم).

تحليل مصفوفة

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

statMatrix[position][card] / numberOfShuffle = 1/52.

لذلك أود أن تحسب كم من هذا العدد نحن.