Markov Chains, Simulation Tools & GPSS Basics

TAKEAWAYS:

• Markov chains model systems where future states depend only on the current state (memoryless property).
• Steady-state probabilities solve for long-term behavior using balance equations or matrix methods.
• GPSS simulation tools use blocks like MARK (mark time) and TABULATE (collect statistics) to model discrete events.
• Model validation ensures accuracy via face validity, animation, and statistical tests.
• Hybrid simulations combine discrete-event and continuous models for complex systems.
• Real-world applications include queueing systems (e.g., Ncell call centers), inventory management (e.g., Daraz warehouses), and financial risk modeling (e.g., NEPSE stock trends).

---

Markov Chains: Definition and Core Concepts

A Markov chain is a stochastic process that models systems where the next state depends only on the current state (memoryless property). It consists of:

• States (S): Distinct conditions of the system (e.g., "busy," "idle").
• Transition probabilities (P): Probability of moving from one state to another in a time step.
• Transition matrix (P): A square matrix where $P_{ij}$ = probability of moving from state $i$ to state $j$.

Visual: State Transition Diagram

Example: A single-server queue (e.g., Ncell customer service):

• States: 0 customers, 1 customer, 2 customers, etc.
• Transition: If a call arrives (probability $\lambda \Delta t$) and the server is idle, move to state 1.

---

Steady-State Probabilities

For large $t$, the system reaches a steady state where state probabilities $\pi =[{\pi }_0,{\pi }_1,{\pi }_2,...]$ satisfy: $$\pi =\pi P$$ with $\sum {\pi }_i=1$.

Worked Example: Coffee Shop Barista (Exam-Style)

A barista serves customers at 2.5 minutes/serving. Customers arrive every 3 minutes (Poisson). Model as a 2-state Markov chain:

• States: Busy (B), Idle (I).
• Transition rates:
  • $P_{BI}=1$ (always leaves busy after service).
  • $P_{IB}=\lambda \times \text{service time}=\frac{1}{3}\times 2.5=0.833$.
  • $P_{II}=1-0.833=0.167$.

Balance equations: $${\pi }_B={\pi }_I\times 0.833,{\pi }_I={\pi }_B+{\pi }_I\times 0.167$$ Solve: $${\pi }_B=0.455,{\pi }_I=0.545$$ Interpretation: 54.5% of time the barista is idle.

---

Applications of Markov Chains

Real Picture: Call center queueing system

---

Simulation Tools: GPSS Basics

GPSS (General Purpose Simulation System) uses blocks to model discrete events:

• MARK: Advances simulation clock by a specified time.
• TABULATE: Collects statistics (e.g., time spent in a state).

Example: Coffee Shop Simulation (GPSS Pseudocode)

GENERATE 3, 0.5   // Customers arrive every 3 ± 0.5 mins
QUEUE           // Join queue
SEIZE BARISTA    // Grab barista
DELAY 2.5        // Serve for 2.5 mins
RELEASE BARISTA
TERMINATE 1      // End simulation
TABULATE BARISTA // Record idle/busy time

---

Model Validation and Calibration

1. Face Validity: Does the model match real-world logic?
2. Animation: Visualize the model (e.g., customer flow in Pathao).
3. Statistical Tests: Compare output (e.g., queue lengths) to real data.

Iterative Calibration:

---

Hybrid Simulation

Combines discrete-event (e.g., customer arrivals) and continuous (e.g., temperature changes) models. Example: NTC traffic simulation:

• Discrete: Cars arrive at intersections.
• Continuous: Traffic flow speed varies smoothly.

---

In the Real World

1. Ncell Call Centers:

   • Markov chains model call arrival/departure probabilities to optimize agent allocation.
   • Example: If calls arrive at $\lambda =10$ calls/hour and agents handle $\mu =12$ calls/hour, the steady-state probability of 0 calls is ${\pi }_0=1-\lambda /\mu =0.167$.

2. Daraz Inventory:

   • Stock levels transition between "high," "medium," and "low" based on order probabilities.
   • Example: If demand is Poisson with $\lambda =5$ orders/day and restocking takes 2 days, the transition matrix predicts stockout risks.

3. Khalti Payment Routing:

   • Markov chains route transactions between servers based on current load (e.g., "Server A" → "Server B" if A is busy).

---

Exam Tip

• Markov Chains: Always define states and transitions clearly. For steady-state, use balance equations or matrix inversion.
• GPSS: Focus on MARK (time advance) and TABULATE (statistics). Draw a flowchart for the simulation logic.
• Validation: Mention face validity, animation, and statistical tests in your answer.
• Hybrid Simulation: Contrast discrete (events) vs. continuous (time) components with a real example (e.g., traffic + weather).

---

Key Formula Summary: