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

Steps in a Sound Simulation Study

A disciplined simulation study follows a sequence of well-defined stages (Banks, Carson, Nelson & Nicol):

1. Problem formulation — State the problem clearly; analyst and client agree on objectives.
2. Setting of objectives and overall plan — Define questions to be answered, performance measures, resources, time and budget.
3. Model conceptualization — Abstract the real system into a conceptual model (entities, attributes, events, state variables). Start simple and add detail.
4. Data collection — Gather input data (e.g., inter-arrival and service times) and fit probability distributions.
5. Model translation — Code the model in a simulation language (GPSS, Arena) or a general language (C++/Python).
6. Verification — Check that the program correctly implements the conceptual model (debugging). Is the model built right?
7. Validation — Check that the model accurately represents the real system, often by comparing output with real data. Is it the right model? (Loop back to step 3/4 if invalid.)
8. Experimental design — Decide which alternatives to simulate, run length, number of replications, warm-up period.
9. Production runs and analysis — Execute runs and statistically analyze output to estimate performance measures.
10. More runs? — Decide whether additional runs/scenarios are needed (loop back if yes).
11. Documentation and reporting — Document the model (program and progress) and report results.
12. Implementation — Put the recommended solution into practice.

Flowchart (described in words)

          Problem Formulation
                  |
        Setting Objectives & Plan
                  |
        Model Conceptualization <----+
                  |                   |
           Data Collection           | (No)
                  |                   |
           Model Translation         |
                  |                   |
        Verification? --No--> (fix code)
                  | Yes               |
        Validation? --No--------------+
                  | Yes
           Experimental Design
                  |
        Production Runs & Analysis
                  |
           More Runs? --Yes--> (back to runs)
                  | No
        Documentation & Reporting
                  |
            Implementation

The verification and validation steps form feedback loops back to model building, and the "more runs?" decision loops back to production runs.

Verification and Validation

Verification is the process of determining whether the simulation computer program correctly implements the conceptual model — i.e. "Is the model built right?" It is essentially debugging: checking code logic, the operational model, and that inputs are processed as intended.

Validation is the process of determining whether the model is an accurate representation of the real system for the study's objectives — i.e. "Is it the right model?" It establishes credibility so that decision-makers trust the results.

Three-Step Approach (Naylor and Finger)

To build valid and credible models, Naylor and Finger proposed a three-step approach:

1. Build a model with high face validity.

   • The model should appear reasonable to people knowledgeable about the system.
   • Involve domain experts and potential users; use sensitivity analysis to confirm output changes sensibly when inputs change.

2. Validate model assumptions.

   • Structural assumptions — how the system operates (e.g., FIFO queue discipline, single vs. multiple servers).
   • Data assumptions — the probability distributions chosen for inputs (e.g., exponential inter-arrival times), validated by goodness-of-fit tests (chi-square, K-S).

3. Validate input-output transformations.

   • Treat the model as a black box and compare its output with that of the real system for the same inputs.
   • Use statistical techniques (e.g., confidence intervals, hypothesis tests like the paired-t test) to compare model output measures with real-world measures.

If any step fails, the analyst loops back to refine the conceptual model, data, or code before re-validating.

Definitions

• System — A collection of entities (people, machines, etc.) that interact together over time toward the accomplishment of some logical end. It has a boundary, environment, entities, attributes, activities, events and state variables.
• Model — A simplified representation or abstraction of a system used to study and predict the system's behavior. It captures the essential features relevant to the study.
• Simulation — The imitation of the operation of a real-world system over time, by building a model and running it to generate an artificial history from which performance measures are estimated.

Types of Models

Models are broadly classified as:

• Physical (iconic) models — Scaled physical replicas (e.g., a model airplane, a globe).
• Mathematical / symbolic models — Use symbols and equations to represent the system. These split into:
  • Static vs. Dynamic — static represents a system at a point in time (Monte Carlo); dynamic represents change over time.
  • Deterministic vs. Stochastic — deterministic has no random variables; stochastic has one or more random inputs.
  • Continuous vs. Discrete — continuous state changes continuously over time; discrete state changes only at discrete event points.

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

Advantages of Simulation

• Allows study of systems too complex for analytical solution.
• New policies, designs and methods can be explored without disrupting the real system.
• Hypotheses about how/why phenomena occur can be tested.
• Time can be compressed or expanded; bottlenecks can be identified.
• Helps understand how the system really works and "what-if" analysis.

