Chapter 7Exam Weight: HIGH (Midterm 2025 Q1 = 7 pts LCG + Concept Questions; STOP BEFORE K-S Math)Lec 6 Transcript Tail (1:52–2:08)Lec 7 Slides 1–42Lec 7 Transcript (Dr. Ayman)

Random Numbers, Generators & Hypothesis Testing Concepts

توليد الأرقام العشوائية واختبار الفروض (ضمن حدود الميدترم)

True vs. Pseudo-random numbers (Incompressibility & Typicality), Mid-Square pitfalls, Linear Congruential Generators (LCG) & full-period conditions, BBS random-access formula, Hypothesis Testing courtroom logic (Fail to reject H₀), and K-S visual idea ONLY.

الأرقام العشوائية الحقيقية vs الزائفة (Pseudo)، طريقة Mid-Square وعيوبها، الـ LCG وشروط الـ Full Period، معادلة BBS، منطق اختبار الفروض في المحكمة (Fail to reject H₀)، وفكرة الـ K-S نظرياً فقط (قبل الحسابات!).

Chapter Mastery0% (0/3 sections · 0/4 checks)

Scope: Assoc. Prof. Ayman Ghoneim (FCAI — Cairo University)

What you'll lock down in this chapter

Contrast True Random Numbers (physical/hardware) with Pseudo-Random Numbers and explain Incompressibility (Kolmogorov-Chaitin) vs. Typicality (Ville / Martin-Löf).
Generate PRNs via Mid-Square (and recognize 00 absorption / self-loops) and LCG Zᵢ₊₁ = (a·Zᵢ + c) mod m, Rᵢ = Zᵢ/m.
Apply full-period theorems for Mixed LCG (m=2ᵇ) and Multiplicative LCG (m=2ᵇ and prime m), plus BBS Euler random-access.
Explain Hypothesis Testing ('Fail to reject H₀', Type I α vs. Type II β, Power 1-β) and the K-S empirical CDF concept without running out-of-scope K-S/Chi-square/Autocorrelation math.

Section 7.1Concept Core

True vs. Pseudo-Randomness (Incompressibility & Typicality)

العشوائية الحقيقية vs الـ Pseudo-Random

Mark Section Mastered

Core Concept

Why Computers Cannot Generate True Randomness Alone

ليه الكمبيوتر مابيطلعش True Random Numbers لوحده؟

Both '0000...0' and a random 20-bit coin-flip string have probability (1/2)²⁰—so randomness is NOT about low occurrence probability! Theoretical randomness is defined via Incompressibility (Kolmogorov-Chaitin: no short program can generate it) and Typicality (Ville / Martin-Löf: passes all computable tests). Because Martin-Löf sequences are non-computable, computers generate Pseudo-Random Numbers ('false but near enough to the true').

Two essential properties of random numbers: Uniformity on (0, 1) and Independence.
6 desirable PRNG traits: Fast, Portable, Long Cycle/Period, Reproducible via Seed (critical for debugging!), Theoretical support, Multiple independent streams, and Avoid 0 & 1 endpoints.

شرح عربي — كلام الدكتور

احتمال ظهور 20 صفر زي احتمال ظهور 20 رمية عشوائية بالظبط (1/2)²⁰ — فالعشوائية مش احتمال الظهور! العشوائية معناها Incompressibility (ماتعرفش تضغطها في برنامج صغير) و Typicality (تعدي كل الاختبارات). وبما إن المتتالية المثالية غير قابلة للحساب (Non-computable)، الكمبيوتر بيعمل Pseudo-random: زي ما د. أيمن قال 'هو أحمد بس مش الحاج أحمد'!

أهم شرطين للأرقام العشوائية: Uniformity (متوزعة بالتساوي) و Independence (مستقلة عن بعضها).
ميزة كبيرة للـ Pseudo إن ليها Seed يخليك تعيد نفس الأرقام بالظبط عشان تصلّح الـ Bugs (Reproducibility).

Section 7.2Exam #1 Priority

Mid-Square, LCG (Midterm 2025 Q1!) & BBS

خوارزميات التوليد: Mid-Square و LCG و BBS

Mark Section Mastered

Midterm Exam Radar

Midterm 2025 · Q17 ptsView

LCG with c = 4, a = 2, m = 11, Z₀ = 5: generate 10 RNs and find the period.

