Lectures: Fridays 13:15-14:45, room H45a, 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 another 25% of the grade, there will be a midterm, consisting of exercises very similar to the ones on the exercise sheets. Date: Oct 22, during class. Here are some hints on the solutions. A retake (pótZH) will probably happen on the 11th week (not 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 70% attandance on both labs and lectures, a basically working simulation, and at least 40% on the midterm.
As an example, here is the first exam this year.
Exercise sheet 1. Erdős-Rényi phase transitions, first and second moment method, Borel-Cantelli lemmas, recurrence of random walks, large deviations bounds.
Exercise sheet 2. Preferential attachment graphs, clustering coefficient, centrality measures, eigenvalues of graphs and Markov chains.
Exercise sheet 3. Renewal theory. Queueing theory. Copulas. Percolation and the Ising model.
Feb 5 Tue: Lab: Triangle containment phase transition in the Erdős-Rényi random graph G(n,M).
Sept 13 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.]
Sept 17 Tue: Lab: Analysing the triangle containment phase transition, with curve fitting, with several methods.
Sept 20 Fri: First and second moment method for having isolated points: phase transition at p = (1+o(1)) log n / n. Starting the phase transition for the largest cluster at p=(1+o(1))/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, but not the differential equation part]
Sept 24 Tue: Lab: Finishing the curve fitting. Isolated vertex versus connectivity phase transition.
Sept 27 Fri: Lect: difference between convergences in distribution, in probability, almost surely. Borel-Cantelli lemmas. 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.
Oct 1 Tue: Lab: Largest cluster phase transition in the Erdos-Renyi random graph.
Oct 4 Fri: Lect: 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). 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]
Oct 8 Tue: Lab: Finishing the largest cluster phase transition in the Erdos-Renyi random graph. Recurrence/transience of 1-, 2-, 3-dim Simple Random Walk and the 1-dim Cauchy random walk.
Oct 11 Fri: Lab: Simulation of Barabási-Albert preferential attachment graph. Degree distribution, diameter.
Oct 15 Tue: Lect: final remarks on critical Erdos-Renyi: gambler's ruin for SRW, sketch definition of Brownian motion, explaining where the n^{2/3} cluster size comes from [PGG Exercise 6.17 and Theorem 12.23]. Barabási-Albert degree distribution calculation: the original heuristics and a proper argument. [Durrett RGD, Section 4.1]
Oct 18 Fri: Lect: Solving some of the HW exercises.
Oct 22 Tue: Midterm.
Oct 25 Fri: Lect: Isoperimetric ratio, expander graphs (with applications to mixing times of random walks, as a cultural remark) [HLW Expander survey]. Clustering coefficient. Degree and eigenvector centrality measures. [Newman Chapter 7, vdHofstad Chapter 1]
Oct 29 Tue: Lab: Centrality measures. Mixing time of random walks.
Nov 5 Tue: Lect: Google's PageRank [Newman Chapter 7]. Starting renewal theory: basic definitions and examples. Renewal paradox for Poisson point process [Durrett EOSP, Section 3.1, Karlin-Taylor Sections 5.1-5.3].
Nov 8 Fri: Lab: PageRank.
Nov 15 Fri: Lect:
SLLN for renewal processes, with rewards. Examples. Elementary Renewal Theorem. Blackwell's Renewal Theorem for non-arithmetic renewal distributions. [Durrett PTE Section 4.4, Karlin-Taylor Chapter 5.]Nov 19 Tue: Lab: Renewal theory.
Nov 22 Fri: Lect: Solving renewal equations. Renewal Theorem. [Durrett PTE Section 4.4, Karlin-Taylor Sections 5.4-6.] Here is my sketch solution for one of the examples. Starting queuing theory. [Durrett EOSP Section 3.1]
Nov 26 Tue: Lab: Queueing theory.
Dec 3 Tue: Lab: End of queuing theory. Beginning percolation on planar lattices.
Dec 7 Sat 10:15 - 13:30: Lect (plan): Lect: Queuing theory: blow-up for G/G/1 systems (if \lambda \leq \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.] Percolation theory. [PGG Section 12.1] Ising model. [PGG Section 13.1]
Dec 10 Tue: Lab: Percolation on planar lattices.
Dec 13 Fri: Lect: Ising model. [PGG Section 13.1]
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
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