Lectures: Fridays 13:15-14:45, room H46, by Gábor Pete.
Labs: Tuesdays 12:15-13:45, room H27, 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. Email us your choice; first-come-first-served. The computer language may be C, Python, or Mathematica. The deadline is Dec 6 Thursday noon.
For another 25% of the grade, there will be a midterm, on October 29, 8 am, consisting of exercises very similar to the ones on the exercise sheets. Repeated on November 20, during the lab.
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. Sheet 2. Sheet 3.
Sept 4 Tue: Lab: Subgraph containment and connectivity phase transitions in the Erdős-Rényi random graph G(n,M).
Sept 7 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: Chebyshev and Paley-Zygmund inequalities. [PGG Section 12.3, first page.] Exponential Markov / Chernoff's inequality for Large Deviations via the moment generating function. [Durrett's PTE Section 2.6, first two pages]
Sept 11 Tue: Lab: Simulation for the cluster size phase transition of a typical vertex. A deeper look at the critical case. Degree distribution.
Sept 14 Fri: Examples class (by Ricsi): Discussing the exercises from Sheet 1.
Sept 18 Tue: Lect (by Balázs Ráth): Sketch proof for the cluster structure phase transition in G(n,p), via explicit calculations for the Poisson limit of the exploration random walk. His lecture notes, but skip the differential equation method and the proof of Kemperman's formula.
Sept 21 Fri: Lect: Recurrence/transience of 1-dim random walks; integer-valued Chung-Fuchs theorem. Application to the exploration random walk in Galton-Watson trees and Erdos-Renyi: exponential decay for large volume in the subcritical regime. [PGG Exercise 12.8 and around; Durrett PTE Sectoin 4.2]
Sept 25 Tue: Lab: Recurrence/transience of random walks: The Cauchy distribution shows that the Chung-Fuchs theorem is not sharp. Trying to see recurrence on Z^2.
Sept 28 Fri: Lect: Pólya’s theorem on recurrence/transience on Z^d. [PGG Section 1.1] Introducing the Barabasi-Albert preferential attachment graph. [Durrett RGD, Section 4.1]
Oct 2 Tue: Lab: Degree distribution and clustering coefficient for the Barabasi-Albert preferential attachment graph
Oct 5 Fri: Lect: Degree distribution for the Barabasi-Albert preferential attachment graph. [Durrett RGD, Section 4.1] Geometric properties of networks: isoperimetry or expansion; clustering coefficient. "Centrality measures" for measuring importance of vertices: 1. degree or indegree 2. leading eigenvector of adjacency matrix. [Newman Chapter 7, vdHofstad Chapter 1]
Oct 7 Tue: Lab: Centrality measures.
Oct 12 Fri: Lect: Centrality measure number 3: Google's PageRank. [Newman Chapter 7] Renewal theory: basic definitions and examples. Bus paradox and size-biasing. [Durrett EOSP Chapter 3, Karlin-Taylor Chapter 5]
Oct 16 Tue: Lab: Renewal paradox for heavy tailed renewal times.
Oct 19 Fri: Lect: Borel-Cantelli lemma, Strong Law of Large Numbers. [Durrett's PTE Section 2.3] Renewal theory: SLLN for the number of renewals and rewards collected [Durrett EOSP, Section 3.1]
Oct 26 Fri: Lect: Discussing Exercise sheet 2.
Oct 30 Tue: Lab: Discussing the midterm exercises.
Nov 6 Tue: Lab: Renewal theorem for joint distribution of the current and excess lifetimes. Basic queuing theorem.
Nov 9 Fri: Lect: Elementary renewal theorem. Delayed renewal processes, special delay to get a stationary process. Blackwell's Renewal Theorem: proof only for non-arithmetic \xi with finite mean \mu<\infty, using coupling with the stationary process. [Durrett PTE Section 4.4, Karlin-Taylor Chapter 5]
Nov 10 Sat: Renewal equations, renewal theorem. (Only sketch proofs.) [Durrett PTE Section 4.4, Karlin-Taylor Chapter 5]
Nov 13 Tue: Lab: Percolation theory: finding the critical density p_c for bond percolation on Z^2.
Nov 16 Fri: Lect: Percolation theory, but nobody turned up.
Nov 20 Tue: Lab: Midterm repeated.
Nov 23 Fri: Lect: Introduction to percolation theory. The equivalence of different definitions of p_c, Harris-FKG inequality, 1/3 \leq p_c(Z^2, bond) \leq 2/3, intuition why p_c(Z^2, bond)=1/2 should hold. [PGG Section 12.1, beginning of Section 12.4. Can also have a look at the Grimmett and Lyons-Peres books.]
Nov 27 Tue: Lab: Cardy's formula for critical percolation crossings.
Nov 30 Fri: Lect: Some examples of models of statistical physics. The Ising model of magnetization. Spatial Markov property, entropy, Gibbs principle. [PGG Section 13.1, Toth 1.4, 1.5, 2. fejezetek]
Dec 4 Tue: Lab: The Ising model of magnetization: Curie-Weiss simulation.
Dec 7 Fri: Lect: Some remarks on bootstrap percolation on Z^2, ergodicity of the product measure on transitive graphs. [PGG Lemma 12.4, first Exercise in Section 13.3] Discussing Ex Sheet 3.
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