23-Ind-A6 Systems Simulation · December 2013

Question 13 of 14: Question 13 (Part D, Set 3 — Acceptance-Rejection Variate Generation)

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

Notes on this paper

National Exams — December 2013 — 98-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: 14 sub-questions across four parts — Part A (do 1 of 2, 25 marks), Part B (do 3 of 5, 15 marks), Part C (do 1 of 3, 10 marks), Part D (do 2 of 4, 20 marks); 7 questions, 70 marks constitute a complete paper. All fourteen sub-questions are solved below for completeness (the source restarts its own numbering at 1 within each Part). Statistical tables (Normal, t, chi-square, F) 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) — simulation study design, random-number generation, input/output data analysis, variance reduction, verification & validation, queueing simulation; Montgomery, Design and Analysis of Experiments (9th ed., Wiley) — factorial designs and ANOVA.

Question 13 (Part D, Set 3 — Acceptance-Rejection Variate Generation) (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. Piecewise density $f(x)$ on $[0,2]$ with maximum value $3/2$ (at $x=1$); majorizing (envelope) function $t(x)=3/2$, constant over $[0,2]$; supplied random numbers (used as pairs, in order): 0.10, 0.65, 0.51, 0.08, 0.77.

Find. The acceptance-rejection procedure, and the first accepted variate from the given random numbers.

Approach. Since $t(x)$ is constant over $[0,2]$, a candidate $x$ is generated uniformly on $[0,2]$ from one random number; a second random number is compared against $f(x)/t(x)$ to accept or reject the candidate; repeat until accepted.

Procedure. Given two fresh $U(0,1)$ draws $(u_1,u_2)$: form the candidate $x=2u_1$ (uniform on the support $[0,2]$); accept $x$ if $u_2\le f(x)/t(x)$, otherwise discard the pair and draw again.
Trial 1 ($u_1=0.10,\ u_2=0.65$). $$x = 2(0.10)=0.20\ \ (\text{in } 0\le x<1),\qquad f(0.20)=1.5(0.20)^2=0.060,\qquad \frac{f(x)}{t(x)}=\frac{0.060}{1.5}=0.040.$$ Since $u_2=0.65 > 0.040$, reject.
Trial 2 ($u_1=0.51,\ u_2=0.08$). $$x = 2(0.51)=1.02\ \ (\text{in } 1\le x\le2),\qquad f(1.02)=1.5(1.02-2)^2=1.4406,\qquad \frac{f(x)}{t(x)}=\frac{1.4406}{1.5}=0.9604.$$ Since $u_2=0.08 \le 0.9604$, accept: $\boxed{x=1.02}$ is the first generated lead-time variate.

Acceptance-rejection: a candidate point $(x, u_2\cdot t(x))$ that falls ABOVE the $f(x)$ curve is rejected (trial 1); one that falls below is accepted (trial 2), yielding the variate $x=1.02$.

Quantity	Result
Trial 1 candidate / decision	$x=0.20$, rejected ($u_2=0.65 > 0.040$)
Trial 2 candidate / decision	$x=1.02$, accepted ($u_2=0.08 \le 0.9604$)
First generated lead-time variate	1.02

Concept & Theory

Topic. Acceptance-rejection random variate generation.

Key relations. Candidate $x=$ (uniform draw scaled to the support); accept if $u_2\le f(x)/t(x)$; expected acceptance rate $=\dfrac{\int f}{\int t}=\dfrac{1}{1.5\times2}=\dfrac13$ here, so an average of 3 trials per accepted variate is expected.

Why this works. Sampling a point uniformly under the majorizing rectangle and keeping only points that also fall under $f(x)$ produces points distributed exactly as $f(x)$ over the region where $f$ and $t$ overlap — the two-step "generate candidate, then accept/reject" is just a geometric restatement of that fact, and any valid $t(x)\ge f(x)$ over the support works, though a tighter envelope raises the acceptance rate.

Common pitfall. Forgetting the candidate $x$ must be generated over the FULL support that $t(x)$ covers ($[0,2]$ here, uniformly, since $t$ is constant) rather than only where $f(x)$ happens to be large; and comparing $u_2$ against $f(x)$ directly instead of the ratio $f(x)/t(x)$ (only valid when $t\equiv1$ over the support, which is not the case here).

Source. Banks, Carson, Nelson & Nicol, Discrete-Event System Simulation, ch. 8 (random variate generation, acceptance-rejection).

← Question 12 Next: Question 14 →