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

Monte Carlo Simulation

Monte Carlo simulation is a numerical technique that uses repeated random sampling to obtain approximate solutions to problems that may be deterministic in nature but are difficult or impossible to solve analytically. By generating large numbers of random samples and observing the fraction that satisfy some condition, we estimate quantities such as areas, integrals, or probabilities.

Key characteristics:

• Relies on random numbers drawn from a known distribution.
• Accuracy improves as the number of trials $N$ increases (error decreases roughly as $1/\sqrt{N}$).
• Used for integration, risk analysis, queuing, and physical-system modelling.

Simple example: To estimate $\int_0^1 f(x)\,dx$, sample $x_i$ uniformly in $[0,1]$ and average: $\int_0^1 f(x)\,dx \approx \frac{1}{N}\sum_{i=1}^{N} f(x_i)$.

Estimating $\pi$ using Monte Carlo

Consider a quarter circle of radius 1 inscribed in a unit square $[0,1]\times[0,1]$.

• Area of unit square $= 1$.
• Area of quarter circle $= \dfrac{\pi r^2}{4} = \dfrac{\pi}{4}$.

If we throw points uniformly at random into the square, the probability that a point falls inside the quarter circle equals the ratio of areas:

So if $M$ out of $N$ random points satisfy $x^2 + y^2 \le 1$, then

Algorithm:

M = 0
for i = 1 to N:
    x = random(0,1)        // uniform
    y = random(0,1)
    if (x*x + y*y <= 1):
        M = M + 1
pi_estimate = 4.0 * M / N

Illustrative result: with $N = 1000$ points, suppose $M = 785$ fall inside the circle. Then $\pi \approx 4 \times 785/1000 = 3.14$. As $N \to \infty$, the estimate converges to $3.14159\ldots$

True vs Pseudo-Random Numbers

Pseudo-random numbers only appear random; they pass statistical tests of randomness (uniformity and independence) but are fully determined by the initial seed.

Linear Congruential Method (LCG)

The LCG generates a sequence using the recurrence:

where:

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

Normalized random numbers in $[0,1)$ are obtained as $R_n = X_n / m$.

• If $c = 0$ it is a multiplicative congruential generator.
• If $c \ne 0$ it is a mixed congruential generator.

The maximum possible period is $m$; achieving full period requires conditions (Hull–Dobell theorem) such as $\gcd(c,m)=1$.

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

Sequence: $7, 6, 1, 8, 11, \ldots$; normalized: $0.4375, 0.375, 0.0625, 0.5, 0.6875, \ldots$

Discrete-Event Simulation (DES)

Discrete-event simulation models a system as a sequence of events occurring at discrete points in time, where the system state changes only at event instants (e.g., a customer arrival, a service completion). Between consecutive events the state remains unchanged, so the simulation clock can jump from one event time to the next rather than advancing continuously.

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) — a list of future events ordered by their scheduled time.
• Statistical counters — accumulate output data (waiting time, utilization).
• Random number generators — produce inter-arrival and service times.

Event-Scheduling / Time-Advance Algorithm

The next-event time-advance mechanism repeatedly:

1. Finds the imminent event (the one with the smallest scheduled time) in the Future Event List.
2. Advances the clock to that event's time.
3. Executes the event routine, updating state, counters, and scheduling new future events.
4. Repeats until a stopping condition is met.

Flowchart (described in steps):

        +------------------------------+
        |  Initialize: clock=0, state, |
        |  schedule first arrival      |
        +---------------+--------------+
                        v
        +------------------------------+
        |  Is event list empty / stop  |---- yes --> [ Generate report / End ]
        |  condition reached?          |
        +---------------+--------------+
                        | no
                        v
        +------------------------------+
        |  Remove imminent event;      |
        |  advance clock to its time   |
        +---------------+--------------+
                        v
        +------------------------------+
        |  Execute event routine:      |
        |  - update system state       |
        |  - update statistics         |
        |  - schedule future events    |
        +---------------+--------------+
                        |
                        +----> (loop back to stop check)

