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

System, Model and Simulation

System: A collection of entities (people, machines, components) that act and interact together toward the accomplishment of some logical end. It has a state described by state variables (e.g., number of customers in a bank).

Model: A simplified abstract representation of a system that captures its essential features and the relationships among them, used to study the system without experimenting on the real thing.

Simulation: The technique of imitating the operation of a real-world system over time by driving a model with inputs and observing its behaviour, in order to evaluate performance, test alternatives, and predict outcomes.

Types of Models

• Physical (Iconic) vs Mathematical models — physical models are scaled-down tangible replicas (a wind-tunnel aircraft); mathematical models use symbols, equations and logical relations.
• Static vs Dynamic — a static model represents a system at one point in time (Monte Carlo); a dynamic model evolves over time (queue evolution).
• Deterministic vs Stochastic — deterministic models contain no randomness (same input → same output); stochastic models include random variables (random arrivals/service).
• Continuous vs Discrete — in continuous models state changes smoothly with time (fluid flow, differential equations); in discrete models state changes only at distinct event instants (customer arrival).

Most computer simulations of interest are dynamic, stochastic and discrete-event models.

Advantages of Simulation

• Allows study of systems that are too complex for analytical/mathematical solution.
• New policies, designs, and "what-if" scenarios can be tested without disturbing or building the real system.
• Time can be compressed (years simulated in seconds) or expanded.
• Bottlenecks and the effect of changing variables can be identified and understood.

Disadvantages of Simulation

• Building a valid model requires special training; results depend on model quality.
• Can be expensive and time-consuming to develop, run and analyse.
• Outputs are estimates with random error, sometimes mistaken for exact answers (hard to interpret).
• Easy to misuse: an invalid or poorly verified model gives misleading conclusions.

Characteristics and Structure of a Basic Queuing System

A queuing system arises whenever customers demand service from limited servers and may have to wait. Its key characteristics are:

1. Arrival (input) process — how customers arrive, described by the inter-arrival time distribution; often Poisson arrivals with rate $\lambda$.
2. Service mechanism — number of servers and the service-time distribution; often exponential service with rate $\mu$.
3. Queue (system) capacity — finite or infinite waiting room.
4. Queue discipline — order of service: FIFO, LIFO, priority, random.
5. Calling population — finite or infinite source of customers.

Structure: Calling population → Arrivals → Queue (waiting line) → Server(s) → Departures. Customers join the queue, wait if all servers are busy, get served, then leave.

Performance Measures of an M/M/1 Queue

M/M/1: Poisson arrivals (rate $\lambda$), exponential service (rate $\mu$), single server, infinite capacity, FIFO. Let the traffic intensity be $\rho = \lambda/\mu$ (system stable only if $\rho < 1$).

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

Example: If $\lambda = 6/\text{hr}$, $\mu = 8/\text{hr}$, then $\rho = 0.75$, $L = 0.75/0.25 = 3$ customers, $W = 1/(8-6) = 0.5$ hr = 30 min.

Monte Carlo Simulation Method

Monte Carlo simulation is a static, stochastic technique that uses repeated random sampling to obtain numerical estimates of quantities that may be deterministic but are difficult to compute analytically. The general steps are:

1. Define a domain of possible inputs and a probability model.
2. Generate inputs randomly (using random numbers $U \sim U(0,1)$).
3. Perform a deterministic computation on each sample.
4. Aggregate (average) the results to estimate the desired quantity.

As the number of samples $N \to \infty$, by the Law of Large Numbers the estimate converges to the true value; error decreases as $O(1/\sqrt{N})$.

Simple example (estimating an integral): to estimate $\int_0^1 f(x)\,dx$, draw $x_i \sim U(0,1)$ and average $f(x_i)$.

Estimating $\pi$ by Monte Carlo

Consider a unit square $[0,1]\times[0,1]$ containing a quarter circle of radius 1. The quarter circle has area $\pi/4$ and the square has area 1, so a random point lands inside the quarter circle with probability $\pi/4$.

Algorithm:

import random

def estimate_pi(N):
    inside = 0
    for _ in range(N):
        x = random.random()   # U(0,1)
        y = random.random()
        if x*x + y*y <= 1.0:  # inside quarter circle
            inside += 1
    return 4.0 * inside / N

print(estimate_pi(1_000_000))   # ~3.1416

Reasoning:

With $N = 1{,}000{,}000$ random points the estimate is close to $3.1416$; accuracy improves as $N$ increases.

Classification of Models

Static vs Dynamic

