الأرقام العشوائية: التوليد والاختبار

تعتمد كل محاكاة في هذا المقرر على الأرقام العشوائية. فهي التي قادت جداول المحاكاة وهي التي أعطت أزمنة ما بين الوصول وأزمنة الخدمة في طابور الخادم الواحد. يعرض هذا القسم كيف ينتج الحاسوب هذه الأرقام بمولدين. ويعرض كيف تتحقق ثلاثة اختبارات إحصائية من أن الأرقام تتصرف مثل الأرقام العشوائية الحقيقية: أي أنها موزعة توزيعا منتظما (uniform) على [0, 1] ومستقلة (independent) بعضها عن بعض. ونحل مسائل التمرين 3 الخمس كلها خطوة بخطوة.

الأهداف

• حساب متتالية المولد الضربي (multiplicative generator) وإيجاد دورته (cycle) وطول دورته (period).
• حساب أرقام عشوائية في [0, 1] باستخدام المولد الخطي المتطابق (linear congruential generator, LCG).
• تطبيق اختبار كولموجوروف-سميرنوف (Kolmogorov-Smirnov) للتحقق من أن عينة صغيرة موزعة توزيعا منتظما.
• تطبيق اختبار مربع كاي (chi-square) للتحقق من أن عينة كبيرة موزعة توزيعا منتظما.
• تطبيق اختبار الارتباط الذاتي (autocorrelation) للتحقق من أن الأرقام التي تفصل بينها مسافة ثابتة مستقلة.
• قراءة القيمة الحرجة (critical value) من الجدول الصحيح وإعلان القرار.

1. ما المطلوب من الرقم العشوائي

تحول المحاكاة الأرقام العشوائية $R_1, R_2, \ldots$ إلى أحداث عشوائية: وصول عميل أو زمن خدمة أو طلب. ولكي تكون النتائج صحيحة يجب أن تتوفر في الأرقام خاصيتان:

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

2. توليد الأرقام العشوائية

المولد الضربي

$$Z_i = (a \, Z_{i-1}) \bmod m$$

• $Z_0$ هي البذرة (seed) وهي القيمة الابتدائية.
• $a$ هو المعامل الضربي (multiplier) و$m$ هو المقياس (modulus).
• x mod m هو باقي قسمة x على m. ولذلك تقع كل قيمة $Z_i$ بين 0 وm - 1.

تعتمد كل قيمة $Z_i$ على $Z_{i-1}$ وحدها. فإذا ظهرت قيمة للمرة الثانية فإن المتتالية تتكرر من تلك النقطة: أي أن المولد دخل في دورة (cycling). وعدد القيم في الدورة الواحدة هو طول الدورة (period). والدورة الطويلة أفضل لأن الأرقام تبدأ في التكرار في وقت متأخر.

السؤال 1 (أ): Z0 = 1, a = 11, m = 16

$$\begin{aligned} Z_1 &= (11 \times 1) \bmod 16 = 11 \bmod 16 = 11 \\ Z_2 &= (11 \times 11) \bmod 16 = 121 \bmod 16 = 9 \\ Z_3 &= (11 \times 9) \bmod 16 = 99 \bmod 16 = 3 \\ Z_4 &= (11 \times 3) \bmod 16 = 33 \bmod 16 = 1 \\ Z_5 &= (11 \times 1) \bmod 16 = 11 \quad \text{(cycling)} \end{aligned}$$

بما أن $Z_4 = Z_0 = 1$ فإن الدورة هي 1, 11, 9, 3 وطول الدورة m / 4 = 16 / 4 = 4 أرقام.

السؤال 1 (ب): Z0 = 2, a = 11, m = 16

$$\begin{aligned} Z_1 &= (11 \times 2) \bmod 16 = 22 \bmod 16 = 6 \\ Z_2 &= (11 \times 6) \bmod 16 = 66 \bmod 16 = 2 \\ Z_3 &= (11 \times 2) \bmod 16 = 6 \quad \text{(cycling)} \end{aligned}$$

طول الدورة هنا 2 فقط. قيمتا a وm هما نفسهما في (أ) ولم تتغير إلا البذرة فانخفض طول الدورة من 4 إلى 2. فاختيار البذرة مهم.

السؤال 1 (ج): Z0 = 1, a = 2, m = 13

$$\begin{aligned} Z_1 &= (2 \times 1) \bmod 13 = 2 \\ Z_2 &= (2 \times 2) \bmod 13 = 4 \\ Z_3 &= (2 \times 4) \bmod 13 = 8 \\ Z_4 &= (2 \times 8) \bmod 13 = 16 \bmod 13 = 3 \\ Z_5 &= (2 \times 3) \bmod 13 = 6 \\ Z_6 &= (2 \times 6) \bmod 13 = 12 \\ Z_7 &= (2 \times 12) \bmod 13 = 24 \bmod 13 = 11 \\ Z_8 &= (2 \times 11) \bmod 13 = 22 \bmod 13 = 9 \\ Z_9 &= (2 \times 9) \bmod 13 = 18 \bmod 13 = 5 \\ Z_{10} &= (2 \times 5) \bmod 13 = 10 \\ Z_{11} &= (2 \times 10) \bmod 13 = 20 \bmod 13 = 7 \\ Z_{12} &= (2 \times 7) \bmod 13 = 14 \bmod 13 = 1 \quad \text{(cycling)} \end{aligned}$$

طول الدورة 12 = m - 1: إذ تظهر كل قيمة من 1 إلى 12 مرة واحدة قبل أن تتكرر المتتالية. وهذه أطول دورة ممكنة عند m = 13 لأن 0 لا يظهر أبدا (فإذا صارت Z = 0 كانت كل القيم بعدها 0 أيضا).

ملاحظة على ورقة التمرين. الجدول في الورقة صحيح لكن سطور الخطوات تتخطى قيمة واحدة: فهي تنتقل من $Z_6 = 12$ مباشرة إلى 24 mod 13 = 9. والصحيح أن 24 mod 13 = 11 هي $Z_7$ وأن 9 تأتي بعدها بخطوة واحدة كما يبين الجدول.

السؤال 1 (د): Z0 = 2, a = 3, m = 13

$$\begin{aligned} Z_1 &= (3 \times 2) \bmod 13 = 6 \\ Z_2 &= (3 \times 6) \bmod 13 = 18 \bmod 13 = 5 \\ Z_3 &= (3 \times 5) \bmod 13 = 15 \bmod 13 = 2 \quad \text{(cycling)} \end{aligned}$$

طول الدورة 3 فقط. فمع المقياس نفسه الذي في (ج) يعطي المعامل الضربي a = 3 دورة قصيرة جدا بينما أعطى a = 2 الدورة الكاملة التي طولها 12.

المولد الخطي المتطابق (LCG)

يضيف المولد الخطي المتطابق ثابتا c يسمى الزيادة (increment) قبل أخذ الباقي:

$$X_i = (a \, X_{i-1} + c) \bmod m$$

كل قيمة $X_i$ عدد صحيح من 0 إلى m - 1. وللحصول على رقم عشوائي في [0, 1] نقسم على المقياس:

$$R_i = \dfrac{X_i}{m}$$

السؤال 2: X0 = 27, a = 8, c = 47

عند m = 100 يكون الباقي هو آخر خانتين في العدد:

$$\begin{aligned} X_1 &= (8 \times 27 + 47) \bmod 100 = (216 + 47) \bmod 100 = 263 \bmod 100 = 63 \\ X_2 &= (8 \times 63 + 47) \bmod 100 = (504 + 47) \bmod 100 = 551 \bmod 100 = 51 \\ X_3 &= (8 \times 51 + 47) \bmod 100 = (408 + 47) \bmod 100 = 455 \bmod 100 = 55 \end{aligned}$$

وأول ثلاثة أرقام عشوائية في [0, 1] هي:

$$R_1 = \dfrac{63}{100} = 0.63, \quad R_2 = \dfrac{51}{100} = 0.51, \quad R_3 = \dfrac{55}{100} = 0.55$$

ملاحظة على ورقة التمرين. يعطي السؤال m = 102 لكن الحل يحسب بـm = 100. ونحن نتبع الحل. ومع m = 102 تكون الأعداد الصحيحة 59, 9, 17 وتكون الأرقام العشوائية 59/102 = 0.578 و9/102 = 0.088 و17/102 = 0.167.

3. اختبار الانتظام

يستخدم الاختباران فرضية واحدة هي فرضية العدم (null hypothesis) $H_0$: الأرقام موزعة توزيعا منتظما على [0, 1]. ويحسب كل منهما إحصاءة اختبار (test statistic) من البيانات ثم يقارنها بقيمة حرجة من جدول عند مستوى المعنوية (level of significance) $\alpha$. فإذا كانت الإحصاءة أصغر من القيمة الحرجة لا نرفض $H_0$.

اختبار كولموجوروف-سميرنوف

يقارن هذا الاختبار العينة بالتوزيع المنتظم المثالي نقطة بنقطة:

1. رتب الأرقام تصاعديا: $R_{(1)} \le R_{(2)} \le \ldots \le R_{(N)}$.
2. احسب أكبر مسافة فوق الخط المثالي:

$$D^{+} = \max_{1 \le i \le N} \left[ \dfrac{i}{N} - R_{(i)} \right]$$

3. احسب أكبر مسافة تحته:

$$D^{-} = \max_{1 \le i \le N} \left[ R_{(i)} - \dfrac{i - 1}{N} \right]$$

4. خذ $D = \max(D^{+}, D^{-})$.
5. اقرأ $D_{\alpha}$ المقابلة لـN و$\alpha$ من جدول KS. فإذا كان $D < D_{\alpha}$ لا نرفض $H_0$.

السؤال 3: 0.54, 0.73, 0.98, 0.11, 0.68 عند α = 0.05

بعد الترتيب تصبح الأرقام 0.11, 0.54, 0.68, 0.73, 0.98 ويكون N = 5:

$$D^{+} = 0.09, \quad D^{-} = 0.34, \quad D = \max(0.09, 0.34) = 0.34$$

من جدول KS نجد $D_{0.05} = 0.565$ عند N = 5. وبما أن $D = 0.34 < 0.565$ فإننا لا نرفض $H_0$: أي أن الأرقام تجتاز اختبار الانتظام.

اختبار مربع كاي

1. قسم [0, 1] إلى n من الفترات المتساوية (class intervals).
2. احسب $O_i$ وهو العدد المشاهد (observed) من القيم التي تقع في الفترة i.
3. احسب العدد المتوقع (expected) لكل فترة: $E_i = N / n$.
4. احسب الإحصاءة:

$$\chi_0^2 = \sum_{i=1}^{n} \dfrac{(O_i - E_i)^2}{E_i}$$

5. اقرأ $\chi^2_{\alpha, n-1}$ من جدول مربع كاي عند n - 1 من درجات الحرية (degrees of freedom). فإذا كان $\chi_0^2 < \chi^2_{\alpha, n-1}$ لا نرفض $H_0$.

السؤال 4: 100 رقم عند α = 0.05

تصنف البيانات في n = 10 فترات: [0, 0.1] و(0.1, 0.2] و(0.2, 0.3] وهكذا حتى (0.9, 1.0]. ومع N = 100 يكون العدد المتوقع في كل فترة $E_i = 100 / 10 = 10$ قيم.

$$\chi_0^2 = 3.4, \qquad \chi^2_{0.05, \, 9} = 16.9$$

نجد القيمة الجدولية في الصف n - 1 = 9 من جدول مربع كاي تحت العمود $\chi^2_{0.05}$. وبما أن $\chi_0^2 = 3.4 < 16.9$ فإننا لا نرفض $H_0$ وتعد البيانات موزعة توزيعا منتظما.

ملاحظة على ورقة التمرين. تكتب شريحة الاستنتاج $\chi_0^2 > \chi^2_{0.05, 9}$. والعلاقة الصحيحة هي $\chi_0^2 < \chi^2_{0.05, 9}$ (3.4 مقابل 16.9) ولهذا لا نرفض $H_0$.

4. اختبار الاستقلال: اختبار الارتباط الذاتي

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

• i هو موقع أول رقم نختبره.
• m هو الإزاحة (lag) وهي المسافة بين رقمين مختبرين. ولا يعني m هنا مقياس المولد.
• N هو عدد القيم في المتتالية.
• M هو أكبر عدد صحيح يبقي آخر رقم مختبر داخل المتتالية:

$$i + (M + 1) \, m \le N$$

وتقدير الارتباط الذاتي وانحرافه المعياري (standard deviation) وإحصاءة الاختبار هي:

$$\hat{\rho}_{im} = \dfrac{1}{M + 1} \left[ \sum_{k=0}^{M} R_{i + km} \, R_{i + (k+1)m} \right] - 0.25$$ $$\sigma_{\hat{\rho}_{im}} = \dfrac{\sqrt{13M + 7}}{12 (M + 1)}, \qquad Z_0 = \dfrac{\hat{\rho}_{im}}{\sigma_{\hat{\rho}_{im}}}$$

