23-Ind-A6 Systems Simulation · May 2018

Question 3 of 9: Acceptance–Rejection and LCG Period

Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)

Notes on this paper

National Exams — May 2018 — 17-Ind-A6 Systems Simulation. Three-hour, closed-book exam; one of two permitted calculators (Sharp or Casio), one 8.5″×11.0″ aid sheet (both sides). Format: three sections — Section A (four concept questions, candidates choose any two, 10 marks each, 20 marks total), Section B (three methods questions built around one continuing warehouse-simulation case study, candidates choose any two, 15 marks each, 30 marks total), Section C (two applications questions, candidates choose any one, 20 marks each). All nine questions are solved below for completeness. Two source anomalies are flagged where they occur: the front-page summary table states Section A is "Do 2 of 3," while Section A's own instructions and its four printed question sets read "two of the following four" — the printed four-question section is answered in full here; and Part C Question 2's sub-parts (a)–(c) are never printed anywhere in the paper, even though the results text for (d)–(f) explicitly refers back to "the factorial design matrix in (a)." Two-page Normal-distribution tables were supplied with the exam; the values below are the same table values obtained by direct computation.

Reference texts: Banks, Carson, Nelson & Nicol, Discrete-Event System Simulation (5th ed., Pearson) — random-number/random-variate generation, input modeling and goodness-of-fit testing, output analysis (warm-up, replication length, batch means vs. replication/deletion), and comparing alternative systems; Montgomery, Design and Analysis of Experiments (current ed., Wiley) — single-factor ANOVA, multiple comparisons, and 2^k factorial designs with interaction analysis (Part C).

Question 3 (Part A.3): Acceptance–Rejection and LCG Period (10 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. $q(x)=3x^2/2$ on $-1\le x\le1$; majorizing function $g(x)=3/2$; linear congruential generator (LCG) $a=21,\ m=100,\ c=13,\ X_0=7$.

Find. (a) an acceptance–rejection (A-R) algorithm; (b) two accepted variates from the LCG stream; (c) a comment on the LCG's period.

Approach. Build the standard A-R test using $g$ as the constant envelope; iterate the LCG and apply the test in non-overlapping $(U_1,U_2)$ pairs until two acceptances occur; check the LCG against the Hull–Dobell full-period conditions.

(a) Set up the algorithm. $g(x)=3/2$ bounds $q(x)$ everywhere on $[-1,1]$ (its maximum, at $x=\pm1$, is $3/2$), so:
Step 1: generate $U_1\sim U(0,1)$ and form the candidate $Y=-1+2U_1$ (uniform on $[-1,1]$).
Step 2: generate $U_2\sim U(0,1)$.
Step 3: accept $X=Y$ if $U_2 \le q(Y)/g(Y)=Y^2$; otherwise reject and return to Step 1.

(b) Run the LCG and test candidates. Iterating $X_{i+1}=(21X_i+13)\bmod100$ from $X_0=7$ and testing non-overlapping pairs $(U_1,U_2)$ against $U_2\le Y^2$:

Acceptance–rejection trial log
Trial	$U_1$	$U_2$	$Y=-1+2U_1$	$Y^2$	Accept?
1	0.60	0.73	0.20	0.0400	reject
2	0.46	0.79	−0.08	0.0064	reject
3	0.72	0.25	0.44	0.1936	reject
4	0.38	0.11	−0.24	0.0576	reject
5	0.44	0.37	−0.12	0.0144	reject
6	0.90	0.03	0.80	0.6400	accept
7	0.76	0.09	0.52	0.2704	accept

Five candidates are rejected before the sixth and seventh trials succeed — consistent with the algorithm's average acceptance rate of $1/c=2/3$ per candidate^† being pulled down here by an unlucky early run. $$\boxed{X_1=0.80,\qquad X_2=0.52}$$

(c) Comment on the period. Apply the Hull–Dobell theorem to $a=21,\ m=100,\ c=13$: (i) $\gcd(c,m)=\gcd(13,100)=1$ ✓; (ii) $a\equiv1$ modulo every prime factor of $m$: $21\equiv1\ (\mathrm{mod}\ 2)$ and $21\equiv1\ (\mathrm{mod}\ 5)$ ✓; (iii) since $4\mid m$, also need $a\equiv1\ (\mathrm{mod}\ 4)$: $21=5(4)+1$ ✓. All three conditions hold, so this LCG achieves the full period $m=100$ — a substantially better design than the pure-multiplicative generators of Questions 1 and 2 (periods $20$ and $10$ respectively), because the additive constant $c$ removes the multiplicative-subgroup restriction that caps a pure MCG's period below $m$ whenever $m$ is composite.

† the constant-envelope area ratio here is $c=g(x)\big/\big(\text{uniform density }1/2\big)=3$, so the expected number of candidates per acceptance is $3$, i.e. an average acceptance probability of $1/3$ — two acceptances in seven trials is well within normal sampling variation of that rate.

Item	Result
(a) algorithm	candidate $Y=-1+2U_1$; accept if $U_2\le Y^2$
(b) two accepted variates	$X_1=0.80$, $X_2=0.52$ (after 5 rejections)
(c) LCG period	Hull–Dobell fully satisfied — full period $=100$

Concept & Theory

Topic. Acceptance–rejection variate generation and the Hull–Dobell full-period theorem.

Key relations. Accept iff $U_2\le q(Y)/g(Y)$; Hull–Dobell conditions for $X_{n+1}=(aX_n+c)\bmod m$ to have full period $m$.

Why this works. A-R only needs pointwise evaluation of the target density (no closed-form CDF required), trading a random number of draws per variate (rate $1/c$) for that generality; a full-period LCG guarantees every residue $0,\dots,m-1$ appears exactly once per cycle — the strongest guarantee available from a first-order linear recursion.

Common pitfall. Testing a fresh, unpaired $U_2$ instead of the $U_2$ drawn immediately after the candidate's own $U_1$; or, for Hull–Dobell, checking only $\gcd(c,m)=1$ and skipping the mod-4 condition when $m$ is divisible by 4.

Source. Banks, Carson, Nelson & Nicol, Discrete-Event System Simulation, ch. 5 (LCGs, Hull–Dobell theorem) & ch. 8 (acceptance–rejection technique).

← Question 2 Next: Question 4 →