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

Basic Queuing System

A queuing system describes the behaviour of customers (entities) arriving at a service facility, possibly waiting in a queue, receiving service, and then departing.

Characteristics / Structure

1. Arrival (input) process — how customers arrive, described by the inter-arrival time distribution (e.g. Poisson arrivals with rate $\lambda$).
2. Queue (waiting line) — the buffer where customers wait. Characterised by capacity (finite/infinite) and population (finite/infinite).
3. Queue discipline — order of service: FIFO, LIFO, SIRO, or priority.
4. Service mechanism — number of servers $c$ and the service-time distribution (e.g. exponential with rate $\mu$).
5. Departure — served customers leave the system.

Structure (in words): Arrivals → Queue → Server(s) → Departures.

Single-Server M/M/1 System

For M/M/1: Poisson arrivals (rate $\lambda$), exponential service (rate $\mu$), one server, infinite queue, FIFO.

Let the traffic intensity (utilization) be:

Performance measures:

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

Example: If $\lambda = 4$/hr and $\mu = 6$/hr, then $\rho = 0.667$, $L = 2$ customers, $L_q = 1.33$, $W = 0.5$ hr, $W_q = 0.333$ hr.

Monte Carlo Simulation

Monte Carlo simulation is a numerical technique that uses repeated random sampling to estimate the value of an unknown quantity (often an integral, probability, or expected value). It is especially useful for problems that are deterministic but hard to solve analytically.

General Steps

1. Define a domain of possible inputs.
2. Generate random inputs from a probability distribution over the domain.
3. Perform a deterministic computation on the inputs.
4. Aggregate the results (average / count successes).
5. The estimate improves as the number of samples $N \to \infty$ (error decreases as $1/\sqrt{N}$).

Estimating $\pi$

Consider a quarter circle of radius 1 inscribed in the unit square $[0,1]\times[0,1]$. The area of the quarter circle is $\pi/4$ and the area of the square is 1.

If we throw $N$ random points uniformly in the square and count $M$ points that fall inside the circle (i.e. $x^2 + y^2 \le 1$), then:

Algorithm:

import random
M = 0
N = 1000000
for _ in range(N):
    x = random.random()   # uniform in [0,1]
    y = random.random()
    if x*x + y*y <= 1.0:
        M += 1
pi_estimate = 4.0 * M / N
print(pi_estimate)        # ~3.1416 for large N

For example, if $N = 1000$ and $M = 785$, then $\pi \approx 4 \times 785/1000 = 3.14$. Larger $N$ gives a more accurate estimate.

True vs Pseudo-Random Numbers

Pseudo-random numbers are preferred in simulation because they are fast and reproducible (essential for debugging and comparing experiments), even though they are not truly random.

Linear Congruential Method (LCG)

The LCG generates a sequence using the recurrence:

where $X_0$ = seed, $a$ = multiplier, $c$ = increment, $m$ = modulus. Random numbers in $[0,1)$ are obtained as $R_n = X_n/m$.

• If $c = 0$ it is a multiplicative LCG; if $c \ne 0$, a mixed LCG.
• Good parameters give a full period of $m$.

Example

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

Sequence: $7, 6, 1, 8, 11, \dots$; normalized: $R = 6/16=0.375,\ 1/16=0.0625,\ 8/16=0.5,\dots$

Random numbers used in simulation must satisfy two statistical properties:

1. Uniformity: The numbers should be uniformly distributed over the interval $[0,1)$. If the interval is divided into $n$ equal sub-intervals, each sub-interval should contain (on average) the same fraction $1/n$ of the numbers. Formally, for $R \sim U(0,1)$ the pdf is $f(x)=1$ for $0\le x<1$, giving mean $1/2$ and variance $1/12$. Uniformity is tested using the frequency (chi-square / Kolmogorov–Smirnov) test.

2. Independence: Each generated number must be statistically independent of the others — the value of one number should give no information about the next, and there should be no correlation or pattern in the sequence. Independence is checked using autocorrelation, runs, and gap tests.

Together, uniformity and independence ensure the numbers behave like a genuine i.i.d. $U(0,1)$ sample, which is the foundation for generating other random variates in simulation.

Inverse Transform Technique (Exponential Distribution)

The inverse transform method generates a random variate $X$ with cdf $F(x)$ from a uniform random number $R\sim U(0,1)$ using $X = F^{-1}(R)$.

Derivation for Exponential

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

Step 1 — Set $F(X) = R$:

Step 2 — Solve for $X$:

Since $(1-R)$ is also $U(0,1)$, this is commonly simplified to:

Example

If $\lambda = 2$ and $R = 0.25$:

Repeating with different $R$ values yields exponential inter-arrival/service times for simulation.

Kendall's Notation

Kendall's notation describes a queuing system in the compact form:

where:

• A — inter-arrival time distribution
• B — service time distribution
• c — number of parallel servers
• K — system capacity (max customers in system; default $\infty$)
• N — calling population size (default $\infty$)
• D — queue discipline (default FIFO)

The last three are often omitted, giving the short form $A/B/c$.

Common symbols for A and B:

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

Examples