Disadvantages of Simulation

• Model building requires special training and is an art; results vary with skill.
• Results may be hard to interpret because outputs are random variables.
• Simulation modeling and analysis can be time-consuming and expensive.
• It is used where an analytical solution is preferable but unavailable; sometimes used inappropriately when an exact analytical method exists.

Importance of Output Analysis

Simulation output (e.g., average waiting time, utilization) consists of random variables, so a single run gives only one realization that may be far from the true mean. Output analysis applies statistical methods to estimate performance measures and their confidence intervals, ensuring conclusions are reliable rather than the result of randomness. It addresses autocorrelation between observations, choice of run length, number of replications, and removal of initialization bias.

Terminating vs. Steady-State Simulation

Poisson Distribution

The Poisson distribution models the number of events (e.g., arrivals) occurring in a fixed interval when events happen independently at a constant average rate $\lambda$:

with mean and variance both equal to $\lambda$. It is discrete.

Exponential Distribution

The exponential distribution models the continuous time between successive events (inter-arrival or service times) with rate $\lambda$:

with mean $1/\lambda$. It is memoryless: $P(T > s+t \mid T > s) = P(T > t)$.

Role in Queuing Simulation

The two are intimately linked: if the number of arrivals in an interval is Poisson with rate $\lambda$, then the inter-arrival times are exponential with mean $1/\lambda$. In the classic M/M/1 queue, arrivals follow a Poisson process and service times are exponential. The memoryless property makes the system Markovian, enabling tractable analysis. In simulation, exponential inter-arrival and service times are easily generated by the inverse-transform method ($X = -\frac{1}{\lambda}\ln(1-R)$), driving the event clock of the queuing model.

Features of a General-Purpose Simulation Language (GPSS)

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

• Transaction (entity) flow model — Dynamic entities called transactions (e.g., customers, jobs) move through a network of blocks that represent the system's operations.
• Block-diagram structure — A model is built from a fixed set of standard blocks (GENERATE, QUEUE, SEIZE, ADVANCE, RELEASE, DEPART, TERMINATE), making programming largely graphical/declarative.
• Built-in resources and facilities — Facilities (single servers) and storages (multi-capacity servers) are provided to model service with automatic capture/release logic.
• Automatic event scheduling and clock management — The language maintains the simulation clock, future/current event chains and advances time automatically; the user does not write the event-list logic.
• Built-in random number and variate generators — Standard statistical distributions are available for inter-arrival and service times.
• Automatic statistics collection — Queue lengths, waiting times, utilization and throughput are gathered and reported automatically.
• Queue handling and standard numerical attributes (SNAs) — Provide system status (clock, queue contents) usable in logic.

These features let an analyst build and analyze queuing-type models quickly without low-level coding.

Chi-Square Test for Uniformity

The chi-square ($\chi^2$) test checks whether a sample of random numbers is uniformly distributed on $[0,1]$ (the frequency/uniformity test).

Procedure:

1. Divide $[0,1]$ into $n$ equal sub-intervals (classes).
2. With $N$ numbers, the expected count per class is $E_i = N/n$.
3. Count the observed number $O_i$ in each class.
4. Compute the statistic:

5. Compare with the critical value $\chi^2_{\alpha, n-1}$ (table) at significance $\alpha$ with $n-1$ degrees of freedom.
6. Decision: if $\chi^2_0 \le \chi^2_{\alpha,n-1}$, the hypothesis of uniformity is not rejected; otherwise it is rejected.

Example

Suppose $N = 100$ numbers are placed into $n = 10$ classes, so $E_i = 10$. Observed counts are:

With $df = 9$ and $\alpha = 0.05$, the table value $\chi^2_{0.05,9} = 16.919$. Since $3.0 < 16.919$, we fail to reject $H_0$; the numbers are accepted as uniformly distributed.

Classification of Mathematical Models

1. Static vs. Dynamic

• Static model: represents the system at a particular point in time; time plays no role. Example: a Monte Carlo model estimating $\pi$ or an integral.
• Dynamic model: represents the system as it evolves over time. Example: simulating a bank's queue over an 8-hour day.

2. Deterministic vs. Stochastic

• Deterministic model: contains no random variables; a given set of inputs always produces the same output. Example: a fixed-schedule appointment system, or solving $D = rt$.
• Stochastic model: has one or more random inputs, so outputs are themselves random and must be treated statistically. Example: arrivals at a bank following a Poisson process.