This cycle of find imminent event → advance clock → process event → schedule new events drives the entire discrete-event simulation.

Kendall's Notation

Kendall's notation is a standard shorthand for describing and classifying a queuing system, written as:

Common distribution codes for $A$ and $B$: M = Markovian/exponential (Poisson arrivals), D = Deterministic, G = General, $E_k$ = Erlang.

Examples:

• M/M/1 — Poisson arrivals, exponential service, single server, infinite capacity, FCFS. The classic single-server queue.
• M/M/c — Poisson arrivals, exponential service, $c$ servers (e.g., a bank with $c$ tellers).
• M/D/1 — Poisson arrivals, constant (deterministic) service time, one server (e.g., automated car wash).
• M/M/1/K — same as M/M/1 but limited capacity $K$ (finite waiting room).

Simulation Clock

A simulation clock is a variable that holds the current value of simulated time during a simulation run. It does not correspond to real (wall-clock) time; it advances according to the events being modelled and provides the time reference against which events are scheduled and statistics collected.

Fixed-Increment vs Next-Event Time Advance

Summary: Fixed-increment advances in uniform $\Delta t$ steps and is simple but can be inaccurate and inefficient; next-event advance moves the clock to each successive event time, giving exact timing and better efficiency, and is the standard mechanism for discrete-event simulation.

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 history of how it was reached. This is the memoryless (Markov) property:

The $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 steady-state distribution $\pi$ satisfies $\pi = \pi P$.

Application in simulation: Markov chains model systems whose future behaviour depends only on present state — weather, machine up/down status, inventory levels, queue lengths, web-page navigation. In simulation we generate the next state by sampling a random number and selecting the destination state according to the current row of $P$.

Example (weather model): States = {Sunny (S), Rainy (R)}.

If today is Sunny, then $P(\text{tomorrow Sunny}) = 0.8$, $P(\text{tomorrow Rainy}) = 0.2$. Solving $\pi = \pi P$ gives the long-run distribution $\pi_S = 2/3$, $\pi_R = 1/3$, i.e., about 67% sunny days in the long run.

Physical Models vs Mathematical Models

Physical model examples: a scaled aircraft tested in a wind tunnel, a globe representing the Earth, a hydraulic model of a river/dam, an architectural building model.

Mathematical model examples: Newton's law $F = ma$, the queuing relation $L = \lambda W$ (Little's Law), a system of differential equations describing population growth, or a probability model of customer arrivals. Mathematical models are the basis of computer simulation because they can be programmed and analysed numerically.

Mid-Square Method

Proposed by von Neumann, the mid-square method generates pseudo-random numbers as follows:

1. Start with an $n$-digit seed $X_0$.
2. Square it to get a $2n$-digit number (pad with leading zeros if needed).
3. Extract the middle $n$ digits — this is the next number $X_1$.
4. Repeat using $X_1$ as the new seed; normalize by dividing by $10^n$ for a value in $[0,1)$.

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

Drawback: can degenerate quickly (numbers may collapse to zero or fall into short cycles), so it is rarely used in practice.

Additive Congruential Method

The additive congruential method generates the next number by adding previous terms in the sequence rather than multiplying. A general form uses the recurrence:

It requires $k$ initial seed values $X_0, X_1, \ldots, X_{k-1}$. A common (lagged-Fibonacci) special case is:

Example: with $m = 100$ and seeds $X_0 = 57$, $X_1 = 34$:

It is fast and can produce very long periods, but the choice of lags and modulus must be made carefully for good statistical quality.

Basic Simulation Terminology

• Entity — An object of interest in the system whose behaviour we model. Entities may be dynamic (move through the system, e.g., a customer, a part on a conveyor) or permanent (resources, e.g., a server, a machine).

