BSc CSIT (TU) Science Simulation and Modelling (BSc CSIT, CSC317) Question Paper 2081 Nepal

Model Verification and Validation

Verification is the process of checking that the computer/simulation program correctly implements the conceptual (assumptions) model — i.e. "Are we building the model right?". It is concerned with debugging the program logic, ensuring the code, mathematical relations and data structures behave as intended.

Validation is the process of confirming that the conceptual model and its implementation are an accurate representation of the real system for the intended purpose — i.e. "Are we building the right model?". It compares model output with the behaviour of the actual system.

Three-Step Approach (Naylor and Finger) for Valid and Credible Models

1. Build a model with high face validity. Develop the model so that, on the surface, it appears reasonable to people knowledgeable about the system. This is achieved by:

   • Discussing the model with subject-matter experts and operators.
   • Collecting accurate, relevant input data.
   • Performing structured walk-throughs and sensitivity analysis of assumptions.

2. Validate the model assumptions. Assumptions fall into two classes:

   • Structural assumptions — how the system operates (e.g. queue discipline, number of servers, routing).
   • Data/distributional assumptions — based on statistical analysis of collected data; verified using goodness-of-fit tests (chi-square, K-S) to confirm chosen probability distributions and parameters.

3. Compare the model's input–output transformations with those of the real system. The model is validated as an input–output transformer: feed the model the same inputs the real system received and statistically compare outputs (e.g. using confidence intervals, hypothesis tests, the Turing test) against historical system data. If output matches within acceptable error, the model is considered valid and credible.

Credibility results when the manager/decision-maker accepts the model and uses its results — achieved through verification, validation, and good documentation/communication.

Definitions

• System: A collection of entities (people, machines, components) that interact together toward the accomplishment of some logical end. Example: a bank with tellers and customers.
• Model: A simplified abstraction or representation of a system used to study its behaviour, capturing the essential features relevant to the problem while omitting irrelevant detail.
• Simulation: The technique of imitating the operation of a real-world system over time using a model, generating an artificial history of the system from which performance estimates are drawn.

Types of Models

1. Physical (iconic) vs Mathematical models — physical models are scaled tangible replicas (e.g. wind-tunnel model); mathematical models represent the system by symbols, equations and logical relations.
2. Static vs Dynamic — static represents the system at a single point in time (Monte Carlo); dynamic represents the system as it evolves over time.
3. Deterministic vs Stochastic — deterministic has no random variables (fixed output for fixed input); stochastic contains random inputs producing random outputs.
4. Continuous vs Discrete — continuous models have state variables that change continuously with time; discrete models have state variables that change only at discrete (event) points.

Simulation models are typically mathematical, dynamic, stochastic and discrete-event.

Advantages of Simulation

• Allows study of complex systems that are intractable analytically.
• Can test new policies/designs without disturbing the real system.
• Compresses or expands time; supports "what-if" experimentation.
• Helps identify bottlenecks and understand variable interactions.
• Safer and cheaper than experimenting on the real system.

Disadvantages of Simulation

• Model building requires special training and is an art; results depend on the modeller's skill.
• Can be expensive and time-consuming to develop.
• Produces only estimates (with sampling error), not exact optimal answers.
• Large volumes of output may be misinterpreted.
• Validation and data collection can be difficult.

Characteristics and Structure of a Queuing System

A queuing system is described by the following key characteristics:

1. Calling population (input source): the population of potential customers; may be finite or infinite.
2. Arrival process: how customers arrive, usually described by the inter-arrival time distribution (often Poisson arrivals / exponential inter-arrival times with rate $\lambda$).
3. Queue (waiting line) capacity: finite or infinite number of customers that can wait.
4. Queue discipline: order of service — FIFO, LIFO, SIRO (random), or priority.
5. Service mechanism: number of servers and the service-time distribution (rate $\mu$).
6. System capacity: maximum number of customers allowed in the system.

Structure: Customers arrive from the calling population, join a queue if the server is busy, are served according to the queue discipline, and then leave the system.

Performance Measures of the M/M/1 Queue

The M/M/1 model has Poisson arrivals (rate $\lambda$), exponential service (rate $\mu$), a single server, infinite capacity and FIFO discipline. Define traffic intensity / utilization $\rho = \lambda/\mu$ (stable when $\rho < 1$).

