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

True vs Pseudo-Random Numbers

True random numbers are genuinely unpredictable but cannot be reproduced, so simulation uses pseudo-random numbers: a deterministic sequence that appears random and passes statistical tests of uniformity and independence.

Linear Congruential Method (LCG)

The LCG generates a sequence of integers $X_0, X_1, X_2, \dots$ using the recurrence:

where:

• $X_0$ = seed (start value), $0 \le X_0 < m$
• $a$ = multiplier, $c$ = increment, $m$ = modulus

Random numbers in $[0,1)$ are obtained by $R_i = X_i / m$.

If $c \ne 0$ it is a mixed LCG; if $c = 0$ it is a multiplicative LCG. The maximum period is $m$; choosing $a, c, m$ carefully (Hull–Dobell conditions) gives a full period.

Example

Let $a = 5,\ c = 3,\ m = 16,\ X_0 = 7$.

So the generated sequence is $7, 6, 1, 8, 11, \dots$ giving uniform random numbers $0.375, 0.0625, 0.5, 0.6875, \dots$

Discrete-Event Simulation (DES)

In discrete-event simulation the state of the system changes only at discrete points in time, called events (e.g. a customer arrival, start/end of service). Between events the system state is assumed constant, so the simulation "jumps" from one event to the next rather than advancing in fixed steps. This makes DES efficient for systems such as queues, networks and inventories.

Key components:

• System state – variables describing the system (e.g. number in queue, server busy/idle).
• Simulation clock – current value of simulated time.
• Event list (FEL) – list of future events ordered by their scheduled time.
• Statistical counters – accumulate output measures (waiting time, utilisation).

Event-Scheduling / Time-Advance Algorithm

The next-event time-advance approach repeatedly removes the most imminent event from the future event list (FEL), advances the clock to that event's time, executes the corresponding event routine (which updates state, statistics and may schedule new events), and repeats.

1. Initialize: clock = 0, set initial state,
   initialize statistical counters,
   schedule initial (first arrival) event in FEL.
2. While FEL not empty AND stopping condition not met:
     a. Remove the imminent event (smallest event time) from FEL.
     b. Advance simulation clock to that event time.
     c. Execute the event routine:
          - update system state
          - update statistical counters
          - generate future events and insert into FEL
3. End: compute and report output statistics.

Flowchart (described in words)

        +------------------------+
        |   Initialization        |
        | clock=0, FEL, counters  |
        +-----------+------------+
                    v
        +------------------------+
        | Remove imminent event   |
        | Advance clock to it     |
        +-----------+------------+
                    v
        +------------------------+
        | Execute event routine:  |
        | update state & stats,   |
        | schedule new events     |
        +-----------+------------+
                    v
            < Stop condition? >---No--> (back to Remove imminent event)
                    | Yes
                    v
        +------------------------+
        | Generate report /       |
        | output statistics       |
        +------------------------+

The loop continues until a stopping condition (fixed time, fixed number of customers, or empty FEL) is reached, after which output measures are reported.

Steps in a Sound Simulation Study

A disciplined simulation study (Banks, Carson, Nelson & Nicol) follows these stages:

1. Problem formulation – clearly state the problem and objectives.
2. Setting objectives and overall project plan – define questions to answer, scope, resources, timeline.
3. Model conceptualization – abstract the real system into a conceptual model (entities, variables, logic).
4. Data collection – gather input data (arrival rates, service times, distributions).
5. Model translation – code the model in a simulation language/package (GPSS, SIMSCRIPT, Arena, etc.).
6. Verification – check that the program correctly implements the conceptual model (debugging).
7. Validation – check that the model accurately represents the real system; compare with real data, often iteratively (loops back to conceptualization/data).
8. Experimental design – decide which scenarios, run lengths, number of replications.
9. Production runs and analysis – execute runs and statistically analyse output.
10. More runs? – if needed, design and run additional experiments.
11. Documentation and reporting – document model, assumptions and results.
12. Implementation – put the recommended solution into practice.

Flowchart (described in words)

Problem formulation
        |
Set objectives & project plan
        |
Model conceptualization <---------+
        |                          |
Data collection ------------------+   (loops back if validation fails)
        |
Model translation (coding)
        |
   < Verified? >--No--> back to Model translation
        | Yes
   < Validated? >--No--> back to Model conceptualization / data
        | Yes
