This course will be held in English.

We will study Markovian models and Queueing Systems to analyse the performance and reliability of computing systems. Examples can be many technical, real-life systems.

Material of this course is the book:

William Stewart. Probability, Markov Chains, Queues and Simulation. Princeton University Press 2009. The pdf file is in the resources of this course.

Dieser Kurs wird auf englisch gehalten.

Wir beschäftigen uns mit den grundlegenden stochastischen Modellen, die zur Untersuchung der Leistung von Computersystemen häufig benutzt werden. Markov modelle und Warteschlangen werden gerne für die Untersuchung dynamischer Systeme verwendet, z.B. Computer Hardware, Kommunicationsprotokolle, biologische Systeme, Epidemien, Verkehr und digitale Währungen.  Wir werden uns einen raschen Überblick verschaffen.  Betrachtete Themen sind der Geburts- und Todesprozess, der Poissonprozess, verallgemeinerte Markov und semi-Markov prozesse sowie deren Lösungsmethoden. Soweit die Zeit es erlaubt werden wir auch die Hintergründe der diskreten Ereignissimulation ansehen.

Literatur

William Stewart. Probability, Markov Chains, Queues and Simulation. Princeton University Press 2009.

Organisation

There will be discussion sessions (flipped classroom) every Tuesday, the first will be on Tuesday, 13.04.2021 at 10:15 at this meeting link:

https://fu-berlin.webex.com/fu-berlin-en/j.php?MTID=mf0d1b65761c19633fd65250e1add8729

Meeting number: 121 106 0043

Password: PRtCimMX637

On Thursday, 15.4.2021 from 12:15-13:45 there will be an extra Q&A session: https://fu-berlin.webex.com/meet/k.wolter

The tutorials will start on Thursday, 22.04.2021 and the meeting link is here: https://fu-berlin.webex.com/fu-berlin-en/j.php?MTID=m385d511acbce32de94f647431aec932d

Meeting number: 121 165 7605

Password: jP7eSRR75pM

Lecture Materials:

All videos can be found in the nextcloud: https://nextcloud.imp.fu-berlin.de/index.php/s/6iao5DXJj87yXTn and in the vbrick server https://fu-berlin.eu.vbrickrev.com/#/ (search for Markov Chains). The following plan may still slightly change.

Week 1: (12.04.-16.04.2021) Introduction  (slides in resources),

