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

(a) System and its components (7)

A system is a collection of entities (people, machines, objects) that act and interact together toward the accomplishment of some logical end. The behaviour of a system is characterised by the following terms (illustrated with a bank teller service):

Distinction: an activity spans an interval of time and ends with an event (an instant), whereas an event changes the state. Entities possess attributes.

(b) Classification of models (5)

• (i) Static vs. Dynamic: A static model represents a system at a particular point in time (no time axis), e.g. Monte Carlo. A dynamic model represents the system as it evolves over time.
• (ii) Deterministic vs. Stochastic: A deterministic model has no random inputs (output fixed once inputs are known); a stochastic model contains one or more random inputs, so outputs are themselves random.
• (iii) Continuous vs. Discrete: In a continuous model state variables change continuously with time (differential equations); in a discrete model state changes only at discrete (countable) points in time.

Placement:

• A Monte Carlo model is static, stochastic (and typically discrete in the sense of not modelling time evolution).
• A discrete-event simulation model is dynamic, stochastic, discrete.

(c) When to use / not use simulation (3)

Appropriate (any three):

1. When the system is too complex for an analytical (closed-form) solution.
2. To study a proposed system before building it / to compare design alternatives.
3. To verify analytic results, or to study a system over a long time frame in compressed time ("what-if" experimentation).

Should NOT be used (any two):

1. When the problem can be solved exactly by simple analytical methods (e.g. a known queuing formula).
2. When the cost/time of building the model exceeds the benefit, or when there is no time/resources/valid data to model and validate it.

(a) Simulation table (8)

Arrival clock = running sum of inter-arrival times. Customer 1 starts at clock 0. Service begins at max(arrival, previous service-end). Idle time = arrival of a customer − service-end of previous customer (when positive).

Totals: total waiting in queue = 0+0+0+2+2+0+3+2+5+5 = 19 min; total service time = 2+1+3+2+1+4+2+5+1+3 = 24 min; total idle = 3+3 = 6 min; simulation ends at clock = 30 min.

(b) Performance measures (5)

• Average waiting time per customer = 19 / 10 = 1.9 min.
• Probability a customer waits = (number who waited) / 10 = 5/10 = 0.5.
• Average service time = 24 / 10 = 2.4 min.
• Server utilization = total busy time / total run time = 24 / 30 = 0.8 (80%). (Server idle 6 of 30 min.)

(c) Time-advance mechanisms (3)

Event-scheduling / next-event time-advance: the simulation clock is initialised to 0 and the times of future events are kept in an event (future-event) list. The clock then jumps directly to the time of the most imminent (smallest-time) event; that event is processed, the state and statistical counters are updated, new future events are scheduled, and the clock advances again to the next imminent event. Periods of inactivity are skipped.

Fixed-increment time-advance: the clock is advanced in equal steps Δt, and at the end of each step all events scheduled to have occurred in that interval are processed (treated as if they happened at the interval end).

Contrast: next-event advance moves only to instants where the state actually changes (efficient, exact event timing), whereas fixed-increment advance steps even through empty intervals and introduces round-off of event times; the latter is mainly suited to continuous/synchronous systems.

(a) Linear congruential generator (6)

Recurrence: $X_{i+1} = (aX_i + c)\bmod m$ with $a=17,\ c=43,\ m=100,\ X_0=27$, and $U_i = X_i/m$.

• $X_1 = (17\cdot 27 + 43)\bmod 100 = (459+43)\bmod100 = 502\bmod100 = \mathbf{2}$, $U_1=0.02$
• $X_2 = (17\cdot 2 + 43)\bmod 100 = 77$, $U_2=0.77$
• $X_3 = (17\cdot 77 + 43)\bmod 100 = (1309+43)\bmod100 = 1352\bmod100 = \mathbf{52}$, $U_3=0.52$
• $X_4 = (17\cdot 52 + 43)\bmod 100 = (884+43)\bmod100 = 927\bmod100 = \mathbf{27}$, $U_4=0.27$
• $X_5 = (17\cdot 27 + 43)\bmod 100 = 2$, $U_5=0.02$

Sequence: 2, 77, 52, 27, 2, … with U-values 0.02, 0.77, 0.52, 0.27, 0.02.