الفرضية $H_0$: الأرقام مستقلة. فإذا كان $-z_{\alpha/2} \le Z_0 \le z_{\alpha/2}$ لا نرفض $H_0$. وعند $\alpha = 0.05$ يكون $\alpha/2 = 0.025$ ولذلك نبحث عن الاحتمال التراكمي 0.975 في جدول التوزيع الطبيعي: $z_{0.025} = 1.96$.

السؤال 5: الأرقام في المواقع 3, 8, 13, ... عند α = 0.05

يبدأ الاختبار من الرقم الموجود في الموقع 3 فيكون i = 3. ومن الموقع 3 إلى الموقع 8 إزاحة قدرها m = 5. ولدينا N = 30.

$$3 + (M + 1) \times 5 \le 30 \;\Rightarrow\; 8 + 5M \le 30 \;\Rightarrow\; M \le 4.4 \;\Rightarrow\; M = 4$$

الأرقام المختبرة هي $R_3, R_8, R_{13}, R_{18}, R_{23}, R_{28}$ = 0.23, 0.28, 0.33, 0.27, 0.05, 0.36 وهي المكتوبة بخط عريض في الجدول أعلاه.

$$\begin{aligned} \hat{\rho}_{35} &= \dfrac{1}{5} \left[ R_3 R_8 + R_8 R_{13} + R_{13} R_{18} + R_{18} R_{23} + R_{23} R_{28} \right] - 0.25 \\ &= \dfrac{1}{5} \left[ (0.23)(0.28) + (0.28)(0.33) + (0.33)(0.27) + (0.27)(0.05) + (0.05)(0.36) \right] - 0.25 \\ &= \dfrac{1}{5} \left[ 0.0644 + 0.0924 + 0.0891 + 0.0135 + 0.0180 \right] - 0.25 \\ &= \dfrac{0.2774}{5} - 0.25 = 0.0555 - 0.25 = -0.1945 \end{aligned}$$ $$\sigma_{\hat{\rho}_{35}} = \dfrac{\sqrt{13 \times 4 + 7}}{12 \times 5} = \dfrac{\sqrt{59}}{60} = \dfrac{7.68}{60} = 0.128$$ $$Z_0 = \dfrac{-0.1945}{0.128} = -1.5195$$

وبما أن $-1.96 < -1.5195 < 1.96$ فإننا لا نرفض $H_0$: أي أن الأرقام في المواقع 3, 8, 13, ... تبدو مستقلة.

5. الأخطاء الشائعة

1. نسيان القسمة على m. يعطي المولد الخطي المتطابق أعدادا صحيحة. والرقم العشوائي في [0, 1] هو $X_i / m$: ففي السؤال 2 يصبح 63 هو 0.63.
2. اختبار الأرقام دون ترتيب. يحتاج اختبار KS إلى ترتيب الأرقام تصاعديا أولا. ولو استخدمنا الترتيب الأصلي في السؤال 3 لقوبل العمود i/N بالقيم الخطأ.
3. الخلط بين عمودي KS. تستخدم $D^{+}$ الفرق $i/N - R_{(i)}$ وتستخدم $D^{-}$ الفرق $R_{(i)} - (i-1)/N$. وكل منهما هو أكبر قيمة في عموده هو. أما القيم السالبة فلا يمكن أن تكون الأكبر.
4. درجات حرية خطأ. يقرأ جدول مربع كاي عند n - 1 من درجات الحرية حيث n عدد الفترات وليس عدد القيم: أي 9 وليس 99.
5. عكس القرار. في الاختبارات الثلاثة كلها تعني الإحصاءة الواقعة داخل الحد الحرج أننا لا نرفض $H_0$. أما ما يؤدي إلى الرفض فهو قيمة كبيرة لـ$D$ أو لـ$\chi_0^2$ أو لـ$|Z_0|$.
6. تقريب M إلى أعلى. M هو أكبر عدد صحيح يحقق $i + (M+1)m \le N$. ففي السؤال 5 يعطي M ≤ 4.4 القيمة M = 4. أما M = 5 فتحتاج إلى رقم في الموقع 33.

6. تدريب

حل كل مسألة ثم راجع الإجابات في نهاية هذه الصفحة. استخدم $D_{0.05} = 0.565$ عند N = 5 و$\chi^2_{0.05, 4} = 9.49$ و$z_{0.025} = 1.96$.