• M/M/1 — Poisson arrivals, exponential service, single server, infinite capacity, FIFO.
• M/M/c — Poisson arrivals, exponential service, $c$ servers (e.g. a bank with $c$ tellers).
• M/D/1 — Poisson arrivals, constant (deterministic) service, single server (e.g. an automated car wash).
• M/M/1/K — single server with finite capacity $K$.
• G/G/1 — general arrival and service distributions, one server.

Simulation Clock

A simulation clock is a variable that holds the current value of simulated (virtual) time in a discrete-event simulation. It does not correspond to real wall-clock time; it advances according to the events of the model and is used to schedule and order events.

Time-Advance Mechanisms

Summary: In fixed-increment, the clock ticks by equal intervals $\Delta t$ regardless of events; in next-event, the clock advances to the timestamp of the most imminent scheduled event, making it more efficient and accurate for discrete-event simulation.

Markov Chains

A Markov chain is a stochastic process $\{X_t\}$ over a set of states that satisfies the Markov (memoryless) property: the probability of the next state depends only on the current state, not on the history of past states.

The $p_{ij}$ form the transition probability matrix $P$, where each row sums to 1. The state distribution evolves as $\pi^{(t+1)} = \pi^{(t)}P$, and a steady-state distribution $\pi$ satisfies $\pi = \pi P$.

Application in Simulation

Markov chains model systems whose future depends only on the present state — e.g. weather, machine up/down status, queue lengths, inventory levels, web-page navigation. In simulation, the next state is generated by sampling a uniform random number and selecting the state according to the cumulative transition probabilities of the current row.

Example (Weather)

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

If today is Sunny, then $P(\text{tomorrow Sunny})=0.8$, $P(\text{Rainy})=0.2$. Starting Sunny, after one step the distribution is $(0.8, 0.2)$; iterating $\pi=\pi P$ converges to the steady-state $\pi \approx (0.667, 0.333)$, i.e. in the long run about 2/3 of days are sunny.

Physical vs Mathematical Models

Physical model: A tangible, scaled-down (or scaled-up) physical representation of a system. It looks like the real system and its behaviour is studied directly by observation or experiment.

• Static physical model: scale model of a building, a globe, an architectural mock-up.
• Dynamic physical model: wind-tunnel model of an aircraft, a hydraulic analog of a water-distribution network.

Mathematical model: An abstract representation of the system using symbols, equations, and logical/quantitative relationships among variables. The system is studied by solving or simulating these equations rather than by physical observation.

• Static mathematical model: a regression equation, Monte Carlo estimate of an integral.
• Dynamic mathematical model: differential/difference equations describing population growth, M/M/1 queue formulas.

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

Mid-Square Method

Proposed by von Neumann, this method generates pseudo-random numbers by repeatedly squaring a number and extracting the middle digits.

Steps:

1. Choose an $n$-digit seed $X_0$.
2. Square it: $X_0^2$ (pad with leading zeros to $2n$ digits).
3. Take the middle $n$ digits as the next number $X_1$.
4. Repeat. Normalize by dividing by $10^n$ to get $R$ in $[0,1)$.

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

Drawbacks: short period; may degenerate to zero or get stuck in a cycle.

Additive Congruential Method

This generates the next number by adding previous terms modulo $m$ instead of multiplying. A general form uses the last $k$ values:

The simplest two-term (Fibonacci-type) version is:

Example: $m = 100$, seeds $X_0=23,\ X_1=47$:

Normalized: $R_2 = 0.70,\ R_3 = 0.17,\ \dots$ It is fast and can achieve long periods but has weaker statistical independence.

In simulation a system is described in terms of the following components:

• Entity: An object of interest in the system whose behaviour is being studied. Example: a customer in a bank, a machine in a factory.

• Attribute: A property or characteristic of an entity. Example: a customer's arrival time or priority; a machine's status (busy/idle).

• Activity: A time-consuming process or operation that changes the state of the system over a period. Example: serving a customer, machining a part.

• Event: An instantaneous occurrence that may change the state of the system. Example: arrival of a customer, completion of a service. (Events are classified as endogenous — internal — or exogenous — from the environment.)

• State of the system: The collection of variables (state variables) needed to describe the system at any instant for the purpose of study. Example: the number of customers in the queue and whether the server is busy or idle.

Together these define the model: entities possessing attributes engage in activities, bounded by events, which together determine the system state over time.

Importance of Output Analysis

Simulation output is random (it depends on the random numbers used), so a single run gives only one sample observation of system performance. Output analysis applies statistical methods to simulation results so that valid conclusions can be drawn. Its importance:

• Estimates performance measures (e.g. mean waiting time) with confidence intervals, not just point values.
• Quantifies the statistical error / variability of estimates.
• Determines the required number of runs / run length for desired precision.
• Enables fair comparison of alternative system designs.
• Avoids misleading conclusions from a single, noisy run.

Terminating vs Steady-State Simulation

Summary: A terminating simulation has a well-defined event that ends each run, and we analyze a fixed interval; a steady-state simulation studies the long-run equilibrium behaviour and requires handling the initial transient via a warm-up period.