Period comment: $X_4 = 27 = X_0$, so the sequence repeats with period 4 — far below the maximum possible $m=100$. The Hull–Dobell conditions are not met (e.g. $a-1=16$ is not a multiple of every prime factor of 100; in particular not of 5), so this is a poor generator.

(b) Hull–Dobell theorem — maximum period (4)

A mixed LCG $X_{i+1}=(aX_i+c)\bmod m$ with $c>0$ attains the full period $m$ iff:

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. If $m$ is a multiple of 4, then $a-1$ is also a multiple of 4.

(c) Inverse-transform for the exponential (5)

The exponential cdf is $F(x)=1-e^{-\lambda x},\ x\ge 0$. Set $U=F(X)$ and invert:

$$U = 1-e^{-\lambda X}\ \Rightarrow\ e^{-\lambda X}=1-U\ \Rightarrow\ X = -\frac{1}{\lambda}\ln(1-U).$$

Since $1-U$ is also $U(0,1)$, one often uses $X=-\tfrac{1}{\lambda}\ln U$.

Algorithm: (1) generate $U\sim U(0,1)$; (2) return $X=-\tfrac{1}{\lambda}\ln(1-U)$.

Numerical: $U=0.25,\ \lambda=0.5$:

$$X=-\frac{1}{0.5}\ln(1-0.25) = -2\ln(0.75) = -2(-0.2877) = \mathbf{0.575}.$$

(a) Verification vs. Validation (7)

• Verification — "Did we build the model right?" It concerns the programming/computer model: checking that the conceptual model has been correctly translated into a working computer program (debugging).
• Validation — "Did we build the right model?" It concerns whether the model is an accurate representation of the real system for its intended purpose (comparing model behaviour with the real world).

Four techniques to verify a simulation program (any four):

1. Have the program/model checked (read/reviewed) by more than one person (structured walkthrough).
2. Make the flow of the program logic as self-documenting and modular as possible, and trace it for a few simple cases by hand.
3. Use a trace — print out the state, clock and event list step by step and compare with hand calculations.
4. Run the model under simplifying assumptions with known analytic results (e.g. exponential service so M/M/1 formulas apply) and compare.
5. Use animation to watch the dynamic behaviour and spot logical errors.

(b) Transient (warm-up) period (4)

In a steady-state simulation the system starts from an artificial empty-and-idle (or other non-representative) initial condition. The early output is biased by these initial conditions — this initial biased portion is the transient or warm-up period. If included, it biases the steady-state estimates, so the data collected during the warm-up must be deleted (truncated) before output analysis.

Welch's method: make several replications, compute the ensemble average of the response at each time step across replications, then smooth this averaged process with a moving average of window $w$. Plot the smoothed averages versus time; the warm-up length $l$ is taken as the time after which the plot levels off (flattens). Data collected before $l$ are discarded.

(c) Terminating vs. Non-terminating simulation (3)

• Terminating simulation: has a natural event that ends the run and a clearly defined start/stop condition; interest is in behaviour over that finite horizon. Example: a bank that opens at 9 am and closes at 5 pm (simulate one day).
• Non-terminating (steady-state) simulation: has no natural ending event; interest is in long-run (steady-state) behaviour. Example: a continuously running manufacturing/assembly line or telephone exchange operating 24×7.

For an M/M/1 queue with $\lambda=8/\text{hr}$ and $\mu=10/\text{hr}$:

(i) Utilization: $\rho=\dfrac{\lambda}{\mu}=\dfrac{8}{10}=\mathbf{0.8}$ (stable since $\rho<1$).

(ii) Number in system: $L=\dfrac{\rho}{1-\rho}=\dfrac{0.8}{0.2}=\mathbf{4\ \text{customers}}$.

(iii) Time in system: $W=\dfrac{1}{\mu-\lambda}=\dfrac{1}{10-8}=0.5\ \text{hr}=\mathbf{30\ \text{min}}$. (Check via Little: $L=\lambda W = 8\times0.5=4$ ✓.)

(iv) Number waiting in queue: $L_q=\dfrac{\rho^2}{1-\rho}=\dfrac{0.64}{0.2}=\mathbf{3.2\ \text{customers}}$.

