PhD student seminars
Seminar schedule
PhD students have weekly seminars of two hours. Students read the material in advance. One of the students leads the seminar and walks us through the theoretic results and derivations. The student leading seminar should understand the material well. There is no need to prepare presentation, we use the original reading material at the seminar. Prepare missing proofs or examples for yourself, if you feel they help!
Time: Wednesdays 2pm (that is, one our before the "normal" class on Wednesdays)
Location: Teknikringen 33, floor 3, room 2317, Laila Ohlgren (one of the rooms between the entrance and the lunch area)
Zoom link: https://kth-se.zoom.us/j/64879224471 Links to an external site.(but please try to join physically!)
Seminar schedule
Jan 24: A1. Poisson Process: Noè
Jan 31: A2. Markov chains: Satya
Feb 7: A3. Steady state via generating function: Zhenyu
Feb 14: A4.Non-Markovian queuing systems; Sangwon
Feb 21: A5. Outlook: Optimal control of queues: Adam
Feb 28: A6. Outlook: Markov decision process: Remi
+ one more seminar about the projects
Literature
(G-H) Donald Gross, John F Shortle, James M Thompson, Carl M Harris, Fundamentals of Queueing Theory, 2013, 4th edition.
Available for KTH through KTH Lib, or maybe even directly at http://onlinelibrary.wiley.com.focus.lib.kth.se/book/10.1002/9781118625651
(Boudec) Jean-Yves Le Boudec, Performance Evaluation of Computer and Communication Systems, 2010, available at: http://perfeval.epfl.ch/ Links to an external site.
Links to an external site.(Lakatos) László Lakatos, László Szeidl, Miklós Telek, Introduction to Queueing Systems with Telecommunication Applications, 2013, available at https://link.springer.com/book/10.1007/978-3-030-15142-3 Links to an external site.
(Neely) M. J. Neely. Stochastic Network Optimization with Application to Communication and Queueing Systems, Morgan & Claypool, 2010. https://link.springer.com/book/10.1007/978-3-031-79995-2 Links to an external site.
(Tijms) H. Tijms, Stochastic Modelling and Analysis - A Computational Approach, Wiley, 1986, pdf Download pdf
Presentation of project ideas
Project ideas will be presented on the last seminars. You have 15 minutes to present the project idea at the whiteboard, including discussion. Introduce the area, and then the specific problem you will address. Talk about the solution methodology you would like to follow, and the results you expect to get.
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 should submit the answers by the date of the final exam.
Topics and references:
1. Poisson process, in one and two dimensions
We read Gross and Harris 1.7-1.8
In addition, let us read some sections on spatial Poisson Point Process (PPP) 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
Sections II-III are sections that are mostly interesting for us, but the rest is nice too. We only review some key properties of PPP without proof.
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 proofs are missing. For proofs check Lakatos, Chapter 3.2. For additional missing proofs, look for sources.
3. Solving Markov chains with the help of generating functions - how to solve the system of balance equations for chains more complicated that a B-D process?
G-H 2.2.2, 3.3.1-3.3.3. Feb. 6. OOOps, it should have included 3.1 as well!
4. Non-Markovian queuing systems, M/G/1 transform forms:
G-H 5.1.2-5.1.5 (seems to me, maybe some other parts are needed too...)
5. Optimal control of queues, Lyapunov optimization.
Neely, Chapter 1 Introduction 1.1-1.3, Chapter 3 Dynamic Scheduling example, 3.1.
6. Markov decision process, some historical results: definition of MDP, policy iteration, convergence of policy iteration on finite state space
Tijms, Chaper 6, 6.0-6.4, 6.7 policy iteration parts
Missed classes problems (added when needed)
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. xxx
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.