Applications of Stochastics
Fall 2021 at BME

Lectures: Fridays 13:15-14:45, room H46, by Gábor Pete.
Labs: Tuesdays 10:15-11:45, room H46, by Marcell Nagy.

Topics planned:

Course structure and grading:

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 solos). 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 29 Fri, from the first two exercise sheets. Second midterm: Nov 30 Tue. Consultation on the preceding Thursdays, at 4:15 pm.

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% attendance on labs, a basically working simulation, and at least 40% on the midterms.

Diary:

Exercise sheet 1. Erdős-Rényi phase transitions, first and second moment method, different modes of convergence.
Exercise sheet 2. Borel-Cantelli, exponential Markov, Chung-Fuchs.
Exercise sheet 3. Cheeger-constant, clustering coefficient, centrality measures. Size-biasing, bus-paradox, renewal processes with rewards.
Exercise sheet 4. Renewal equations. Queueing. Copulas. Percolation.

Sept 7 Tue: Lab1: Triangle containment phase transition in the Erdős-Rényi random graph G(n,M).

Sept 10 Fri: Lect: A typical example of a simulation final project could be:

• For simple symmetric random walk on the integers, the return probability is P[S_{2n}=0] \sim 1/\sqrt{\pi n} by Stirling's formula, the standard deviation is D[S_n]=\sqrt{n}, and the CLT holds, hence, for every \eps>0, if K is large enough, then P[\sqrt{n}/K < |S_n| < K\sqrt{n}]>1-\eps holds for all n. That is, the typical distance is of order \sqrt{n}. This is not by simulation, but by recalling things from the Probability 1 course: Markov's and Chebyshev's inequalities, CLT. [See your old textbooks and/or Durrett PTE Chapter 1 and Section 3.1]
• Let L_t(i) be number of times the edge (i,i+1) is crossed by time t (in any direction) --- called the local time on the edge (i,i+1). Then consider the following self-repelling nearest-neighbour random walk: P[X_{t+1}=X_t+1 | X_0,X_1,\dots,X_t] / P[X_{t+1}=X_t-1 | X_0,X_1,\dots,X_t]=\exp(-\beta L_t(X_t)) / \exp(-\beta L_t(X_t-1)), for some fixed \beta > 0. Find by simulations the typical distance |X_t|, as a function of t. (The answer is a theorem of Bálint Tóth from 1995, with beautiful additional results with Fields-medal winner Wendelin Werner from 1998.)

Sept 14 Tue: Lab2: Analysing the triangle containment phase transition, with curve fitting, with several methods.

Sept 17 Fri: Lect: 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. Having a triangle in G(n,p): the probability is difficult to calculate, but the expectation of the number of triangles is easy. Variance is not hard, either. [PGG Section 12.3, first page.]

Sept 21 Tue: Lab3: Finishing the curve fitting. Isolated vertex versus connectivity phase transition.

Sept 24 Fri: Lect: Definitions of different types of convergences of random variables: in distribution, in probability, almost surely, in L^p. An example of converging in probability to 0, but not almost surely. An example of converging to 0 in P, but not in L^p. [See, e.g., Durrett PTE, first pages of Sections 2.2 and 3.2.] Chebyshev for triangle containment in Erdős-Rényi. Other subgraphs. 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.) [PGG Section 12.3, first page.]

Sept 28 Tue: Lab4: Finishing the analysis of the isolated vertex versus connectivity phase transition.

Oct 1 Fri: Lect: 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.] Starting the phase transition for the largest cluster at p=\lambda/n, around \lambda=1, via the exploration random walk and its Poisson limit. [PGG Theorem 12.23 in Section 12.3, and Figure 12.4.]

Oct 5 Tue: Lab5: Erdős-Rényi giant cluster and random walks.

Oct 8 Fri: Lect: The limiting exploration process is in fact the exploration process of the Galton-Watson branching process with Poi(\lambda) offspring distribution. Supercritical GW trees survive with positive probability. [PGG Figure 12.4 and the text around it.] For this, we used the Borel-Cantelli lemmas and the Strong Law of Large Numbers assuming a finite 4th moment. [Durrett's PTE Sections 2.3 and 2.4]

Oct 12 Tue: Lab6

Oct 15 Fri: Lect: Exponential Markov / Chernoff's inequality for Large Deviations via the moment generating function. [Durrett's PTE Section 2.7, first two pages] Application: for negative drift (subcritical Poisson GW tree), the time to hit zero has an exponential tail; the largest cluster in G(n,lambda/n) for lambda<1 is O(log n). An intuitive explanation that for \lambda>1 there is a unique giant cluster. [See PGG Theorem 12.23 for an actual argument, if you are interested.] Mentioning the Galton-Watson duality. [Lyons-Peres, Proposition 5.28] Starting the critical case: recalling the gambler's ruin for SRW, deducing the guess P[starting from 1, the SRW hits 0 in time > t] = Theta( t^{-1/2} ), mentioning the universality phenomenon. [See Exercise Sheet 2, Ex9 for the details.]

Oct 19 Tue: Lab7

Oct 22 Fri: Lect: Going through most of the problems in Ex Sheet 1. Critical GW trees die out: integer-valued Chung-Fuchs for recurrence of 1-dim random walks. [PGG Section 12.1, Exercise {ex.ChuFu} and around; Durrett PTE Section 5.4]

Oct 26 Tue: Lab8

Oct 29 Fri: Lect: Writing Midterm1.

Nov 2 Tue: Lab9

Nov 5 Tue: Lect: Barabási-Albert definition and degree distribution calculation: the original heuristics and a brief sketch of a proper argument. [Durrett RGD, Section 4.1] The isoperimetric ratio (Cheeger constant) of graphs.

Nov 9 Tue: Lab10

Nov 12 Fri: Lect: Why are Markov chain mixing times important, and what is the relevance of the Cheeger constant to this. [LPW book, HLW Expander survey]. Clustering coefficient. Centrality measures: degree, eigenvector, PageRank. [Newman Chapter 7, vdHofstad Chapter 1] Starting renewal processes, the bus paradox and size-biasing. https://towardsdatascience.com/the-inspection-paradox-is-everywhere-2ef1c2e9d709.

Nov 19 Fri: Lect: Renewal processes: SLLN, renewal processes with rewards, Elementary and Blackwell's Renewal Theorems. [Durrett EOSP, Section 3.1, Karlin-Taylor Sections 5.1-5.3, Durrett PTE Section 2.6]

Nov 23 Tue: Lab

Nov 30 Tue: Lab: Midterm2

Dec 3 Fri: Lect: Solving renewal equations. Renewal Theorem. [Durrett PTE Section 2.6, Karlin-Taylor Sections 5.4-6.] Here is my sketch solution for one of the examples. 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). [Feller Vol II. Section VI.9, here is the relevant part, Durrett EOSP Section 3.1]

Dec 7 Tue: Lab

Dec 10 Fri: Lect: Gaussian copula. [Wikipedia. Li's article.] Percolation theory: equivalence of the different definitions of p_c; Kolmogorov's 01 law; examples: \Z, \Z^2, regular trees. [PGG Section 12.1, or Grimmett Section 3.1]

Bibliography:

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