BE Computer Engineering (Pokhara University) Simulation and Modeling (PU, CMP 338) Question Paper 2079 Nepal

(a) System, system environment and system entities (6)

System: A system is a group of objects that are joined together in some regular interaction or interdependence toward the accomplishment of some purpose. Example: a bank serving customers, or a manufacturing shop producing parts.

System entities: The objects of interest inside the system whose behaviour we study. They have attributes (properties) and take part in activities.

System environment: Everything outside the system boundary that influences the system but is not controlled by it. Changes in the environment affect the system but the system does not (significantly) affect them. The line that separates the two is the system boundary.

Example — a bank:

In a manufacturing shop, entities are machines and jobs; the environment is the demand/order stream and raw-material supply that drive the system but are external to it.

(b) Classification of models (8)

Class of a discrete-event simulation (DES): A DES model is dynamic, stochastic and discrete — the state variables change only at a discrete (countable) set of points in time (the event times), the model evolves over time, and arrivals/service times are typically random.

Marking scheme: (a) definition of system 2, environment vs. entities 2, worked example 2; (b) ~1 mark per correctly explained pair with example (4×1.5 ≈ 6) + 2 for stating DES is dynamic/stochastic/discrete.

(a) Hand-simulation table (8)

Arrival time = cumulative inter-arrival times (customer 1 arrives at t=0). Service begin = max(own arrival time, previous customer's service-end). Waiting time = service begin − arrival time. Service end = service begin + service time. Time in system = service end − arrival time.

Arrival times: 0, 3, 5, 10, 11, 15, 17, 23.

Totals: total waiting time in queue = $0+1+1+1+1+0+0+0 = 4$ min; total service time = $4+2+5+1+3+2+4+2 = 23$ min; total time in system = $4+3+6+2+4+2+4+2 = 27$ min.

(b) Performance measures (6)

Average waiting time per customer $= \dfrac{4}{8} = 0.5$ min.

Probability a customer has to wait $= \dfrac{\text{customers who waited}}{8} = \dfrac{4}{8} = 0.5$ (customers 2,3,4,5 waited).

Average service time $= \dfrac{23}{8} = 2.875$ min.

Server utilization $= \dfrac{\text{total service (busy) time}}{\text{total simulation time}} = \dfrac{23}{25} = 0.92$ (server finishes the last customer at t=25; it was busy 23 of those 25 minutes — note the only idle gap is between t=21 and t=23).

Average time a customer spends in the system $= \dfrac{27}{8} = 3.375$ min (supporting figure).

Marking scheme: correct arrival/begin/end columns 4, wait & system columns 4; each of the four part-(b) statistics 1.5 each.

(a) Linear congruential method (LCG) and Hull–Dobell conditions (6)

The linear congruential generator produces a sequence of integers $X_0, X_1, X_2,\dots$ in $\{0,1,\dots,m-1\}$ by the recurrence

$$X_{i+1} = (a X_i + c)\bmod m, \qquad i = 0,1,2,\dots$$

where $m$ is the modulus ($m>0$), $a$ the multiplier ($0<a<m$), $c$ the increment ($0\le c<m$) and $X_0$ the seed. Uniform $(0,1)$ numbers are obtained by $R_i = X_i/m$.

If $c\neq 0$ it is a mixed congruential generator; if $c=0$ it is multiplicative.

Hull–Dobell theorem (full period $m$ for a mixed LCG): A mixed congruential generator has the maximum possible period $m$ for every seed if and only if

1. $c$ and $m$ are relatively prime, i.e. $\gcd(c,m)=1$;
2. $a-1$ is divisible by every prime factor of $m$;
3. $a-1$ is divisible by 4 if $m$ is divisible by 4.

(b) Multiplicative generator $X_{i+1}=(5X_i)\bmod 16$, seed $X_0=3$ (6)

First six generated integers: 15, 11, 7, 3, 15, 11 with uniforms 0.9375, 0.6875, 0.4375, 0.1875, 0.9375, 0.6875.

Comment on the period: The sequence repeats after the values $15,11,7,3$ — i.e. the period is 4, not the maximum. For a multiplicative generator with $m=2^k$ ($m=16$ here), the maximum achievable period is only $m/4 = 4$, and it is reached only when $a \equiv 3$ or $5 \pmod 8$ and the seed is odd. Because $m=16$ is a power of two, a full period of 16 is impossible for a multiplicative ($c=0$) generator (the Hull–Dobell full-period conditions require $c\neq0$); even numbers can never appear once an odd seed is used, so at most odd residues are visited and the period is short.

Marking scheme: (a) recurrence + parameter meaning 3, three Hull–Dobell conditions 3; (b) correct six values 4, correct comment on period 2.

(a) Inverse-transform technique — statement and proof (5)

Statement: Let $X$ be a continuous random variable with cumulative distribution function $F(x)$ that is continuous and strictly increasing. Let $R\sim U(0,1)$. Then the variate

$$X = F^{-1}(R)$$

has the distribution function $F$.

Proof: Since $F$ is continuous and strictly increasing it has an inverse $F^{-1}$. Consider the CDF of $X=F^{-1}(R)$:

$$P(X\le x) = P\big(F^{-1}(R)\le x\big) = P\big(R \le F(x)\big),$$

where we applied $F$ (an increasing function) to both sides. Because $R$ is uniform on $(0,1)$, $P(R\le u)=u$ for $0\le u\le 1$, and $0\le F(x)\le 1$. Hence

$$P(X\le x) = F(x).$$

Thus $X=F^{-1}(R)$ has exactly the desired distribution $F$. $\blacksquare$

Algorithm: (1) generate $R\sim U(0,1)$; (2) set $X=F^{-1}(R)$.

(b) Exponential variate by inverse transform (5)

The exponential CDF with rate $\lambda$ is

$$F(x) = 1 - e^{-\lambda x}, \quad x\ge 0.$$

Set $R = F(x) = 1-e^{-\lambda x}$ and solve for $x$:

$$e^{-\lambda x} = 1-R \;\Rightarrow\; -\lambda x = \ln(1-R) \;\Rightarrow\; x = -\frac{1}{\lambda}\ln(1-R).$$

Since $1-R$ is also $U(0,1)$, this is equivalently written $x = -\frac{1}{\lambda}\ln R$.

Numerical evaluation with $\lambda = 0.5$ and $R = 0.35$ (using the standard form $x=-\frac1\lambda\ln(1-R)$):

$$x = -\frac{1}{0.5}\ln(1-0.35) = -2\ln(0.65) = -2(-0.4308) = 0.8616.$$

So the generated exponential variate is approximately $x \approx 0.86$ (time units).

Marking scheme: (a) statement 1, correct proof using $P(R\le u)=u$ 4; (b) derivation of $x=-\tfrac1\lambda\ln(1-R)$ 3, correct numeric answer 2.

Steps in a sound simulation study (7)

The accepted sequence (Banks, Carson, Nelson & Nicol) is:

1. Problem formulation — clearly state the problem.
2. Setting of objectives and overall project plan — questions to answer, resources, time.
3. Model conceptualization — abstract the system into a model.
4. Data collection — gather input data (often concurrent with step 3).
5. Model translation — code the model in a simulation language/package.
6. Verified? — verification: is the program a correct implementation of the conceptual model? If no, return to model translation.
7. Validated? — validation: does the model accurately represent the real system? Often compared against a real system; if no, return to model conceptualization / data collection.
8. Experimental design — decide replications, run length, scenarios.
9. Production runs and analysis — run the model, analyse output.
10. More runs? — if yes, go back to step 8.
11. Documentation and reporting — record assumptions, program, and results.
12. Implementation — put the results into practice.

Flow diagram (described in words): boxes flow top-to-bottom 1→2→3 and 4 (3 and 4 side-by-side) →5→ Verified? (decision) → Validated? (decision) →8→9→ More runs? (decision) →11→12. The two decision diamonds loop back: "Verified? No" loops to model translation; "Validated? No" loops to model conceptualization; "More runs? Yes" loops to experimental design.

Where V&V occur: Verification is carried out right after model translation (step 6) to confirm the code matches the conceptual model; Validation is carried out at step 7, calibrating the model against the real system before production runs.

Marking scheme: correct ordered list of steps 4, flow-diagram/loops shown 2, correctly identifying the V&V step 1.

Monte Carlo method (7)

The Monte Carlo method is a technique that uses repeated random sampling to obtain numerical estimates of quantities that may be deterministic (e.g. an integral, an area, or $\pi$) but are hard to compute analytically. By generating many random samples and averaging an appropriate outcome, the law of large numbers makes the estimate converge to the true value. It is typically a static, stochastic simulation (no time axis).

Estimating $\pi$

Consider a quarter circle of radius 1 inscribed in the unit square $[0,1]\times[0,1]$. The square has area 1; the quarter circle has area $\pi/4$. So the probability that a uniformly random point in the square falls inside the circle is $\pi/4$.

Procedure:

count = 0
for i = 1 to N:
    x = U(0,1)            # random x
    y = U(0,1)            # random y
    if x*x + y*y <= 1:    # inside quarter circle
        count = count + 1
pi_estimate = 4 * count / N

The fraction of points inside, $count/N$, estimates $\pi/4$, hence $\hat\pi = 4\,count/N$.

Accuracy vs. number of samples

The estimate is the mean of $N$ Bernoulli trials, so its standard error decreases as

$$\text{error} \propto \frac{1}{\sqrt{N}}.$$

To halve the error you must quadruple $N$. Thus Monte Carlo converges slowly ($O(1/\sqrt N)$), but the rate is independent of dimension, which is its great advantage for high-dimensional problems.

Marking scheme: definition of Monte Carlo 2, $\pi$ procedure/code with ratio $\pi/4$ 3, accuracy $\propto 1/\sqrt N$ 2.

M/M/1 queue, $\lambda=8$/hr, $\mu=10$/hr (6)

(a) Server utilization

$$\rho = \frac{\lambda}{\mu} = \frac{8}{10} = 0.8.$$

The server is busy 80% of the time.

(b) Expected number in system

$$L = \frac{\rho}{1-\rho} = \frac{0.8}{1-0.8} = \frac{0.8}{0.2} = 4 \text{ customers}.$$

(c) Expected waiting time in queue

Using $L_q = \dfrac{\rho^2}{1-\rho} = \dfrac{0.64}{0.2} = 3.2$ customers and Little's law $W_q = L_q/\lambda$:

$$W_q = \frac{L_q}{\lambda} = \frac{3.2}{8} = 0.4 \text{ hour} = 24 \text{ minutes}.$$

Equivalently $W_q = \dfrac{\rho}{\mu-\lambda} = \dfrac{0.8}{10-8} = 0.4$ hr.

Marking scheme: (a) $\rho=0.8$ 2, (b) $L=4$ 2, (c) $W_q=0.4$ hr (24 min) 2.

Verification vs. Validation (6)

In short, verification checks the model is implemented correctly, while validation checks the right model has been built (it behaves like the real system).

Four techniques to increase validity and credibility (any four)

1. Use high face validity — build a model that, on the surface, looks reasonable to people knowledgeable about the system (involve subject-matter experts).
2. Validate model assumptions — test structural and data assumptions statistically against real data.
3. Compare model output with real-system data — run the model under the same conditions as the real system and statistically compare results (e.g. confidence-interval or t-test on key measures).
4. Sensitivity analysis — vary input parameters to see whether the model responds in the same direction/magnitude as the real system.

(Other acceptable answers: animation/trace, historical-data validation, Turing test with experts, degenerate/extreme-condition tests.)

Marking scheme: clear V vs. V distinction 2 (1 each), any four valid techniques 4 (1 each).

Why random numbers must be tested (6)

Numbers from a generator are pseudo-random — produced by a deterministic algorithm. Before use they must be tested to confirm they are:

• Uniformly distributed on $(0,1)$, and
• Independent (no autocorrelation/pattern).

If they fail these properties the simulation results are biased or invalid, so statistical tests for uniformity (frequency/$\chi^2$, Kolmogorov–Smirnov) and independence (runs, autocorrelation) are applied.

Kolmogorov–Smirnov (K–S) test for uniformity

The K–S test compares the empirical CDF of the $N$ generated numbers with the theoretical uniform CDF $F(x)=x$ on $(0,1)$.

Procedure:

1. Arrange the $N$ numbers in ascending order: $R_{(1)} \le R_{(2)} \le \dots \le R_{(N)}$.
2. Compute the largest deviations above and below the theoretical CDF:

$$D^{+} = \max_{1\le i\le N}\left(\frac{i}{N} - R_{(i)}\right), \qquad D^{-} = \max_{1\le i\le N}\left(R_{(i)} - \frac{i-1}{N}\right).$$

3. The test statistic is

$$D = \max(D^{+}, D^{-}).$$

Decision rule: Look up the critical value $D_{\alpha}$ from the K–S table for the chosen significance level $\alpha$ and sample size $N$.

• If $D \le D_{\alpha}$: do not reject $H_0$ — the numbers are consistent with a uniform distribution.
• If $D > D_{\alpha}$: reject $H_0$ — the hypothesis of uniformity is rejected.

Marking scheme: reasons for testing (uniformity & independence) 2, K–S statistic $D=\max(D^+,D^-)$ with formulae 2, comparison rule $D$ vs $D_\alpha$ 2.

Terminating vs. steady-state simulation (6)

Why replication–deletion and a warm-up period are needed

In a steady-state study the output at the start of a run is influenced by the (usually empty/idle) initial conditions, producing initialization bias — early observations are not representative of steady state.

• Warm-up period (deletion): discard the data collected during the initial transient period $[0, l]$ (e.g. using Welch's procedure), so statistics are gathered only after the system has reached steady state. This removes initialization bias.
• Replication–deletion approach: make $n$ independent replications (different random-number streams), in each replication delete the warm-up data, compute the steady-state average of the remaining data, and then use these $n$ replication averages as i.i.d. observations to form a point estimate and a confidence interval for the steady-state measure.

Together they give an unbiased steady-state estimate with a valid confidence interval, which a single long run cannot easily provide.

Marking scheme: correct distinction with one example each 3, role of warm-up (initialization bias) 1.5, replication–deletion for CI 1.5.

Discrete-event simulation terms (6)

(a) Event: An instantaneous occurrence that may change the state of the system. Examples: an arrival, the completion of a service.

(b) Event notice: A record (data structure) stating that a particular event is to occur at a given future time, e.g. (event type, event time, associated entity). It is the entry placed on the FEL.

(c) Future Event List (FEL): A list of all event notices for events scheduled to occur in the future, ordered by event time (earliest first). The simulation always removes the most imminent event from the head of this list.

(d) System state: The collection of state variables that completely describe the system at any time (e.g. number of customers in queue, server status busy/idle).

(e) Activity: A duration of time of known length (specified when it begins), such as a service time or an inter-arrival time. It corresponds to the interval between two related events.

How the simulation clock advances (event-scheduling / next-event approach)

The clock uses next-event time advance: rather than ticking in fixed steps, the simulation jumps directly to the time of the next (most imminent) event on the FEL.

While FEL not empty:
    1. Remove the imminent event notice (smallest event time) from the FEL.
    2. Advance the simulation clock to that event time.
    3. Execute the event routine: update system state and statistics.
    4. Possibly schedule new future events (insert notices into the FEL).

Thus the clock advances unevenly, skipping over periods of inactivity in which no state change occurs.

Marking scheme: five definitions 1 mark each (5), clock advance via next-event mechanism 1.

95% confidence interval for mean delay (6)

Data (n = 5): 4.2, 5.1, 3.8, 4.6, 4.9 minutes.

Sample mean:

$$\bar{X} = \frac{4.2+5.1+3.8+4.6+4.9}{5} = \frac{22.6}{5} = 4.52 \text{ min}.$$

Deviations and squared deviations:

Sample variance and standard deviation:

$$S^2 = \frac{\sum (X_i-\bar X)^2}{n-1} = \frac{1.1080}{4} = 0.2770, \qquad S = \sqrt{0.2770} = 0.5263.$$

Standard error:

$$\frac{S}{\sqrt{n}} = \frac{0.5263}{\sqrt 5} = \frac{0.5263}{2.2361} = 0.2354.$$

Half-width (with $t_{0.025,4}=2.776$):

$$h = t_{0.025,4}\cdot\frac{S}{\sqrt n} = 2.776 \times 0.2354 = 0.6535.$$

95% confidence interval:

$$\bar X \pm h = 4.52 \pm 0.65 = (3.87,\; 5.17) \text{ minutes}.$$

We are 95% confident the true mean customer delay lies between about 3.87 and 5.17 minutes.

Marking scheme: mean 1, variance/SD 2, standard error 1, half-width using t 1, final interval 1.