Random numbers must satisfy two properties: uniformity (each value equally likely on $[0,1]$) and independence (no correlation between successive numbers).

Chi-square frequency test (uniformity)

Tests uniformity. Divide $[0,1]$ into $n$ equal sub-intervals (classes). For $N$ numbers, the expected count per class is $E_i=N/n$. With observed counts $O_i$, compute

$$\chi_0^2=\sum_{i=1}^{n}\frac{(O_i-E_i)^2}{E_i}.$$

Null hypothesis $H_0$: the numbers are uniformly distributed on $[0,1]$. Reject $H_0$ if $\chi_0^2 > \chi^2_{\alpha,\,n-1}$ (table value with $n-1$ degrees of freedom at significance level $\alpha$).

Runs (up-and-down) test (independence)

Tests independence. Scan the sequence and mark a '+' where a number is larger than its predecessor and '−' where it is smaller; a run is a maximal string of like signs. Count the total number of runs $a$. Under independence the expected number and variance are

$$\mu_a=\frac{2N-1}{3},\qquad \sigma_a^2=\frac{16N-29}{90}.$$

The standardized statistic $Z_0=\dfrac{a-\mu_a}{\sigma_a}$ is approximately standard normal. Null hypothesis $H_0$: the numbers are independent. Reject $H_0$ if $|Z_0|>z_{\alpha/2}$.

(a) Acceptance–Rejection technique (4)

Used to generate a variate $X$ with density $f(x)$ when direct inversion is hard. Choose a majorizing function: find a density $g(x)$ (easy to sample) and a constant $c$ with $f(x)\le c\,g(x)$ for all $x$.

Algorithm:

1. Generate Y from g(x).
2. Generate U ~ U(0,1), independent of Y.
3. If U <= f(Y) / (c g(Y))  then ACCEPT: return X = Y.
   else REJECT and go to step 1.

The acceptance probability is $1/c$, so a tight bound (small $c$) is efficient.

When preferred: when the cdf $F(x)$ has no closed-form inverse (so inverse-transform is impractical), e.g. the beta or gamma (non-integer shape) distributions, or when inversion is numerically expensive.

(b) Convolution method for an Erlang variate (2)

An Erlang-$k$ variate with rate $\lambda$ is the sum of $k$ independent exponential variates each with mean $1/\lambda$. Generate $k$ uniforms $U_1,\dots,U_k$ and form

$$X=\sum_{i=1}^{k}\Big(-\tfrac{1}{\lambda}\ln U_i\Big) = -\tfrac{1}{\lambda}\ln\!\Big(\prod_{i=1}^{k}U_i\Big).$$

This $X$ is Erlang-$k$ (a sum/convolution of exponentials).

Continuous vs. Discrete-event simulation

Components of a DES model

Described (diagram in words): a central simulation executive/main program repeatedly takes the most imminent event from the event list, advances the clock, calls the corresponding event routine, and updates state and counters.

• System state: the collection of state variables describing the system (e.g. number in queue, server status busy/idle).
• Simulation clock: a variable giving the current value of simulated time.
• Event (future-event) list: a list of future events with their scheduled times of occurrence, ordered by time; the simulation always processes the earliest one next.
• Statistical counters: variables that accumulate performance data (e.g. total waiting time, number served, area under the queue-length curve) for computing output measures.

(Diagram: clock → event list → pick imminent event → update system state → update statistical counters → schedule new events → back to event list.)

(a) Confidence interval for the mean response (4)

A confidence interval (CI) is an interval $[\,\bar{X}-h,\ \bar{X}+h\,]$ that contains the true mean response $\mu$ with a stated probability (e.g. 95%); $h$ is the half-width measuring the precision of the estimate.

Construction from $R$ independent replications: run the terminating simulation $R$ times with independent random-number streams, obtaining sample means $X_1,\dots,X_R$ (one per replication). Then

$$\bar{X}=\frac{1}{R}\sum_{i=1}^{R}X_i,\qquad S^2=\frac{1}{R-1}\sum_{i=1}^{R}(X_i-\bar{X})^2,$$

and the $100(1-\alpha)\%$ CI is