• Static model: represents a system at a particular instant of time, with no role for time evolution (e.g., a Monte Carlo model of a single roll of dice).
• Dynamic model: represents the system as it changes over time (e.g., a bank queue evolving as customers arrive and leave).

Deterministic vs Stochastic

• Deterministic model: contains no random variables; a given set of inputs always produces the same output (e.g., a fixed schedule of patients with known service times).
• Stochastic model: contains one or more random inputs, so outputs are themselves random and described by distributions (e.g., random customer arrivals and service times).

Continuous vs Discrete

• Continuous model: state variables change continuously with respect to time, usually described by differential equations (e.g., level of water in a reservoir).
• Discrete model: state variables change only at discrete (separated) points in time when events occur (e.g., number of customers changing only at an arrival or a departure).

These dimensions are independent; a typical simulation is dynamic, stochastic and discrete.

Tests for Randomness

Generated pseudo-random numbers must be tested for two properties: uniformity (the numbers are uniformly distributed on $(0,1)$) and independence (no correlation between successive numbers). Common tests include the frequency (Kolmogorov-Smirnov / chi-square) test for uniformity and the runs test, gap test, poker test, and autocorrelation test for independence.

Frequency Test — Kolmogorov-Smirnov (K-S)

The K-S test checks 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. Let $D=\max(D^{+},D^{-})$.
4. If $D \le D_{\alpha}$ (critical value from the K-S table for sample size $N$ and significance $\alpha$), accept the hypothesis that the numbers are uniform; otherwise reject.

Runs Test

The runs test checks independence. A run is a succession of similar events (e.g., a run up = increasing sequence, run down = decreasing). The numbers, not their values, are examined for the pattern of increases/decreases.

• Count the total number of runs $a$ in the sequence of $N$ numbers.
• Under independence, the mean and variance of the number of runs (runs up and down) are

• Form the standardized statistic $Z=\dfrac{a-\mu_a}{\sigma_a}$.
• If $-z_{\alpha/2}\le Z\le z_{\alpha/2}$, accept independence; otherwise reject (too few or too many runs indicates dependence).

Basic Properties of Random Numbers

A sequence of random numbers $R_1, R_2, \dots$ used in simulation must behave like independent draws from a Uniform $(0,1)$ distribution. The two essential statistical properties are uniformity and independence.

1. Uniformity

The numbers must be uniformly distributed over the interval $(0,1)$; every value is equally likely. If the interval is divided into $n$ equal sub-intervals, each should contain about $N/n$ of the $N$ numbers. Formally, the probability density function is

with expected value $E(R)=\tfrac12$ and variance $\operatorname{Var}(R)=\tfrac{1}{12}$.

2. Independence

Each random number must be statistically independent of the others; the value of one number gives no information about the next. Therefore there should be no correlation between successive numbers, and the probability of observing a value in any sub-interval is independent of previous values.

Uniformity is verified using frequency tests (chi-square, Kolmogorov-Smirnov); independence is verified using the runs test, autocorrelation test, gap test, etc. A generator satisfying both properties produces numbers acceptable for simulation.

Inverse Transform Technique (Exponential Distribution)

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

Steps

1. Write the CDF. The exponential distribution with rate $\lambda$ (mean $1/\lambda$) has pdf $f(x)=\lambda e^{-\lambda x}$, $x\ge 0$, and CDF

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

3. Solve for $X$:

4. Simplify. Since $1-R$ is also $U(0,1)$, we may write

Example

If $\lambda = 2$ and a random number $R = 0.25$, then

Each uniform random number $R$ thus yields one exponential variate; repeating gives a sample of exponential inter-arrival or service times for the simulation.

Kendall's Notation for Queuing Systems

Kendall's notation is a shorthand $A/B/c/N/K/Z$ used to describe a queuing system, where:

Usually only the first three are written: A/B/c. Common codes for A and B:

• M — Markovian / exponential (Poisson process)
• D — Deterministic (constant)
• E$_k$ — Erlang of order $k$
• G — General (arbitrary) distribution

Examples

• M/M/1 — Poisson arrivals, exponential service, single server, infinite capacity, FIFO.
• M/M/c — Poisson arrivals, exponential service, $c$ identical servers (e.g., bank with $c$ tellers).
• M/D/1 — Poisson arrivals, constant (deterministic) service time, one server (e.g., automated car wash).
• M/M/1/N — single server but finite capacity $N$ (customers turned away when full).
• G/G/1 — general arrival and service distributions, one server.

Simulation Clock

