Lectures: Fridays 10:15-11:45, room H607, by Gábor Pete.
Labs: Tuesdays 8:15-9:45, room H507, by Richárd Patkó.
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 computer language may be C, Python, or Mathematica.
For another 25% of the grade, there will be a midterm, consisting of exercises very similar to the ones on the exercise sheets. Date: April 12, Friday, during class.
For 50% of the grade, there will be a written final exam, consisting of reproducing simpler proofs and solving exercises, again very similar to the ones on the exercise sheets, with the types of problems already appearing in the midterm underrepresented.
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 a basically working simulation and at least 40% on the midterm.
Exercise sheet 1. Exercise sheet 2. Exercise sheet 3.
Feb 5 Tue: Lab: Triangle containment phase transition in the Erdős-Rényi random graph G(n,M).
Feb 8 Fri: Lect: The two Erdős-Rényi random graph models, and the couplings with G(n,M_1)\subset G(n,M_2) and G(n,p_1)\subset G(n,p_2). Subgraph containment phase transition in G(n,p). First and second moment methods, via Chebyshev's inequality. [PGG Section 12.3, first page.]
Feb 12 Tue: Lab: Finishing the triangle containment phase transition, with curve fitting.
Feb 15 Fri: First and second moment method for having isolated points: phase transition at p = (1+o(1)) log n / n. Phase transition for the largest cluster at p=lambda/n, via the exploration random walk and its Poisson limit. [PGG Theorem 12.23 in Section 12.3, or Balázs Ráth's lecture notes]
Sept 19 Tue: Lab: Isolated vertex versus connectivity phase transition.
Feb 22 Fri: Lect: Borel-Cantelli lemma. Strong Law of Large Numbers under a 4th moment condition. [Durrett's PTE Section 2.3] Exponential Markov / Chernoff's inequality for Large Deviations via the moment generating function. [Durrett's PTE Section 2.6, first two pages] Application: largest cluster in G(n,lambda/n) for lambda<1 is O(log n).
Sept 26 Tue: Lab: Largest and typical cluster size in the Erdos-Renyi random graph. The difference between convergences in distribution, in probability, almost surely.
March 1 Fri: Lect: The integer-valued Chung-Fuchs theorem on the recurrence of 1-dim random walks. Application: critical Galton-Watson branching processes die out. [PGG Section 12.1, Exercise {ex.ChuFu} and around; Durrett PTE Section 4.2]
March 5 Tue: Lab: Recurrence of 1-dim random walks with long jumps.
March 8 Fri: Lect: The last bit on critical Erdos-Renyi: where the n^{2/3} largest size comes from. [PGG Theorem 12.23, equation {e.DeepTrick}] Introducing the Barabasi-Albert preferential attachment graph. [Durrett RGD, Section 4.1]
March 12 Tue: Lab: Recurrence of 1-dim random walks with long jumps, part 2.
March 26 Tue: Lab: Barabási-Albert preferential attachment graph.
March 29 Fri: Lect: Finishing the Barabási-Albert degree distribution calculation. [Durrett RGD, Section 4.1] Clustering coefficient and centrality measures in networks: eigenvectors, Google's PageRank. [Newman Chapter 7, vdHofstad Chapter 1]
April 2 Tue: Lab: Discussing some exercises from Sheet 1.
April 5 Fri: Lect: Renewal theory: basic definitions and examples. SLLN for the number of renewals and rewards collected. Renewal paradox for Poisson point process. Size-biasing a random variable. [Durrett EOSP, Section 3.1, Karlin-Taylor Sections 5.1-5.3]
April 9 Tue (plan): Lab: Discussing some exercises from Sheet 2 if needed. Clustering and centrality measures.
April 12 Fri: Midterm.
April 26 Fri: Discussing the midterm exercises. Elementary Renewal Theorem [Durrett PTE Section 4.4]
May 3 Fri: Lect: Definition of non-arithmetic distributions. Stating Blackwell's renewal theorem. Solving renewal equations. Renewal Theorem. Application: the renewal paradox and size-biasing. [Durrett PTE Section 4.4, Karlin-Taylor Section 5.6]
May 10 Fri: Midterm retake.
May 17 Fri: Lect: A bit of queuing theory: blow-up for G/G/1 systems (if \lambda < \mu, then the system will always get empty again; if \lambda > \mu, then the waiting times converge a.s. to infinity). Little's law. [Feller Vol II. Section VI.9, here is the relevant part, Durrett EOSP Section 3.1] Gaussian copula. [Wikipedia. Li's article.]
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. 4th edition. Cambridge University Press, 2010. https://www.math.duke.edu/~rtd/PTE/PTE4_1.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
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