7 درجات: احسب أول 10 أرقام عشوائية من LCG وهات الـ Period.

Core Concept

Mid-Square Pitfalls & Lehmer's LCG

عيوب Mid-Square ومعادلة الـ LCG

Mid-Square (von Neumann & Metropolis, 1940s) squares a d-digit seed and extracts the middle d digits (pad leading zeros to 2d digits!). Fatal flaw: quickly collapses to 00 or traps in self-loops (e.g., 50²=2500 → 50, 60²=3600 → 60). Linear Congruential Generator (LCG, Lehmer 1949) computes Zᵢ₊₁ = (a·Zᵢ + c) mod m and Rᵢ = Zᵢ / m.

Mixed LCG (c ≠ 0): max possible period = m.
Multiplicative LCG (c = 0): max possible period ≤ m - 1 (since 0 is an absorbing trap!).
Full Period Theorem for m = 2ᵇ (Mixed): period = m iff gcd(c, m) = 1 AND a = 1 + 4k (e.g., Lec 7 Slide 24: a=5, c=3, m=16 gives period 16!).
Multiplicative m = 2ᵇ: max period = m/4 when Z₀ is odd and a = 3 + 8k or 5 + 8k.
Multiplicative prime m: max period = m - 1 if smallest k with m | (aᵏ - 1) is k = m - 1.

شرح عربي — كلام الدكتور

طريقة Mid-Square بتربّع الرقم وتاخد الخانات اللي في النص (وما تنساش تزود أصفار على الشمال لو التربيع أقل من 2d خانة!). عيبها القاتل إنها بتقع في الصفر أو تلف حوالين نفسها (زي 50 أو 60). أما الـ LCG فهي الأشهر: Zᵢ₊₁ = (a·Zᵢ + c) mod m ثم نقسم على m عشان نجيب Rᵢ في [0, 1).

لو c ≠ 0 (Mixed): أقصى دورة (Period) هي m.
لو c = 0 (Multiplicative): أقصى دورة هي m - 1 (الصفر ممنوع وإلا كله يبقى أصفار!).
شرط الدورة الكاملة عند m = 2ᵇ و c ≠ 0: يكون gcd(c, m) = 1 و a = 1 + 4k (يعني باقي قسمة a على 4 يساوي 1).

Blum Blum Shub (BBS) & Other RNGs

خوارزمية BBS الآمنة ومولدات تانية

Quadratic Congruential (Coveyou) uses a second-degree polynomial mod m. Blum Blum Shub (BBS) sets Zᵢ = Zᵢ₋₁² mod m where m = p·q with primes p ≡ q ≡ 3 (mod 4) and gcd(Z₀, m) = 1. Euler's shortcut lets you jump directly to step i: Zᵢ = (Z₀^(2ⁱ mod λ(m))) mod m where λ(m) = lcm(p - 1, q - 1).

Other families in Lec 7: Multiple Recursive (period up to mˡ - 1), Lagged Fibonacci Zᵢ = (Zᵢ₋ᵣ + Zᵢ₋ₛ) mod m, and LFSR (XOR mod 2).

شرح عربي — كلام الدكتور

الـ BBS بيستخدم تربيع الرقم mod m حيث m = p·q وأعداد أولية باقي قسمتها على 4 يساوي 3. وميزته إن بمعادلة أويلر تقدر تنط للرقم رقم i مباشرة من غير ما تحسب اللي قبله: تحسب 2ⁱ mod λ(m) الأول واللي يطلع ترفعله Z₀ وتاخد mod m.

مولدات تانية في السلايدز: Multiple Recursive (تعتمد على آخر l أرقام)، Lagged Fibonacci، و LFSR.

Linear Congruential Generator (LCG)

Formula

معادلة المولد الخطي LCG

LCG Recurrence & Scaling :: Z_{i+1} = (a\,Z_i + c) \bmod m, \qquad R_i = \frac{Z_i}{m}

Double-check whether the prompt asks for R₁ = Z₁/m (starting after first step, as in Midterm 2025 Q1 & Lec 7 Slide 24) vs. including R₀ = Z₀/m!

Blum Blum Shub (BBS) Random-Access Formula

Formula

معادلة النط المباشر في BBS