3. Continuous vs. Discrete

• Continuous model: the state variables change continuously with respect to time, usually described by differential equations. Example: water level in a reservoir, or the flow of a chemical process.
• Discrete model: the state variables change only at discrete (countable) points in time (events). Example: the number of customers in a queue, which changes only at arrival/departure events.

Most simulation models in computer science are dynamic, stochastic and discrete-event models.

Tests for Randomness

Generated random numbers must be tested for two properties: uniformity (frequency tests) and independence (autocorrelation/runs tests). Common tests include the chi-square test, the Kolmogorov-Smirnov (K-S) test, the runs test, the gap test, the poker test and the autocorrelation test.

Kolmogorov-Smirnov (Frequency) Test

The K-S test compares the empirical CDF $S_N(x)$ of the sample with the theoretical uniform CDF $F(x) = x$ on $[0,1]$.

Procedure:

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

3. Let $D = \max(D^{+}, D^{-})$.
4. Compare $D$ with the critical value $D_{\alpha}$ from the K-S table. If $D \le D_{\alpha}$, uniformity is not rejected; otherwise reject. The K-S test works well for small samples and is exact (no class grouping).

Runs Test (Test for Independence)

A run is a succession of similar events (e.g., a run "up" = increasing sequence, run "down" = decreasing). The runs test counts runs to detect dependence/trends in the sequence.

For a sequence of $N$ numbers, the expected number of runs and its variance are:

The test statistic is standardized:

where $a$ is the observed number of runs. If $|Z_0| \le Z_{\alpha/2}$, the hypothesis of independence is not rejected; otherwise the numbers show dependence.

Basic Properties of Random Numbers

A sequence of random numbers $R_1, R_2, \dots$ generated for simulation must possess two key statistical properties:

1. Uniformity

• The numbers must be uniformly distributed over the interval $[0,1]$; every value (or sub-interval) is equally likely.
• Formally, the probability density function is:

• Expected value $E(R) = \tfrac{1}{2}$ and variance $V(R) = \tfrac{1}{12}$.
• If $[0,1]$ is split into $n$ equal classes, each class should contain about $N/n$ of the $N$ numbers.

2. Independence

• Each random number must be statistically independent of the others; the probability of observing a value in any sub-interval is unaffected by previous values.
• There should be no correlation between successive numbers (no patterns, trends or cycles).

When both properties hold, the numbers behave like a true uniform $U(0,1)$ stream. Departures are detected by uniformity tests (chi-square, K-S) and independence tests (runs, autocorrelation, gap, poker).

Inverse Transform Technique — Exponential Distribution

The inverse transform method generates a random variate $X$ from a distribution with CDF $F(x)$ by setting $F(X) = R$, where $R \sim U(0,1)$, and solving $X = F^{-1}(R)$.

Step 1 — CDF of the exponential distribution. The exponential pdf with rate $\lambda$ (mean $1/\lambda$) is:

Its CDF is:

Step 2 — Set $F(X) = R$.

Step 3 — Solve for $X$.

Since $(1-R)$ is also uniform on $[0,1]$, this is commonly simplified to:

Example: with mean $1/\lambda = 2$ (so $\lambda = 0.5$) and $R = 0.4$:

Repeatedly applying this with fresh uniform numbers yields exponential inter-arrival or service times for the simulation.

Kendall's Notation

Kendall's notation describes a queuing system using the standard form:

where:

• A — the arrival process / inter-arrival time distribution.
• B — the service time distribution.
• c — the number of parallel servers.
• N — the system capacity (maximum number in the system, queue + in service). Omitted if $\infty$.
• K — the size of the calling population (source). Omitted if $\infty$.

Common symbols for A and B:

• M — Markovian (exponential inter-arrival / service times; Poisson arrivals), memoryless.
• D — Deterministic (constant) times.
• E_k — Erlang distribution of order $k$.
• G — General (arbitrary) distribution.

The default queue discipline is FCFS (first-come, first-served) unless stated.

Examples

• M/M/1 — Poisson arrivals, exponential service, one server, infinite queue and population (the basic single-server queue).
• M/M/c — Poisson arrivals, exponential service, c servers (e.g., a bank with $c$ tellers).
• M/M/1/N — same as M/M/1 but with finite system capacity $N$ (e.g., a buffer of size $N$).
• M/D/1 — Poisson arrivals, constant service time, one server (e.g., automated car wash).
• G/G/1 — general arrival and service distributions, one server.