Experimental design
        |
Production runs & analysis
        |
   < More runs? >--Yes--> Experimental design
        | No
Documentation & reporting
        |
Implementation

Verification and validation are decision points that feed back into earlier stages, making the process iterative rather than purely sequential.

Markov Chains

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

The one-step transition probabilities $p_{ij}$ form a transition matrix $P$, where each row sums to 1. The state probability vector after $n$ steps is $\pi^{(n)} = \pi^{(0)} P^{n}$, and the long-run (steady-state) distribution $\pi$ satisfies $\pi = \pi P$.

Application in Simulation

Markov chains model systems whose future depends only on present state, e.g. machine up/down status, weather, customer brand switching, queue length. In simulation we generate a uniform random number $R$ at each step and use the current row of $P$ to decide the next state, producing a realistic state trajectory.

Example (Weather)

States: Sunny (S), Rainy (R), with

If today is Sunny, then $P(\text{Sunny tomorrow}) = 0.8$. To simulate, draw $R \in [0,1)$: if $R < 0.8$ next state is Sunny, else Rainy. The steady-state $\pi = (\pi_S, \pi_R)$ solves $\pi = \pi P$, giving $\pi_S = 2/3,\ \pi_R = 1/3$ — i.e. about 67% sunny days in the long run.

Physical vs Mathematical Models

Physical (iconic) model – a tangible, scaled physical representation of the real system that looks and/or behaves like it. The model's properties are represented by physical properties.

Mathematical model – represents the system using mathematical symbols, equations and logical relationships among variables; it is solved analytically or by simulation rather than built physically.

Examples

• Physical models: a wind-tunnel model of an aircraft, a scaled model of a dam or building, a globe representing the Earth.
• Mathematical models: Newton's $F = ma$, the queuing relation $L = \lambda W$ (Little's law), $X_{i+1}=(aX_i+c)\bmod m$ for an LCG, a set of differential equations describing population growth.

Most computer simulations are built on mathematical models because they are flexible, inexpensive and allow rapid experimentation.

Mid-Square Method

Proposed by von Neumann, it generates random numbers by squaring the seed and extracting the middle digits.

Steps (for $n$-digit numbers):

1. Take a seed $X_0$ of $n$ digits.
2. Square it; pad with leading zeros to $2n$ digits.
3. Extract the middle $n$ digits → next number $X_1$.
4. Repeat; $R_i = X_i / 10^{n}$.

Example ($n=4$, seed $= 5735$):

• $5735^2 = 32890225$ → middle 4 digits $= 8902$ → $X_1 = 8902,\ R_1 = 0.8902$
• $8902^2 = 79245604$ → middle 4 digits $= 2456$ → $X_2 = 2456,\ R_2 = 0.2456$

Drawback: if the middle digits become 0 the sequence degenerates and the period can be short.

Additive Congruential Method

This method extends the linear congruential idea by adding two (or more) previous values instead of multiplying. The general recurrence uses the last $k$ seeds:

A common form (lagged Fibonacci) uses two earlier terms:

It requires an initial set of $k$ seed values. It is fast and can achieve very long periods, but is more sensitive to the choice of seeds and lags than the LCG.

Example: with $m = 10$ and seeds $X_1=1, X_2=1, X_3=2$, using $X_i=(X_{i-1}+X_{i-2})\bmod 10$: $X_4=(2+1)=3$, $X_5=(3+2)=5$, $X_6=(5+3)=8$, $X_7=(8+5)\bmod10=3,\dots$

Basic Simulation Terminology

• Entity – an object of interest in the system whose behaviour is modelled. It may be dynamic (moves through the system, e.g. a customer, a part) or static (e.g. a server). Example: customers in a bank.

• Attribute – a property or characteristic of an entity. Example: a customer's arrival time, priority, or account balance.

• Activity – a time-consuming operation or process that changes the system, with a known/specified duration. Example: the service of a customer by a teller.

• Event – an instantaneous occurrence that changes the state of the system (it takes no time). Example: a customer arrival or a service completion (departure).

• State of the system – the collection of variables needed to describe the system at any instant, relative to the study's objectives. Example: number of customers in the queue and whether the teller is busy or idle.

Thus events are the instants at which activities begin and end, entities possess attributes, and the values of the state variables evolve as events occur.

Importance of Output Analysis

Simulation output is random (because inputs are random variates), so a single run gives only one realization. Output analysis applies statistical methods to these random outputs to draw valid conclusions. Its importance:

• Estimates performance measures (mean waiting time, utilisation) with confidence intervals rather than a single uncertain number.
• Distinguishes real differences between system alternatives from random noise.
• Determines required run length, warm-up period and number of replications.
• Prevents wrong decisions from treating one lucky/unlucky run as truth.

Terminating vs Steady-State Simulation

In terminating simulations the modeller runs many independent replications and averages; in steady-state simulations the initial transient is removed and methods like batch means are used to estimate the long-run mean.

Poisson Distribution

A discrete distribution giving the probability of $k$ events occurring in a fixed interval when events happen independently at a constant average rate $\lambda$:

with mean $= \lambda$ and variance $= \lambda$. It models the number of arrivals per unit time.

Exponential Distribution

A continuous distribution describing the time between successive events of a Poisson process, with rate $\lambda$:

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

Role in Queuing Simulation

These two distributions are duals: if arrivals are Poisson with rate $\lambda$ (number per unit time), then inter-arrival times are exponential with mean $1/\lambda$. The same holds for service: exponential service times correspond to Poisson service completions. This is the basis of the classic M/M/1 queue (Markovian arrivals/Markovian service, one server), where both inter-arrival and service times are exponential.

In simulation we generate exponential inter-arrival and service times by inversion:

These variates drive the event list to schedule arrivals and departures.

General-Purpose Simulation Language (GPSS)

GPSS (General Purpose Simulation System) is a process/transaction-oriented, discrete-event simulation language especially suited to queuing systems. Its main features:

• Transaction (entity) flow model: the system is described as dynamic entities called transactions moving through a sequence of blocks that represent operations (GENERATE, ADVANCE, QUEUE, SEIZE, RELEASE, TERMINATE).
• Built-in resources: Facilities (single-server resources), Storages (multi-capacity resources) and Queues are predefined, so modelling servers and waiting lines is easy.
• Automatic clock and event handling: the simulation clock, future-event scheduling and entity movement are managed by the system; the modeller does not code the time-advance logic.
• Built-in random-number and distribution generators for arrival and service times.
• Automatic statistics collection: utilisation, queue length, average waiting time and counts are gathered and reported automatically.
• Block-diagram (flowchart) representation: models map directly to an easy-to-read block diagram, reducing programming effort.

Because these queuing constructs and statistics are built in, GPSS lets a modeller build and analyse discrete-event models quickly with little general-purpose programming, at the cost of less flexibility than a general language.

Chi-Square Test for Uniformity

The chi-square ($\chi^2$) goodness-of-fit test checks whether a set of random numbers is uniformly distributed on $[0,1)$.

Procedure:

1. Divide $[0,1)$ into $n$ equal sub-intervals (classes).
2. Count the observed frequency $O_i$ of numbers falling in each class.
3. For $N$ numbers and $n$ equal classes the expected frequency is $E_i = N/n$.
4. Compute the statistic

5. Compare with the critical value $\chi^2_{\alpha, n-1}$ (degrees of freedom $= n-1$). If $\chi^2_0 \le \chi^2_{\alpha,n-1}$, do not reject $H_0$ — the numbers are uniform.

Example

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

Degrees of freedom $= 9$. At $\alpha = 0.05$, $\chi^2_{0.05,9} = 16.92$. Since $3.0 < 16.92$, we do not reject $H_0$: the numbers are uniformly distributed.

Classification of Simulation Models

Static vs Dynamic

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

Deterministic vs Stochastic

• Deterministic model: contains no random variables; the same input always gives the same output. Example: a set of differential equations for a known chemical reaction.
• Stochastic model: contains one or more random variables, so outputs are themselves random and must be analysed statistically. Example: a queue with random (exponential) arrival and service times.

Continuous vs Discrete

• Continuous model: the state variables change continuously with respect to time, typically described by differential equations. Example: the level of water in a reservoir.
• Discrete model: the state variables change only at discrete points in time (events). Example: the number of customers in a queue, which changes only at arrivals/departures.

These dimensions are independent; a real model is described by one choice from each pair (e.g. a single-server queue is dynamic, stochastic, discrete).