Exam Questions

Question 1

How to argue that something is a Markov-chain?

Answer 1

Claim that the events that trigger a change of state are scheduled to take place after a random time with an exponential distribution.

Question 2

How to the the transistion rates Q?

Answer 2

Usually you can set the λ for all increasing (by 1), iμ for decreasing (by 1), -λ-iμ for i = j, set -λ for i =j = 0, -iμ for i = j = n.

For the rest set 0.

Question 3

How to explain the q_ij for non trivial values?

Answer 3

First describe the distribution of increasing, and the distribution of decreasing. Then explain that the min of the 2 is just the two distributions added together (in an exponential distribution).

Explain that the probability of arrival is the values in the arrival distribution divided by the values in the total distribution. (Same for the leaver).

Then by multiplying the probability and the total distribution you get the transition rates.

Question 4

How to reason that a discrete time Markov chain is ergodic?

Answer 4

Argue: “We can reach any state from any other state, and it is finite, and aperiodic, thus it is positive recurrent i.e. ergodic.”

Question 5

What is PASTA?

Answer 5

According to PASTA the chance that you arrive to a system in state 𝛼_i = 𝜋_i. Thus this means that the chance that you arrive in that state is equal to the long run probability of being in that state.

Question 6

How to find the number of customers that are lost in a limited Markov-chain?

Answer 6

You can use PASTA to find the probability that a customer arrives when in state 𝛼_n=𝜋_n (i.e. you just need to find the stationary distribution).

Question 7

What formula states that we can find a long run average?

Answer 7

Note: you can leave out the |X(0) = j part.

Question 8

How to find the limiting distribution (using Q)?

Answer 8

𝜋Q = 0

Question 9

What is the Markov instantaneous reward theorem?

Answer 9

Question 10

If you have two different Poisson distributions what can you do with them?

Answer 10

You can easily add them together in one Poisson distribution.

Question 11

How to calculate time probability that time to first is longer than t? (Using Poisson)

Answer 11

Question 12

How to find the expectation of two different exponential distributions which are Poisson distributed?

Answer 12

Question 13

How to show the memoryless property of the Poisson distribution?

Answer 13

Example:

Question 14

What is the PMS function of the Poisson distribution?

Answer 14

Question 15

How to find probability of needing n steps until in absorbing state?

Answer 15

We can just use (Pⁿ)_0,k. Note: since it is absorbing you do not have to add a sum.

Question 16

What is often important to mention when using the Poisson distribution?

Answer 16

That it is memoryless.

Question 17

How to show that the stationary distribution exists in a Queueing system?

Answer 17

1. State that all states are communicating
2. Verify that λ < (c)μ

Question 18

When stating the state space S, what is important to define for a continuous Markov chain, and how to define it in a distrete time Markov chain?

Answer 18

X_i(t) : meaning of it,

discrete: X_n, n = 0, 1, 2, …

Question 19

In the case of multiple exponential processes, what is the transition rate?

Answer 19

nμ, where n is the number of exponential processes.

Question 20

How to reason all the transition rates q_ij?

Answer 20

Question 21

If we combine two exponential distributions, what kind of probability distribution do we get?

Answer 21

a hyperexponential distribution

Question 22

What are the two Markov reward theorems? What are they based on?

Answer 22

• Markov Instanteonous Reward Theorem
• Markov Jump Reward Theorem

Question 23

What is the Markov Jump Reward formula?

Answer 23