Lectures: Thursdays and Fridays 10:15-12:00, room H46
Email: my first name at math dot bme dot hu
Office hours: see here.
Exercise sheet 1. Sheet 2. Sheet 3. Sheet 4. Sheet 5. Sheet 6. Sheet 7. Sheet 8. Sheet 9.
First midterm is on March 9, Friday, during class. Second midterm is on April 27, Friday, during class. (The midterm problems will be in English, but it is fine if you write your answers in Hungarian or in Hunglish.) And there will be an oral final exam, a few times during the examination period.
Here are the exam questions. Each student will get 3 random questions out of the 16, and can drop one. Office hours for the exams: June 6 Wed 3:15-5 pm, June 19 Tue 4:15-6 pm.
The weights for the final grade will be 25% first midterm, 25% second midterm, 50% final exam.
The grading scheme is that 2 from 40%, 3 from 55%, 4 from 70%, 5 from 85%.
1.) Feb. 8. The evolution of the Erdos-Renyi random graph G(n,p): stochastic domination, first and second moment method for the phase transition of containing a triangle. [PGG Section 12.3, first page. On stochastic domination, see vdHofstad Section 2.3.]
2.) Feb. 9. Component structure of G(n,(1+\eps)/n) for \eps < 0, \eps = 0, \eps > 0: stating the Erdos-Renyi-Luczak-Aldous theorem [PGG Theorem 12.23]. Starting the proof: apparent relation to the Poisson Galton-Watson tree, using an exploration process. Proving the phase transition between the extiction and survival of GW trees, with two methods so far: a) Generating functions. Stating the GW duality. b) For Z_n, use the first and second moment methods, and the martingale convergence theorem. [Lyons-Peres Section 5.1; vdHofstad Chapter 4; our Exercise 1.5. For background on martingales, see Durrett's PTE or EOSP, or vdH Section 2.5]
3.) Feb 15. Discussing Exercise sheet 1.
4.) Feb 16. Third method for GW phase transition: an exploration random walk related to depth-first-search [PGG Section 12.1, around Figure 12.1] Stating the Chung-Fuchs theorem. Stating and proving the Azuma-Hoeffding inequality for bounded martingale differences [PGG Section 1.2]. For the exponential decay for the volume of a subcritical GW tree, when the offspring is not bounded, I still owe a proof, since Azuma-Hoeffding used boundedness. For this, see Exercise sheet 2.
5.) Feb 22. Discussing Exercise sheet 2.
6.) Feb 23. The Erdos-Renyi phase transition for the giant cluster. [PGG Theorem 12.23] In the proof for the critical case, the bounds of Exercise 6.17 and (12.26) may be accepted without a full proof, doing them only for SRW on the integers instead of the Poisson(1)-1 jumps. (See Exercise sheet 3.)
7.) March 1. Solving Exercise 3/1. Approximate definition of Brownian motion and statement of Donsker's theorem, just as a cultural remark [Durrett's PTE Sections 8.1, 8.6]. Definition of Barabasi-Albert preferential attachment graphs, with the simplistic differential equation approximation for the degree distribution [Durrett's RGD, Section 4.1].
8.) March 2. Barabasi-Albert PA-graphs, with the system of difference equations for the expectations. [Durrett's RGD, Section 4.1] Definition of Doob's martingales, with some examples: MG's from discrete harmonic functions, and edge- and vertex-exposure MG's for Erdos-Renyi graphs [PGG Section 6.3]. Azuma-Hoeffding for the Doob MG in PA-graphs [Durrett's RGD, Section 4.1]. Starting renewal theory: the SLLN for the number of renewals and rewards collected [Durrett's EOSP, Section 3.1]
9.) March 8. Solving Exercises 3/3 and 4/3. First and Second Borel-Cantelli Lemmas, and the Strong Law of Large Numbers under a finite fourth moment assumption [Durrett's PTE Section 2.3]
10.) March 9. First midterm.
11.) March 10. A few more words about networks: clustering coefficient, PageRank, isoperimetry, expander graphs. [Newman Chapter 7, vdHofstad Chapter 1, Hoory-Linial-Wigderson survey] The Elementary Renewal Theorem. [Karlin-Taylor Chapter 5, Durrett EOSP Chapter 3, PTE Section 4.4]
12.) March 22. Discussing the problems of the First Midterm.
13.) March 23. 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]
14.) March 29. Solving renewal equations. The Renewal Theorem. The renewal paradox. [Durrett PTE Section 4.4, Karlin-Taylor Chapter 5]
15.) April 12. Discussing Exercise sheet 6.
16.) April 13. 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.]
17.) April 19. Discussing Exercise sheet 7.
18.) April 20. The Ising model of magnetization. Spatial Markov property, entropy, Gibbs principle. [PGG Section 13.1, Toth 1.4, 1.5, 2. fejezetek]
19.) April 26. Discussing Exercise sheet 8.
20.) May 3. Discussing the problems of the Second Midterm, plus the Curie-Weiss model from Exercise sheet 8.
21.) May 4. A Q/Q/1 queuing model blows up iff \lambda > \mu. The limiting waiting time in queue has the same distribution as the maximum of the random walk. [Feller Vol 2, Section VI.9. Note that Figure 1 is in Section VI.8. See also our Exercise 9/1.] Little's law [Durrett EOSP Section 3.2] Embedded Markov chains and explicit calculations in M/G/1 systems. [Telek pages 16-26, our Exercise 9/2.] Pollaczek-Khinchin formula [Our Exercises 9/3 and 9/4, Durrett EOSP Section 3.2.3, Durrett PTE Section 6.8.4] It is probably worth looking around on Miklos Telek's homepage for more material on queuing.
22.) May 10. Discussing Exercise sheet 9.
23.) May 11. More on Exercise 9/1. Recalling some basics of Continuous Time Markov Chains. Fluid queuing models: the PDE for first order homogeneous infinite buffer models, and finding the stationary solution. [Telek Chapter 4, the appropriate parts of pages 215-270.]
24.) May 17. Solving Exercise 9/5, including a Law of Large Numbers for the time spent at a given state of a CTMC. A probabilistic bit of the 2008/09 financial crisis: Gaussian copulae. [Wikipedia and David X Li's paper.]
25.) May 18. Repeated Second Midterm.
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