• Server utilization: $\rho = \dfrac{\lambda}{\mu}$
• Probability of $n$ customers in system: $P_n = (1-\rho)\rho^{n}$; idle probability $P_0 = 1-\rho$.
• Average number in system: $L = \dfrac{\rho}{1-\rho} = \dfrac{\lambda}{\mu-\lambda}$
• Average number in queue: $L_q = \dfrac{\rho^{2}}{1-\rho} = \dfrac{\lambda^{2}}{\mu(\mu-\lambda)}$
• Average time in system: $W = \dfrac{1}{\mu-\lambda}$
• Average time in queue: $W_q = \dfrac{\rho}{\mu-\lambda} = \dfrac{\lambda}{\mu(\mu-\lambda)}$

These are linked by Little's law: $L = \lambda W$ and $L_q = \lambda W_q$.

Example: If $\lambda = 6$/hr and $\mu = 10$/hr, then $\rho = 0.6$, $L = 0.6/0.4 = 1.5$ customers, $W = 1/4$ hr = 15 min, $L_q = 0.36/0.4 = 0.9$ customers.

Features of a General-Purpose Simulation Language (GPSS)

GPSS (General Purpose Simulation System) is a process/transaction-oriented, discrete-event simulation language. Its key features are:

• Transaction-oriented (block) modelling: the system is described as a sequence of blocks through which dynamic entities called transactions flow (e.g. GENERATE, QUEUE, SEIZE, ADVANCE, RELEASE, TERMINATE).
• Built-in entities: facilities (single servers), storages (multi-server resources), queues, and logic switches are predefined, so the modeller need not program them.
• Automatic time advance and event scheduling: the simulation clock and the future-event handling are managed internally using next-event time-advance — the user does not write the clock-control routine.
• Built-in random number and variate generation from standard distributions.
• Automatic statistics collection: queue lengths, waiting times, facility utilization, etc., are gathered and reported automatically.
• Ease of use: little programming required, rapid model development, good for queuing/service systems.

Limitation: less flexible than general programming languages for highly customised logic.

Chi-Square Test for Uniformity of Random Numbers

The chi-square ($\chi^2$) test is a frequency test that checks whether generated random numbers are uniformly distributed over $[0,1]$.

Procedure:

1. Divide $[0,1]$ into $n$ equal subintervals (classes).
2. Count the observed frequency $O_i$ of numbers falling in each class.
3. Compute the expected frequency $E_i = N/n$ (for $N$ numbers, uniform expectation is equal per class).
4. Compute the statistic:

5. Compare with the critical value $\chi^2_{\alpha, n-1}$ (degrees of freedom $= n-1$). Accept uniformity (fail to reject $H_0$) if $\chi^2_0 \le \chi^2_{\alpha,n-1}$.

Example: Suppose $N = 100$ numbers are grouped into $n = 10$ intervals, so $E_i = 10$ each. If the observed counts give $\sum (O_i-E_i)^2/E_i = 4.2$, and the critical value $\chi^2_{0.05, 9} = 16.919$, then since $4.2 < 16.919$ we do not reject $H_0$ and conclude the numbers are uniformly distributed at the 5% level.

Classification of Models

• Static vs Dynamic

  • Static model: represents the system at a single point in time, ignoring time evolution. Example: Monte Carlo simulation of an integral.
  • Dynamic model: represents the system as it changes/evolves over time. Example: a queue observed over an 8-hour day.

• Deterministic vs Stochastic

  • Deterministic model: contains no random variables; the same input always gives the same output. Example: a fixed-formula chemical reaction model.
  • Stochastic model: contains one or more random variables, so outputs are themselves random and must be treated as estimates. Example: a bank simulation with random arrivals and service times.

• Continuous vs Discrete

  • Continuous model: the state variables change continuously with respect to time (described by differential equations). Example: water level in a reservoir.
  • Discrete model: the state variables change only at discrete, separate points in time (events). Example: number of customers in a shop, changing on each arrival/departure.

A typical discrete-event simulation model is dynamic, stochastic and discrete.

Tests for Randomness

After generating random numbers we test two properties: uniformity (frequency tests) and independence (run/autocorrelation tests). Two important tests:

Frequency Test — Kolmogorov–Smirnov (K-S) Test

Tests uniformity by comparing the empirical CDF of the sample with the theoretical uniform CDF $F(x)=x$ on $[0,1]$.

1. Rank the $N$ numbers in ascending order: $R_{(1)} \le R_{(2)} \le \dots \le R_{(N)}$.
2. Compute

3. Take $D = \max(D^+, D^-)$.
4. Compare $D$ with the critical value $D_{\alpha}$. If $D \le D_{\alpha}$, accept that the numbers are uniformly distributed.

Runs Test

Tests independence by examining the sequence of numbers for runs (a run is a succession of increasing or decreasing values — a run up or run down).

1. Count the total number of runs $a$ in the sequence.
2. For $N$ numbers, the expected number of runs and variance are:

3. Compute the standardized statistic $Z_0 = \dfrac{a - \mu_a}{\sigma_a}$.
4. If $|Z_0| \le Z_{\alpha/2}$, the hypothesis of independence is not rejected.

Basic Properties of Random Numbers

A sequence of random numbers $R_1, R_2, \dots$ (each between 0 and 1) must possess two important statistical properties:

1. Uniformity

The numbers are uniformly distributed over the interval $[0,1]$. If the interval is divided into $n$ equal sub-intervals, the expected number of observations in each is $N/n$ for $N$ numbers. Formally each $R_i$ has the density

with mean $E[R] = 1/2$ and variance $\mathrm{Var}(R) = 1/12$.

2. Independence

Each random number is statistically independent of the others; the probability of observing a value in any sub-interval is unaffected by previous values. Knowing $R_1, \dots, R_{i-1}$ gives no information about $R_i$ (no correlation/autocorrelation).

Violating uniformity biases results; violating independence introduces patterns/correlation. These properties are checked using frequency tests (chi-square, K-S) for uniformity and runs/autocorrelation tests for independence.

Inverse Transform Technique — Exponential Distribution

The inverse transform method generates a random variate $X$ from a distribution by setting its CDF equal to a uniform random number $R \sim U(0,1)$ and inverting.

Steps:

1. The exponential distribution with rate $\lambda$ (mean $1/\lambda$) has CDF:

2. Set $F(X) = R$:

3. Solve for $X$:

4. Since $(1-R)$ is also uniform on $[0,1]$, this simplifies to:

Example: For $\lambda = 2$ and $R = 0.25$:

Repeating with successive uniform numbers $R$ produces a stream of exponential variates.

Kendall's Notation

Queuing systems are described by the standard Kendall's notation, written as:

Where:

• A = inter-arrival-time distribution
• B = service-time distribution
• c = number of parallel servers
• N = system capacity (maximum number in system) — omitted means $\infty$
• K = size of the calling population — omitted means $\infty$
• (sometimes a 6th symbol for queue discipline, default FIFO)

Common symbols for A and B:

• M = Markovian / exponential (Poisson) — memoryless
• D = Deterministic (constant)
• G = General (arbitrary) distribution
• Ek = Erlang-k

Examples:

• M/M/1 — Poisson arrivals, exponential service, single server, infinite capacity and population (the basic single-server queue).
• M/M/c — Poisson arrivals, exponential service, $c$ servers (e.g. a bank with multiple tellers).
• M/D/1 — Poisson arrivals, constant (deterministic) service time, one server (e.g. an automated car wash).
• M/M/1/N — single-server queue with limited capacity $N$.

Simulation Clock

A simulation clock is a variable in a discrete-event simulation that holds the current value of simulated time. It does not run in real time; instead it is advanced by the program as events occur, keeping track of when the system reaches each state.

There are two mechanisms for advancing the clock:

Fixed-Increment Time Advance

• The clock is advanced by a fixed amount $\Delta t$ at each step.
• After each increment, the simulation checks whether any events occurred during the interval $(t, t+\Delta t]$ and processes them.
• Simple to implement, but events within an interval are treated as occurring at the interval end, causing rounding error; also wastes effort during intervals with no events.
• Suited to systems where events occur at regular intervals (and to continuous simulation).

Next-Event Time Advance

• The clock jumps directly to the time of the next (most imminent) event in the future-event list.
• No time is wasted on idle intervals; no events are missed or mis-timed.
• More efficient and accurate for discrete-event systems; used by most simulation languages (e.g. GPSS).

Markov Chains

A Markov chain is a stochastic process $\{X_n\}$ that moves among a set of states such that the probability of the next state depends only on the current state, not on the sequence of past states (the Markov / memoryless property):

The one-step transition probabilities $p_{ij}$ form a transition probability matrix $P$, where each row sums to 1. The $n$-step transition probabilities are obtained from $P^n$, and the long-run (steady-state) distribution $\pi$ satisfies $\pi = \pi P$ with $\sum_i \pi_i = 1$.

Application in Simulation

Markov chains model systems whose state changes probabilistically over time — e.g. machine up/down status, weather, inventory levels, customer brand switching, and queue states. In simulation they let us generate the next state by drawing a uniform random number against the cumulative transition probabilities of the current state, and to compute steady-state behaviour.

Example: Weather

States: Sunny (S), Rainy (R). Transition matrix:

If today is Sunny, there is an 80% chance tomorrow is Sunny and 20% chance Rainy. Solving $\pi = \pi P$ gives the long-run fractions of sunny and rainy days: $\pi_S = 2/3$, $\pi_R = 1/3$.