1. مولد ضربي فيه Z0 = 3 وa = 5 وm = 16. احسب القيم حتى تدخل المتتالية في دورة ثم أعط طول الدورة.
2. مولد خطي متطابق فيه X0 = 7 وa = 21 وc = 13 وm = 100. احسب أول ثلاثة أرقام عشوائية في [0, 1].
3. استخدم اختبار كولموجوروف-سميرنوف عند $\alpha = 0.05$ لفحص انتظام الأرقام 0.44, 0.81, 0.14, 0.05, 0.93.
4. لدينا خمسون رقما مصنفة في 5 فترات متساوية والأعداد المشاهدة فيها 12, 7, 9, 13, 9. استخدم اختبار مربع كاي عند $\alpha = 0.05$.
5. باستخدام الأرقام الـ30 في السؤال 5 اختبر الارتباط الذاتي للأرقام في المواقع 1, 7, 13, ... عند $\alpha = 0.05$.

أهم النقاط

• يحسب المولد الضربي $Z_i = (a Z_{i-1}) \bmod m$. والبذرة والمعامل الضربي والمقياس هي التي تحدد طول الدورة.
• يضيف المولد الخطي المتطابق زيادة: $X_i = (a X_{i-1} + c) \bmod m$. ثم يعطي $R_i = X_i / m$ رقما في [0, 1].
• كولموجوروف-سميرنوف: رتب ثم احسب $D^{+}$ و$D^{-}$ وخذ الأكبر وقارنه بـ$D_{\alpha}$.
• مربع كاي: احسب عدد القيم في كل فترة واجمع $(O_i - E_i)^2 / E_i$ وقارن بالجدول عند n - 1 من درجات الحرية.
• الارتباط الذاتي: أوجد M واحسب $\hat{\rho}$ و$\sigma$ و$Z_0$ ثم قارن $Z_0$ بـ$\pm z_{\alpha/2}$.
• في كل اختبار تعني الإحصاءة الواقعة داخل الحد أننا لا نرفض الفرضية.

الإجابات

التدريب 1

نحسب: $Z_1 = (5 \times 3) \bmod 16 = 15$ و$Z_2 = (5 \times 15) \bmod 16 = 75 \bmod 16 = 11$ و$Z_3 = (5 \times 11) \bmod 16 = 55 \bmod 16 = 7$ و$Z_4 = (5 \times 7) \bmod 16 = 35 \bmod 16 = 3$. وهذه القيمة هي $Z_0$ مرة أخرى. فالدورة هي 3, 15, 11, 7 وطولها 4 = m / 4.

التدريب 2

نحسب: $X_1 = (21 \times 7 + 13) \bmod 100 = 160 \bmod 100 = 60$ و$X_2 = (21 \times 60 + 13) \bmod 100 = 1273 \bmod 100 = 73$ و$X_3 = (21 \times 73 + 13) \bmod 100 = 1546 \bmod 100 = 46$. فالأرقام العشوائية هي 0.60 و0.73 و0.46.

التدريب 3

نجد $D^{+} = 0.26$ و$D^{-} = 0.21$ إذن $D = 0.26$. وبما أن $0.26 < 0.565$ فإننا لا نرفض $H_0$: أي أن الأرقام موزعة توزيعا منتظما.

التدريب 4

لدينا $E_i = 50 / 5 = 10$. وقيم حدود المجموع هي 0.4, 0.9, 0.1, 0.9, 0.1 ولذلك $\chi_0^2 = 2.4$. وعند n - 1 = 4 من درجات الحرية تكون $\chi^2_{0.05, 4} = 9.49$. وبما أن $2.4 < 9.49$ فإننا لا نرفض $H_0$.

التدريب 5

لدينا i = 1 وm = 6 وN = 30: والشرط $1 + (M+1) \times 6 \le 30$ يعطي $M \le 3.83$ إذن M = 3. والأرقام المختبرة هي $R_1, R_7, R_{13}, R_{19}, R_{25}$ = 0.12, 0.64, 0.33, 0.75, 0.95.

$$\hat{\rho}_{16} = \dfrac{1}{4} \left[ (0.12)(0.64) + (0.64)(0.33) + (0.33)(0.75) + (0.75)(0.95) \right] - 0.25 = \dfrac{1.248}{4} - 0.25 = 0.062$$ $$\sigma = \dfrac{\sqrt{13 \times 3 + 7}}{12 \times 4} = \dfrac{\sqrt{46}}{48} = 0.1413, \qquad Z_0 = \dfrac{0.062}{0.1413} = 0.439$$

وبما أن $-1.96 < 0.439 < 1.96$ فإننا لا نرفض $H_0$: أي أن هذه الأرقام تبدو مستقلة.