• Attribute — A property or characteristic of an entity. It distinguishes one entity from another and may hold a value. Example: a customer's arrival time, priority level, or account balance; a machine's speed.

• Activity — A duration of time of specified length during which something happens, representing a time-consuming process between two events. Example: the service of a customer (lasts a service time), or machining a part.

• Event — An instantaneous occurrence that may change the state of the system. It marks the start or end of an activity. Example: a customer arrival, a service completion, a machine breakdown.

• State of the system — The collection of state variables needed to describe the system at any instant relative to the objectives of the study. Example: the number of customers in the queue, whether the server is busy or idle, and the number waiting.

Relationship: Entities (with their attributes) engage in activities; activities are bounded by events; and the values of state variables together define the system state at any point in simulated time.

Importance of Output Analysis

Simulation outputs are random because they are driven by random number inputs; a single run gives only one sample observation. Output analysis is the statistical treatment of simulation results to draw valid, reliable conclusions. Its importance:

• Estimates performance measures (mean waiting time, utilization, throughput) with confidence intervals rather than single point values.
• Quantifies the variability/precision of estimates and determines the number of replications/run length needed.
• Avoids misleading conclusions from a single, possibly atypical, run.
• Enables valid comparison of alternative system designs.

Terminating vs Steady-State Simulation

Summary: A terminating simulation studies a system over a bounded interval ending in a defined event and is analysed by independent replications; a steady-state simulation studies long-run behaviour and must handle warm-up bias using methods such as batch means.

Poisson Distribution

The Poisson distribution is a discrete distribution that models the number of events occurring in a fixed interval of time when events happen independently at a constant average rate $\lambda$:

Its mean and variance both equal $\lambda$. In queuing it models the number of arrivals per unit time.

Exponential Distribution

The exponential distribution is a continuous distribution modelling the time between successive events (inter-arrival or service time) for a process with rate $\lambda$:

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

Role in Queuing Simulation

These two distributions are intimately linked: if arrivals occur as a Poisson process with rate $\lambda$ (number of arrivals in any interval is Poisson), then the inter-arrival times are exponentially distributed with mean $1/\lambda$. This pairing underlies the M/M/1 and M/M/c queuing models, where:

• Arrivals follow a Poisson process (the first M),
• Service times are exponential (the second M).

The memoryless property makes such systems analytically tractable (Markovian). In simulation, exponential inter-arrival and service times are generated by inverse transform: $t = -\frac{1}{\lambda}\ln(1 - R)$ where $R$ is a uniform random number in $[0,1)$.

General-Purpose Simulation Language (GPSS)

A general-purpose simulation language (GPSL) such as GPSS (General Purpose Simulation System) is a special-purpose programming language designed specifically for building discrete-event simulation models, especially queuing systems. Rather than coding clock management and event lists by hand, the modeller describes the system using high-level blocks.

Key features:

• Transaction-flow (process) orientation — Dynamic entities called transactions (e.g., customers, jobs) flow through a sequence of blocks that represent operations on them.
• Built-in block statements — Ready-made blocks such as GENERATE (create transactions), QUEUE/DEPART (collect queue statistics), SEIZE/RELEASE (capture/free a facility), ADVANCE (consume service time), and TERMINATE (remove transactions).
• Automatic simulation control — The language automatically maintains the simulation clock, the future event list, and time advance; the user need not program these.
• Built-in random number and distribution generators — Functions for uniform, exponential, and other distributions for arrivals and service.
• Automatic statistics collection — Queue lengths, waiting times, facility utilization, and throughput are gathered and reported automatically.
• Facilities, storages and queues — Predefined entities to model single-capacity servers (facilities), multi-capacity resources (storages), and waiting lines (queues).
• Standard output reports — Produces summary reports of performance measures at the end of a run.

Advantages: rapid model development, less coding effort, fewer programming errors, and reusable, readable models — at some cost in flexibility compared with a general-purpose language like C.