Till KTH:s startsida Till KTH:s startsida

PhD students

Expected schedule: 

Meeting on Wednesdays after EP2200 class (week 5 excluded). Most probably we can stay in the same classroom. If not, we come up the the LCN offices in the Q building. The seminars will be ca. one hour long.

Project performed during the second part and after the course. Project ideas presented on seminars 4,5,6, based on maturity.

Material: see link below (for logged in students)

Missed classes: if you missed a class, you need to solve a small related problem. The problems are not complex, but require the reading and understanding of the material. See the questions on the bottom of the page. You can submit the answer together with your project.

Seminar style:

PhD students present on white board. Students schedule:

  1. Sladjana
  2. Andreas
  3. Yue
  4. Vahan 
  5. Xiaolin 
  6. Viktoria

Topics and references:

Gross and Harris, Fundamentals of Queuing Theory. PDF is available through KTH (e.g., go to www.lib.kth.se, and write Gross and Harris in the search field...)

1. Poisson process, in one and two dimensions
Gross and Harris 1.7-1.8
In addition, let us read some sections on spatial Poisson Process and percolation theory here:
Haenggi, M.; Andrews, J.G.; Baccelli, F.; Dousse, O.; Franceschetti, M., "Stochastic geometry and random graphs for the analysis and design of wireless networks," IEEE Journal on Selected Areas in Communications, , vol.27, no.7, pp.1029,1046, September 2009
http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5226957
II.A, IV.C are sections that are mostly interesting for us, but the rest is nice too.

2. Analysis of both discrete and continuous time MCs in transient state. Ergodicity and stability, proof of conditions for these.

We read Chapter 1.9 in Gross and Harris. Unfortunately it does not prove the "main theorem" on the existence of stationer solution, that is, Theorem 1.1 a,b,c on page 38. Neither the two other books I looked at. So, if you have time, please check whether you find a proof. I will keep searching too.

Also, please look at the imbedded MC with equation (1.31).  Can we derive the stability condition of the continuous time birth-death process from this?

3. Use of generating function
M/M/1 Gross and Harris, 2.2.2
Bulk arrival: G-H 3.1
Erlang-r example: G-H 3.3.3 (also phase type?)

4. M/G/1 transform forms:
G-H 5.1.2-5.1.5 (seems to me, maybe some other parts are needed too...)

5. Queuing networks, and specifically product form solutions of large markov chains.
Thomas G. Robertazzi​, Computer networks and systems : queuing theory and performance evaluation, chapters 3.3 and 3.4 (lots of examples, you do not need to go through all of them)

6. Advanced topics: Large deviation theory, Palm calculus - this may be changed given preferences Large deviation: Lewis, An Introduction... (attached): up to page 9 and page 16, Palm theory: Le Boudec, Performance evaluation of computer and communication systems: chapters 7.1, 7.2 (the first two Palm calculus chapters in my first edition) - needs updated material for Large deviation, and more focused selection for Palm.

Missed classes problems 

1. Prove the following two properties of the Poisson distribution:

  • Given that there are k arrivals in time period T, the arrival times are uniformly distributed in interval T (proof is in the Gross and Harris notes).
  • The limit of a binomial distribution is Poisson. Specifically, consider the limit of the binomial distribution as n-> inf, and np = constant (lambda)

2. Consider the discrete time Markov chain with two states and state transition probabilities {{1/2,1/2}{3/4,1/4}}. Show that the resulting stochastic process is ergodic (see section 1.9.6 in G-H). Calculate the state probabilities in steady state.

3. Consider the z-transform of the state probability distribution under bulk arrivals (section 3.1, below equation 3.3). Consider the specific case, where there is exactly 1 customer arriving in each “bulk”, and derive the state probabilities, through the given z-transform form.

4. Give the exact expressions for k_i, the state transition probability values of the imbedded discrete time Markov chain, when the service times are deterministic. Denote the arrival intensity with lambda, the service time with x.