The simulation clock is a variable that records the current value of simulated time in the model. It is not real time; it advances according to the model logic and tells the simulation "when" the current state holds. Because nothing of interest happens between events, the clock is advanced from event to event. Two mechanisms advance it:

Fixed-Increment Time Advance

• The clock advances in uniform, fixed steps $\Delta t$ (e.g., 1 minute at a time).
• After each step, the model checks whether any events occurred during that interval and processes them, assuming they happened at the end (or start) of the interval.
• Pros: simple; suitable for continuous systems sampled periodically.
• Cons: wasted computation on intervals with no events; loss of accuracy because events are forced onto step boundaries; choosing $\Delta t$ is a trade-off between speed and precision.

Next-Event Time Advance

• The clock jumps directly to the time of the next imminent event, skipping idle periods.
• The system maintains a future event list (FEL); at each step the earliest event is selected, the clock is set to that event time, and the state and statistics are updated.
• Pros: no idle steps, so it is efficient; events are processed at their exact times (accurate). This is the standard mechanism for discrete-event simulation.
• Cons: more complex bookkeeping (event list management).

Key Difference

Fixed-increment moves time in equal pre-set steps regardless of events; next-event moves time to wherever the next event occurs, making it faster and more accurate for discrete-event systems.

Markov Chains

A Markov chain is a stochastic process $\{X_n\}$ that moves among a set of states such that the future state depends only on the present state, not on the past — the memoryless or Markov property:

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

Application in Simulation

Markov chains model systems whose state evolves probabilistically over time — queue lengths, machine up/down status, weather, inventory levels, web-page navigation, and Markov-Chain Monte Carlo (MCMC) sampling. In simulation, the transition matrix is used with random numbers to decide the next state at each step.

Example — Weather Model

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

If today is Sunny, then $P(\text{tomorrow Rainy})=0.2$. To simulate, draw $R\sim U(0,1)$: from state S, if $R<0.8$ next state is Sunny, else Rainy. Iterating generates a sequence of weather states whose long-run fractions converge to the steady-state distribution found from $\pi=\pi P$ (here $\pi_S=\tfrac{2}{3}$, $\pi_R=\tfrac{1}{3}$).

Physical Models vs Mathematical Models

Physical (Iconic) Model: A tangible, scaled physical replica of the real system that looks like what it represents. It captures geometric and physical properties and is used for visualization and physical experimentation.

Mathematical Model: An abstract representation that uses symbols, variables, equations and logical relationships to describe how the system behaves. It captures functional relationships rather than physical appearance and is studied analytically or by computer simulation.

Examples:

• Physical: a miniature aeroplane tested in a wind tunnel; a planetarium model of the solar system.
• Mathematical: Newton's law of motion $F=ma$; an M/M/1 queue described by its rate equations; a computer simulation of traffic flow.

Most computer simulations use mathematical models because they are flexible, inexpensive and easy to experiment with.

Mid-Square Method

A technique proposed by von Neumann to generate pseudo-random numbers:

1. Start with a seed $X_0$ of $n$ digits (commonly 4 digits).
2. Square it to get a $2n$-digit number (pad with leading zeros if necessary).
3. Take the middle $n$ digits as the next number $X_1$.
4. Repeat; the random number in $(0,1)$ is $R_i = X_i / 10^{n}$.

Example (4-digit seed $X_0 = 7182$):

• $7182^2 = 51\,581\,124 \to$ middle 4 digits $= 5811$, so $X_1 = 5811$, $R_1 = 0.5811$.
• $5811^2 = 33\,767\,721 \to$ middle digits $7677$, $X_2 = 7677$, $R_2 = 0.7677$.

Drawback: the sequence may degenerate (collapse to zero or fall into a short cycle), so it is rarely used in practice.

Additive Congruential Method

A generator that produces the next number by adding previous terms (a lagged generalization of the linear congruential method). The recurrence is

for some lag $k$, where $m$ is the modulus. It requires $k$ seed values $X_0, X_1, \dots, X_{k-1}$. The corresponding uniform numbers are $R_i = X_i / m$.

Example ($k=2$, i.e. Fibonacci-type, $m = 10$, seeds $X_0=3, X_1=5$):

• $X_2 = (5+3)\bmod 10 = 8$
• $X_3 = (8+5)\bmod 10 = 3$
• $X_4 = (3+8)\bmod 10 = 1$, and so on, giving $R_i = X_i/10$.

Additive (lagged-Fibonacci) generators can produce very long periods, which makes them useful for large simulations.