$$\bar{X}\ \pm\ t_{\,\alpha/2,\ R-1}\,\frac{S}{\sqrt{R}}.$$

The $X_i$ are i.i.d. across replications, which justifies the use of the $t$-distribution.

(b) Method of replication for variance of the sample mean (2)

Make $R$ independent replications, each giving one summary statistic $X_i$. Because the $X_i$ are i.i.d., the variance of the overall mean $\bar{X}$ is estimated by

$$\widehat{\operatorname{Var}}(\bar{X})=\frac{S^2}{R}=\frac{1}{R(R-1)}\sum_{i=1}^{R}(X_i-\bar{X})^2.$$

Replications break the autocorrelation present within a single run, giving an unbiased variance estimate.

Steps in a sound simulation study (with V&V)

The iterative cycle (Banks/Law) is:

1.  Problem formulation
2.  Setting of objectives and overall project plan
3.  Model conceptualization  ┐
4.  Data collection          ┘ (often done together)
5.  Model translation (coding into a program/language)
6.  VERIFIED?  ── no ──> back to step 5 (coding)   [VERIFICATION]
        │ yes
        v
7.  VALIDATED? ── no ──> back to steps 3 & 4 (concept/data) [VALIDATION]
        │ yes
        v
8.  Experimental design
9.  Production runs and analysis
10. More runs?  ── yes ──> back to step 8
        │ no
        v
11. Documentation and reporting
12. Implementation

Where V&V fit:

• Verification is the check after model translation (step 5): is the program a correct implementation of the conceptual model? A failure loops back to fixing the code.
• Validation is the next check: does the (verified) model accurately represent the real system? A failure loops back to model conceptualization and data collection (steps 3–4).

Thus the cycle is iterative — the model is repeatedly refined until both verified and validated before production runs are made.

Little's Law

$$\boxed{L = \lambda\, W}$$

Meaning of terms:

• $L$ = the long-run average number of customers in the system.
• $\lambda$ = the long-run average arrival (throughput) rate of customers into the system.
• $W$ = the long-run average time a customer spends in the system.

In words: the average number in the system equals the arrival rate multiplied by the average time each customer stays. (It applies equally to the queue alone: $L_q=\lambda W_q$.)

Numerical: given $L=4$ and $\lambda=2$ customers/min,

$$W=\frac{L}{\lambda}=\frac{4}{2}=\mathbf{2\ \text{minutes}}.$$

Assumptions under which Little's law holds:

1. The system is in steady state (stable), so long-run averages exist.
2. Customers are conserved — every arrival eventually departs (no creation/loss inside the system).
3. The arrival rate $\lambda$ equals the departure rate (rate in = rate out over the long run).

It is distribution-free: it needs no assumption about the arrival or service distributions or the queue discipline.

(Any two of the following.)

(a) Discrete empirical (table-lookup) random variate

For a discrete random variable taking values $x_1<x_2<\dots$ with probabilities $p_i=P(X=x_i)$, build the cumulative distribution $F(x_k)=\sum_{i\le k}p_i$. To generate a variate: draw $U\sim U(0,1)$, then find the smallest $k$ such that $U\le F(x_k)$ and return $X=x_k$. This is the inverse-transform method applied to a step cdf (a table lookup of $U$ against the cumulative-probability column).

(b) Poisson process and the exponential distribution

A Poisson process with rate $\lambda$ counts random arrivals such that the number of events in an interval of length $t$ is Poisson distributed with mean $\lambda t$, and counts in disjoint intervals are independent. Its key link: the inter-arrival times are independent exponential random variables with mean $1/\lambda$. Equivalently, if events occur as a Poisson process, the time between successive events is $\text{Exp}(\lambda)$; this is the memoryless property and is why exponential service/arrival times generate Poisson counts in queuing models.

(c) Pseudo-random numbers and desirable properties

Pseudo-random numbers are deterministically generated (by an algorithm such as an LCG) yet appear random; being deterministic, they are reproducible. A good generator should be:

1. Uniform — values evenly distributed on $[0,1]$.
2. Independent — no correlation between successive numbers.
3. Long period — repeats only after a very large cycle.
4. Fast and memory-efficient, and reproducible (same seed → same stream) and portable across machines.