BBS Direct Access :: Z_i = Z_0^{\,2^i \bmod \lambda(m)} \bmod m, \qquad \lambda(m) = \operatorname{lcm}(p - 1,\; q - 1)

When to use: To compute Zᵢ directly for large i when m = p·q with p ≡ q ≡ 3 (mod 4).

Section 7.3Scope Boundary

Hypothesis Testing & K-S Concept ONLY (Scope Stop Line!)

منطق اختبار الفروض وفكرة الـ K-S نظرياً فقط (نهاية المنهج!)

Mark Section Mastered

Exam Trap

Courtroom Analogy: 'Fail to Reject H₀', Type I (α) vs. Type II (β)

تشبيه المحكمة: المتهم بريء حتى تثبت إدانته (Fail to reject H₀)

Null Hypothesis H₀ (e.g., 'numbers are U(0,1)' or 'defendant is innocent') is assumed true until strong evidence forces rejection in favor of H₁. If evidence isn't strong enough, NEVER say 'Accept H₀'—say 'Fail to reject H₀' (insufficient proof of guilt does not prove innocence!).

Type I Error (α = P(Reject H₀ | H₀ is true)): False positive—convicting an innocent person or falsely rejecting a good RNG.
Type II Error (β = P(Fail to reject H₀ | H₀ is false)): False negative—letting a guilty suspect / bad RNG walk free. Statistical Power = 1 - β.
Dr. Ayman's Airport vs. Carrefour Analogy: Airport security tolerates higher Type I (false alarm) to keep Type II (missing a threat) near 0; Carrefour emails avoid Type I annoyance.

شرح عربي — كلام الدكتور

في المحكمة المتهم بريء (H₀) لحد ما النيابة تجيب أدلة قوية تدينه (Reject H₀). لو الأدلة مش كفاية، القاضي بيقول براءة لعدم كفاية الأدلة — يعني Fail to reject H₀، مابنقولش أبداً Accept H₀!

Type I Error (α): ترفض H₀ وهي صح (تحبس بريء / ترفض مولد كويس) — زي إنذار المطار الكاذب.
Type II Error (β): تفشل في رفض H₀ وهي غلط (تسيب مجرم). والـ Power = 1 - β.

Study Tip

K-S Visual Idea ONLY (Explicit Scope Cutoff!)

فكرة اختبار Kolmogorov-Smirnov نظرياً فقط (قف هنا!)

Lec 7 audio ends right after explaining the visual idea of the Kolmogorov-Smirnov (K-S) test: sort N numbers R₍₁₎ ≤ ... ≤ R₍ₙ₎, compare the empirical staircase i/N against the uniform diagonal F(x) = x, and measure the worst vertical gaps D⁺ and D⁻. DO NOT spend tonight memorizing K-S critical-value tables, Chi-Square bins, Autocorrelation formulas, or Input Modeling—all 4 are OUT OF SCOPE for the midterm.

شرح عربي — كلام الدكتور

تسجيل د. أيمن وقف بالظبط قبل حسابات الـ K-S! الفكرة النظرية بس: بترتب الأرقام وتقارن السُّلم التجريبي i/N بالخط النظري F(x)=x وتقيس أكبر فرق رأسي (D⁺ و D⁻). كل حسابات الـ K-S و Chi-Square و Autocorrelation و Input Modeling بره امتحان الميدترم.

Say This, Not ThatLec 7 Audio

Don't Say / Trap

Because p-value = 0.24 > α = 0.05, we Accept H₀ and prove the RNG is truly uniform.

Say This Instead

Because p-value = 0.24 > 0.05, we Fail to reject H₀ (no sufficient evidence against uniformity).

Statistical tests can falsify H₀ beyond reasonable doubt, never prove H₀ with 100% certainty.

عدم وجود دليل إدانة معناه Fail to reject H₀، عمره ما معناه Accept H₀!

Say This, Not That

Don't Say / Trap

Study Chi-Square, Autocorrelation, K-S critical tables, and Input Modeling for tomorrow's midterm.

Say This Instead

Stop right after Hypothesis Testing + the K-S empirical vs. F(x)=x concept!

Dr. Ayman's Lec 7 stops right before K-S numerical calculations.

محاضرة 7 وقفت قبل حسابات الـ K-S مباشرة — وفر وقتك للي جوه المنهج!

Interactive Simulation LabCh 7

LCG, Mid-Square & BBS Period Lab

مولدات الأرقام العشوائية وفحص الدورة

Ch 7 Interactive Lab: LCG Period, Mid-Square Traps & BBS Checker

Test LCG full-period conditions, inspect [0,1) uniformity, see Mid-Square degeneration traps, and verify Blum-Blum-Shub jumps.

Ch 7

Multiplier (a)

Increment (c)

Modulus (m ≤ 256)

Seed (Z₀)

Cycle Period = 10

Z_i = (a Z_{i-1} + c) \bmod m, \quad U_i = \frac{Z_i}{m}

General modulus m=11: observed cycle length = 10 (cycle starts at step 0).

[0, 1) Uniformity Dot Plot10 points plotted

0.00

0.25

0.50

0.75

1.00

$i$	$Z_{i-1}$	$a Z_{i-1} + c$	$Z_i \bmod m$	$U_i = Z_i / m$	Status
1	5	2×5+4 = 14	3	0.2727	Unique
2	3	2×3+4 = 10	10	0.9091	Unique
3	10	2×10+4 = 24	2	0.1818	Unique
4	2	2×2+4 = 8	8	0.7273	Unique
5	8	2×8+4 = 20	9	0.8182	Unique
6	9	2×9+4 = 22	0	0.0000	Unique
7	0	2×0+4 = 4	4	0.3636	Unique
8	4	2×4+4 = 12	1	0.0909	Unique
9	1	2×1+4 = 6	6	0.5455	Unique
10	6	2×6+4 = 16	5	0.4545	Cycle Closed!

Instant Micro-Checks0/4 passed

Test your grasp before moving on

Wrong answers are automatically logged to your Weak Topics on the Coverage & Progress dashboard until you pass them.

Check 1

For LCG

Z_{i+1} = (5 Z_i + 3) \bmod 16

with

Z_0 = 7

, what are

Z_1

Z_2

, and the cycle period?

في الـ LCG ( $Z_{i+1} = (5 Z_i + 3) \bmod 16$ و $Z_0 = 7$ )، إيه قيم $Z_1$ و $Z_2$ وطول الدورة؟

Check 2

Using 2-digit Mid-Square starting at seed Z₀ = 50, what happens immediately?

لو بدأت طريقة Mid-Square من خانتين بالرقم 50، إيه اللي بيحصل؟

Check 3

Why are Martin-Löf random sequences impossible to generate directly with a computer algorithm?

ليه مانقدرش نكتب برنامج يولّد متتالية Martin-Löf العشوائية المثالية؟

Check 4

In hypothesis testing of an RNG, rejecting H₀ ('numbers are uniform') when the RNG is actually uniform is which type of error?

لو رفضت H₀ (إن المولد كويس ومتجانس) مع إنه في الحقيقة سليم، ده خطأ من النوع الكام؟

30-Second Recap

Read these bullets right before entering the exam hall.

1True RN (physical) vs. Pseudo-RN (algorithmic, fast, reproducible via seed, passes finitely many tests).
2Mid-Square can collapse to 00 or self-loop (50, 60); LCG Zᵢ₊₁ = (aZᵢ + c) mod m, Rᵢ = Zᵢ/m.
3Full period m = 2ᵇ (mixed): gcd(c, m) = 1 and a = 1 + 4k; Multiplicative (c=0) max period ≤ m - 1.
4Courtroom rule: 'Fail to reject H₀', NEVER 'Accept H₀'; K-S calculations, Chi-Square, Autocorrelation & Input Modeling are OUT OF SCOPE.

ملخص ٣٠ ثانية بالعربي:

الـ Pseudo-random سريعة وبتتكرر بنفس الـ Seed وبتعدي اختبارات محدودة.
الـ Mid-Square بتقع في 00 أو Self-loop؛ الـ LCG: Zᵢ₊₁ = (aZᵢ + c) mod m و Rᵢ = Zᵢ/m.
شرط الـ Full period عند m=2ᵇ: gcd(c,m)=1 و a=1+4k.
بنقول Fail to reject H₀ ومش Accept H₀؛ وحسابات K-S و Chi-Square و Autocorrelation و Input Modeling بره الميدترم!

Ready to drill Chapter 7 questions?

10curated concept & written questions for this chapter.

Practice Chapter 7 (10)Browse Questions