Lecture 1: Probability theory primer part 1 (video: https://fu-berlin.eu.vbrickrev.com/sharevideo/605ffac7-3de7-484f-a5dc-7500fd4cf58d or  https://nextcloud.imp.fu-berlin.de/index.php/s/WFtGDZEgQYDxcPj, lecture notes in resources).

Lecture 2: Probability theory primer part 2, Moments, Generating Functions, Minimum and Maximum of RV (video1:  https://fu-berlin.eu.vbrickrev.com/sharevideo/0e089345-ba47-400e-8ac5-f3e35662941a or https://nextcloud.imp.fu-berlin.de/index.php/s/MsMGYQeo2jyHQos , video2: https://fu-berlin.eu.vbrickrev.com/sharevideo/2493e910-cb71-4ef4-b765-fd7df2c527f3  or https://nextcloud.imp.fu-berlin.de/index.php/s/WbY5kHzEkXrZocR.

Week 2 (19.04.-23.04.2021):

Lecture 3: Discrete probability distributions  https://fu-berlin.eu.vbrickrev.com/sharevideo/1d2133bb-ca5d-42c7-8427-c9e52dde7508 or https://nextcloud.imp.fu-berlin.de/index.php/s/64sgW86tXtft5pM

Lecture 4: Continuous probability distributions, reliability https://fu-berlin.eu.vbrickrev.com/sharevideo/76842793-36f8-46b1-a1a3-ac5cb5211056  or https://nextcloud.imp.fu-berlin.de/index.php/s/Nt27eKeZTTHWfZY

Part b: Phase-type distributions https://fu-berlin.eu.vbrickrev.com/sharevideo/7654dbd2-25a8-4d61-b9d3-7afc4b361ea7  or  https://nextcloud.imp.fu-berlin.de/index.php/s/d5g78B96Qp5No9R

Week 3 (26.04.-30.04.2021):

Lecture 5: Bounds and limit theorems:  https://fu-berlin.eu.vbrickrev.com/sharevideo/8b37bbfd-993c-4d6d-90a7-31d5cd534583   or https://nextcloud.imp.fu-berlin.de/index.php/s/ofyrtwTQ7g6MLn4

Lecture 6: Discrete time Markov chains https://fu-berlin.eu.vbrickrev.com/sharevideo/491d7c88-4eb9-43ce-ac5a-0c465bc67cc5 or https://nextcloud.imp.fu-berlin.de/index.php/s/27LR85BS29A32tJ

Week 4 (03.05.-07.05.2021):

Lecture 7: DTMCs, Sojourn times and embedded MCs  https://fu-berlin.eu.vbrickrev.com/sharevideo/305636f9-7698-4994-b91e-cf5b238d9331 or https://nextcloud.imp.fu-berlin.de/index.php/s/w4k7dTT3qgzfczg

Lecture 8: DTMCs Classification of states https://fu-berlin.eu.vbrickrev.com/sharevideo/a74301da-bb72-4781-8bd7-076b60987e0f  or https://nextcloud.imp.fu-berlin.de/index.php/s/EK8S8ySTB4P8twi

Week 5 (10.05-14.052021):

Lecture 9: DTMCs, Irreducibility, Potential and Fundamental matrix   https://fu-berlin.eu.vbrickrev.com/sharevideo/fafba7ad-2061-4794-a743-387568f8620f   or  https://nextcloud.imp.fu-berlin.de/index.php/s/sDd7xzxHMAPoWQp

Lecture 10: Random Walk  https://fu-berlin.eu.vbrickrev.com/sharevideo/080d549b-5b74-449a-90a6-a7aa4c9a1a23  or  https://nextcloud.imp.fu-berlin.de/index.php/s/MEDn5Xa7zB9ZSkJ

Week 6 (17.05.-21.05.2021):

Lecture 11: Limiting and stationary distributions https://fu-berlin.eu.vbrickrev.com/sharevideo/4ca5c416-0719-4f42-b03a-280b0bdc9f03  or  https://nextcloud.imp.fu-berlin.de/index.php/s/9nqJ8PdEQKr7mwi 

Lecture 12: Reversibility    https://fu-berlin.eu.vbrickrev.com/sharevideo/b81bcc98-97ad-4b8e-bc3f-d4d124e55603   or  https://nextcloud.imp.fu-berlin.de/index.php/s/KjE5LQRsLb62fF3

Lecture 13: Page rank  https://fu-berlin.eu.vbrickrev.com/sharevideo/e65fb743-fcfd-4f27-9098-f2624556993f  or https://nextcloud.imp.fu-berlin.de/index.php/s/5FrkEn7WbsyG5BK

Week 7 (24.05.-28.05.2021):

Lecture 14: CTMCs  https://fu-berlin.eu.vbrickrev.com/sharevideo/f4e314ae-26fe-47e0-b841-69c97b2ad23f  or https://nextcloud.imp.fu-berlin.de/index.php/s/TJWyDYm64SeMsTf

Lecture 15: Renewal processes, PP, uniformisation, stochastic Petri nets https://fu-berlin.eu.vbrickrev.com/sharevideo/6d1cbc1b-9c6c-4791-a6e8-f91454b4e4e0   or  https://nextcloud.imp.fu-berlin.de/index.php/s/n83bq9jyXcFAkcK

Week 8 (31.5.-04.06.2021):

Lecture 16:

Petri net tool PIPE2:    https://fu-berlin.eu.vbrickrev.com/sharevideo/6ee2f5c1-4714-4bce-be27-2fe798cb5e03  or  https://nextcloud.imp.fu-berlin.de/index.php/s/Ri7wFbiEsF5Fedm

Lecture 17: Basic queueing theory   https://fu-berlin.eu.vbrickrev.com/sharevideo/bb1a2e24-6f6a-4497-82be-28a3d5d101ed or  https://nextcloud.imp.fu-berlin.de/index.php/s/KWAKz62miegR5m4

Week 9 (07.06.- 11.06.2021):

Lecture 18: Basic queueing theory (Part 2) https://fu-berlin.eu.vbrickrev.com/sharevideo/dacb3026-0717-40e6-96e3-12c6f7aa4e37    https://nextcloud.imp.fu-berlin.de/index.php/s/RqNi3kjSqBb9BN5

Lecture 19: The M/M/1 queue   https://fu-berlin.eu.vbrickrev.com/sharevideo/0a5911f9-0358-41e1-976b-d74e46a99525  or     https://nextcloud.imp.fu-berlin.de/index.php/s/8ZgN3NHRjHRnf9k

Week 10 (14.06.-18.06.2021):

Lecture 20: The M/M/m queue https://fu-berlin.eu.vbrickrev.com/sharevideo/a0b7ef7b-19ec-4997-a8d3-5e5a06ce114c   or  https://nextcloud.imp.fu-berlin.de/index.php/s/NSCAF924786HH8L

Lecture 21: The M/M/m/K queue  https://fu-berlin.eu.vbrickrev.com/sharevideo/c7495d8e-6c26-4c81-823c-08cc8aa8f799  or   https://nextcloud.imp.fu-berlin.de/index.php/s/fpMwgD7qYnQQjcW

Week 11 (21.06.-25.06.2021):

Lecture 22: The M/G/1 queue  https://fu-berlin.eu.vbrickrev.com/sharevideo/4a625125-ec14-40a2-9c59-b216c06b0e39 or  https://nextcloud.imp.fu-berlin.de/index.php/s/qGPo3NYj3Gj6rTJ

Lecture 23: Open queueing networks https://fu-berlin.eu.vbrickrev.com/sharevideo/c0722e9e-6cef-43e4-8021-e9dd1fd50cc8 or  https://nextcloud.imp.fu-berlin.de/index.php/s/q2gWwE9PAbZFYig

Week 12 (28.06.-02.07.2021):

Lecture 24 Closed Queueing Networks https://fu-berlin.eu.vbrickrev.com/sharevideo/0ce476d9-e232-46aa-ae72-ab444bd6a876 or  https://nextcloud.imp.fu-berlin.de/index.php/s/EZay9cz9AP4NR4q

Week 13 (05.07.-09.07.2021):

Lecture 25 Mean Value Analysis https://fu-berlin.eu.vbrickrev.com/sharevideo/85154b64-1e4d-4f24-b63e-2a108ac3948c  or  https://nextcloud.imp.fu-berlin.de/index.php/s/e9MR6ft4HTMa692

Week 14 (12.07.-16.07.2021):

Exam