--- title: "Congruential methods; rejection method" subject: "Simulation and Modeling" chapter: 6 key: "semester_8/simulation_and_modeling:congruential-methods-rejection" source: https://www.bctengineer.com/q/semester_8/simulation_and_modeling/congruential-methods-rejection site: BCT Engineering --- # Congruential methods; rejection method Simulation and Modeling · Chapter 6: Random Number - Asked in: 2074 Magh, 5+3 marks - Video: [Combined linear congruential method - Ashny](https://www.youtube.com/watch?v=-YOtvrP-lfM) — Shailesh Shetty - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_8/simulation_and_modeling/congruential-methods-rejection - Whole chapter: https://www.bctengineer.com/md/semester_8/simulation_and_modeling/chapter-6 ## Question Explain the different congruential random number generation methods with example. Explain rejection method. ## Short answer Congruential methods include mixed LCG X(n+1)=(aX(n)+c) mod m, multiplicative c=0, and additive, producing R=X/m. The rejection method accepts a candidate x only if a second uniform value y satisfies y <= f(x), giving the desired distribution with efficiency equal to acceptance fraction. ## Answer #### Congruential methods Congruential generators produce integers X1, X2, ... by modular arithmetic, and the random numbers are R = X/m. **1. Mixed (linear) congruential method** X(n+1) = (a X(n) + c) mod m, with seed X0, multiplier a, increment c and modulus m. Parameters must give a long period; the maximum period is m. Example: a = 5, c = 3, m = 16, X0 = 7: X1 = (5 x 7 + 3) mod 16 = 38 mod 16 = 6, so R1 = 6/16 = 0.375 X2 = (5 x 6 + 3) mod 16 = 33 mod 16 = 1, so R2 = 0.0625 X3 = (5 x 1 + 3) mod 16 = 8, so R3 = 0.5 X4 = 11, X5 = 10, X6 = 5 ... and it returns to 7 after 16 steps (full period). **2. Multiplicative congruential method** (c = 0) X(n+1) = a X(n) mod m. It is faster, but the maximum period is smaller (for m = 2^b, at most m/4, and the seed must be odd). Example: a = 13, m = 64, X0 = 1 gives 13, 41, 21, 17, 29, 57, 37, 33 (R = 0.203, 0.641 ...). **3. Additive congruential method** X(n) = (X(n-1) + X(n-k)) mod m, using earlier values of the sequence. Example with k = 2, m = 100, seeds 65 and 89: 54, 43, 97, 40, 37, 77. #### Rejection (acceptance-rejection) method Rejection method generates random variates from a distribution by generating candidates and discarding those that do not satisfy a condition. The values that survive follow the wanted distribution. **Steps** for a density f(x) on [a, b] with maximum value M: 1. Generate R1 uniform on (0, 1) and set x = a + (b - a) R1. 2. Generate R2 uniform on (0, 1) and set y = M R2. 3. If y <= f(x), accept x as the variate; otherwise reject it and go to step 1. Example: f(x) = 2x on [0, 1], M = 2. If R1 = 0.6, R2 = 0.5: x = 0.6, y = 1.0, f(x) = 1.2, y <= f(x) so accept 0.6. If R1 = 0.2, R2 = 0.9: x = 0.2, y = 1.8, f(x) = 0.4, so reject. On average half of the pairs are accepted here. A simpler example: to get uniform values on (1/4, 1) from U(0, 1), generate R and reject it if R < 1/4. The rejection method is also used to generate Poisson variates (multiply uniform random numbers until the product is below e^(-lambda)). Its efficiency is the fraction of accepted candidates. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. For m = 2^b, what is a limitation of the multiplicative congruential method compared with the mixed method? A. Its maximum period is smaller (at most m/4) and the seed must be odd B. It cannot be programmed on a computer C. It needs two seeds D. It produces negative numbers Answer: A. The multiplicative method is faster but its maximum period is at most m/4 for m = 2^b, and the seed must be odd. (Key point: Multiplicative limits) 2. In the rejection method for density f(x) with maximum M, when is the candidate x accepted? A. If y > f(x) B. If y <= f(x), where y = M R2 C. If R1 < 0.5 D. If x = M Answer: B. A candidate x is accepted when the height y = M R2 falls under the curve, y <= f(x). (Key point: Rejection step) 3. For f(x) = 2x on [0,1] with M = 2, R1 = 0.2, R2 = 0.9, what happens? A. Accept, since x = 0.2 B. Accept, since y = 1.8 > f(x) C. Reject, since y = 1.8 > f(x) = 0.4 D. Reject, since M is too small Answer: C. y = 2 x 0.9 = 1.8 exceeds f(0.2) = 0.4, so the pair is rejected and new numbers are generated. (Key point: Rejection example) 4. Which formula defines the additive congruential method? A. X(n) = a X(n-1) mod m B. X(n) = (X(n-1) + X(n-k)) mod m C. X(n) = X(n-1)^2 D. X(n) = (a X(n-1) + c) mod m Answer: B. It adds earlier values of the sequence: X(n) = (X(n-1) + X(n-k)) mod m. (Key point: Additive congruential) ## Related in Simulation and Modeling - [Random number generation methods](https://www.bctengineer.com/question.md?key=semester_8%2Fsimulation_and_modeling%3Arn-generation-methods) — Simulation and Modeling, chapter 6 - [Random number; problems in generating pseudo-random](https://www.bctengineer.com/question.md?key=semester_8%2Fsimulation_and_modeling%3Arn-problems-pseudo-random) — Simulation and Modeling, chapter 6 - [Short note: Convolution in random number](https://www.bctengineer.com/question.md?key=semester_8%2Fsimulation_and_modeling%3Aconvolution-short-note) — Simulation and Modeling, chapter 6 - [Random number properties and Gap test](https://www.bctengineer.com/question.md?key=semester_8%2Fsimulation_and_modeling%3Arn-properties-gap-test) — Simulation and Modeling, chapter 6, asked 4× - [Random number properties; KS test algorithm](https://www.bctengineer.com/question.md?key=semester_8%2Fsimulation_and_modeling%3Arn-properties-ks-algorithm) — Simulation and Modeling, chapter 6 - [Properties and generation techniques of RN](https://www.bctengineer.com/question.md?key=semester_8%2Fsimulation_and_modeling%3Arn-properties-generation-techniques) — Simulation and Modeling, chapter 6