Slides

Question 1

What is a feature of the Markov-chains regarding the probability to switching to another node?

Answer 1

Only the current node matters, thus P(X_n+1 = i_n+1 | X_n = I_n, X_n-1 = i_n-1,…) = P(X_n+1 = i_n+1 | X_n = I_n)

Question 2

What are the Chapman-Kolomonogorov equations? And what do they mean?

Answer 2

p_ij^(n+m) = Σ_{k in S} p_ik⁽ⁿ⁾p_kj^(m) i, j in S.

It means that the probability of going from i to j in n + m steps is that probability. It is the same as matrix multiplication and thus it means we can just use matrix multiplication.

Question 3

What are the three states a Markov chain can be in?

Answer 3

1. Recurrent
2. Transient
3. Absorbing

Question 4

What is the definition of a transient Markov chain?

Answer 4

Question 5

What is the definition of a recurring Markov-chain?

Answer 5

Question 6

What is the definition of an absorbing Markov-chain?

Answer 6

Question 7

What are the two ways you can calculate the long run probabilities 𝜋?

Answer 7

1. Power method: compute the square of the matrix of transition probabilities until all rows are about the same. (i.e. first calculate P², then (P²)², etc.)
2. Solve a system: solve the following system of linear equations 𝜋 = 𝜋P and Σ_{i in {1, …, n}}𝜋_i = 1.

Question 8

How to calculate the Mean Return Time?

Answer 8

You can easily calculate the MRT using μ_jj = 1/𝜋_jj

Question 9

What is the definition of the First Return Time (or recurrence time)?

Answer 9

Question 10

What is the Mean First Passage Time?

Answer 10

It is the average first time the chain goes through a node.

Question 11

How to compute the Mean First Passage Time?

Answer 11

Define N_j = P but without the i^th column AND row,

then solve the following set of linear equations:

μ_j = [I - N_j]^-11

Question 12

What is the definition of the time until the Markov chain is absorbed?

Answer 12

Question 13

How to find the probability of absorption?

Answer 13

Solve the following set of Linear Equations.

Question 14

How to get the mean time until absorption?

Answer 14

Solve the following system of linear equations

Question 15

How can we do the calculations for probability of absorption and mean time until absorption using matrix calculations?

Answer 15

Question 16

Why can we define a single matrix Q that is sufficient for all P(t)?

Answer 16

Question 17

How to find the transition matrix Q?

Answer 17

First of all note that the row sum of every transition Q should be 0.

We (usually) have that the diagonal of the matrix contains the negative of the sum of the rest of the entire row.

Formally we have (image).

We set 𝝂_n to be the value in the Exp(…) distribution. We set q_ij as in the value that is in the Poisson(..) or Exp(..) distribution of the changes.

Question 18

What does a Queue consist of?

Answer 18

• i.i.d. arrivals (from either finite or infinite populations)
• a waiting room (finite, infinite or even zero)
• i.i.d. service requiests
• servers (at least 1, finite or infinite)

The Queue has an order of service.

Question 19

What are the most important examples of order of service?

Answer 19

• FCFS (First Come First Served)
• LCFS (Last Come First Served)
• ROS (Random Order of Service)
• PS (Processor Sharing)

Question 20

What are some of the most important properties of the exponential distribution?

Answer 20

1. It is memoryless (i.e. P(X> t + s | X > t) = P(X > s))
2. The minimum of mutilple exponential distributed variables is exponentially distributed:
   
   • x_j ~ Exp(μ_j)
   • M = min(x₁, x₂, …), then M ~ Exp(μ_* = Σ_{j in {1, 2, …}}μ_j)
   • P(M = X_n) = μ_n/μ_*

Question 21

When is a Markov chain ergodic?

Answer 21

A Markov chain is ergodic if there is a number N such that any state can be reached from any other state in any number of steps less or equal to a number N

Question 22

How can the limiting distribution (p) be found (in a basic single server B&D model)?

Answer 22

Question 23

What are some of the intresting statistics of queues?

Answer 23

Question 24

How to calculate the total customers in the system in steady state (L_s)?

Answer 24

Question 25

How to compute the expected number of waiting customers?

Answer 25

Question 26

How to compute the waiting time (in line waiting and total)?

Answer 26

Using Little’s Law:

Question 27

How to compute the number of busy server and utilization rate?

Answer 27

Question 28

How can Queue charactaristics be written?

Answer 28

Question 29

In a M/M/1 model how do we get p_n?

Answer 29

Question 30

What is meant by PASTA?

Answer 30

Question 31

How do we get p_n in a M/M/c queue?

Answer 31

Question 32

What are the queue statistics in a M/M/1 model?

Answer 32

Question 33

What are the queue statistics for a M/M/c model?

Answer 33

Question 34

How to get the probability of delay in a M/M/c queue?

Answer 34

(see the Erlang-C formula, rest is included for clarity).

Question 35

How is the steady-state and are the performance measures calculated for a M/M/c/N queue?

Answer 35

They are calculated numerically by a computer. We can compute p_n (see image). Normalization means to sum it and then infer the p₀ since the total probability is 1.

Question 36

How is p_n calculated in a M/M/∞? And the performance measures?

Answer 36

Question 37

How do you calculate p_n for a M/M/c/c queue?

Answer 37

Question 38

How co calculate the loss probability in a M/M/c/c queue?

Answer 38

(Erlang-B formula, rest added for context)

Question 39

What is a Finite Source Queing Model? How is p_n found in a Finite Source Queueing Model?

Answer 39

(see image)

p_n is found using a numerical program (using the recursion p_n+1 = p_n λ_n/μ_n+1

Question 40

How to calculate p_n in a M/G/1 queue?

Answer 40

Question 41

What is the Open Jackson Network Model? How do we calculate the important statistics?

Answer 41