Lectures: Fridays 13:15-14:45, room H46, by Gábor Pete.
Labs: Tuesdays 10:15-11:45, room H46, by Marcell Nagy.
We will study a variety of topics in stochastic processes, applicable in other sciences and real-life settings. This is done via a little bit of theory and a lot of exercises and computer simulations. Tuesday labs introduce problems and notions via computer simulations. One goal here is to teach students simulation skills; another goal is to make the course material visible and tangible. The Friday lectures discuss the new material rigorously. Harder proofs will often be omitted, illustrated only by simulations on the Tuesday labs. The discussion of exercise sheets will happen mostly on Fridays, sometimes on Tuesdays.
For 25% of the grade, choose one simulation project from this list, in pairs (or triples or solos in exceptional cases). Email us your choice; first-come-first-served. The preferred computer language is Python.
For two times 12.5% of the grade, there will be two 45-minute midterms during the lecture, consisting of exercises very similar to the ones on the exercise sheets. First midterm: Oct 16 Fri, from the first exercise sheet. Second midterm: Dec 4 Fri, 12:00 pm to 1:00 pm on Teams, from the second exercise sheet.
For 50% of the grade, there will be an oral final exam, consisting of reproducing definitions, simpler proofs, and solving exercises, again very similar to the ones on the exercise sheets.
The starred bonus exercises can be handed in before the start of the examination period for some extra points.
The grading scheme is that 2 from 40%, 3 from 55%, 4 from 70%, 5 from 85%. Passing the lab part (aláírás) requires 70% attandance on both labs and lectures, a basically working simulation, and at least 40% on the midterms.
Exercise sheet 1. Erdős-Rényi phase transitions, first and second moment method, Borel-Cantelli lemmas, different versions of convergence, Chung-Fuchs theorem.
Exercise sheet 2. Coming very soon! We will discuss some of the exercises on the class of Nov 27.
Sept 8 Tue: Lab: Triangle containment phase transition in the Erdős-Rényi random graph G(n,M).
Sept 11 Fri: Lect: Mentioning two motivations for studying random graphs: phase transitions in statistical physics, and complex networks. The two Erdős-Rényi random graph models. The standard couplings with G(n,M_1)\subset G(n,M_2) and G(n,p_1)\subset G(n,p_2), and the definition of increasing (upward closed) events. Another example of a coupling with two random walks on \Z. Having a triangle in G(n,p): the probability is difficult to calculate, but the expectation of the number of triangles is easy. Definition of convergence in probability, and an example of converging to 0 in P, but blowing up in expectation. Introducing the notations \ll, \gg, \asymp, \sim. [PGG Section 12.3, first page, and section on Notation. On convergence in P, Durrett PTE, Section 2.2, first page.]
Sept 15 Tue: Lab: Analysing the triangle containment phase transition, with curve fitting, with several methods.
Sept 18 Fri: Second moment method for triangle containment in G(n,p). An example of a subgraph containment question where the first moment does not tell us where the phase transition is, because the second moment is too big (see Exercise Sheet 1 for details, soon to come.) First and second moment method for having isolated points: phase transition at p = (1+o(1)) log n / n. [PGG Section 12.3, first page, and this write-up.]
Sept 22 Tue: Lab: Finishing the curve fitting. Isolated vertex versus connectivity phase transition.
Sept 25 Fri: Lect: Starting the phase transition for the largest cluster at p=\lambda/n, around \lambda=1, via the exploration random walk and its Poisson limit. Relation to the Galton-Watson branching process with Poi(\lambda) offspring distribution. [PGG Theorem 12.23 in Section 12.3, and Figure 12.4.] WLLN implies that for \lambda<1 the Poisson random walk dies almost surely. Difference between convergences in probability and almost surely. Borel-Cantelli lemmas.
Sept 29 Tue: Lab:
Oct 2 Fri: Lect: Besides convergence in probability and almost surely, also discussing convergence in distribution. Proof of Strong Law of Large Numbers under a 4th moment condition. [Durrett's PTE Section 2.3] Corollary: random walk on the integers, starting from 1, with negative or positive drift, will a.s. go, or might not go below zero, respectively. Integer-valued Chung-Fuchs for recurrence of 1-dim random walks. [PGG Section 12.1, Exercise {ex.ChuFu} and around; Durrett PTE Section 4.2]
Rick Durrett. Essentials of Stochastic Processes. 2nd edition. Springer, 2011. https://services.math.duke.edu/~rtd/EOSP/EOSP2E.pdf.
Rick Durrett. Probability: theory and examples. 5th edition. Cambridge University Press, 2019. https://services.math.duke.edu/~rtd/PTE/PTE5_011119.pdf.
Rick Durrett. Random graph dynamics. Cambridge University Press, 2007. https://www.math.duke.edu/~rtd/RGD/RGD.pdf.
William Feller. An Introduction to Probability Theory and Its Applications, Vol 2. Second edition. Wiley, 1971. Here.
Geoffrey Grimmett. Probability on graphs. Cambridge University Press, 2010. http://www.statslab.cam.ac.uk/~grg/books/pgs.html.
Remco van der Hofstad. Random graphs and complex networks, Vol. I. Cambridge University Press, 2017. http://www.win.tue.nl/~rhofstad/NotesRGCN.pdf
Shlomo Hoory, Nati Linial, Avi Wigderson. Expander graphs and their applications. Bull. Amer. Math. Soc. 43 (2006), 439-561.
S. Karlin and H. Taylor. A first course in stochastic processes. Academic Press, 1975. Here.
David X. Li. On Default Correlation: A Copula Function Approach. The RiskMetrics Group, Working Paper Number 99-07. Here.
See also https://en.wikipedia.org/wiki/Copula_(probability_theory).
Russ Lyons and Yuval Peres. Probability on trees and networks. Cambridge University Press, 2016. http://mypage.iu.edu/%7Erdlyons/prbtree/prbtree.html
Mark Newman. Networks. An introduction. Oxford University Press, 2010. Here.
Gábor Pete. Probability and geometry on groups. Book in preparation. PGG.pdf
Miklós Telek. Advanced Performance Modeling and Analysis. BME HIT jegyzet, 2017, http://webspn.hit.bme.hu/~telek/notes/pres.pdf
Tóth Bálint. A statisztikus fizika matematikai módszerei. BME TTK jegyzet, 2011. http://tankonyvtar.ttk.bme.hu/pdf/15.pdf