ENEE 620: Random Processes
Fall 2023
Instructor : Alexander Barg,
Professor
Department of Electrical and Computer Engineering/Institute for Systems Research
Office: 2361 A.V.Williams Building. E-mail abarg at umd dot edu
Course Homepage: http://www.ece.umd.edu/~abarg/620
TA: Arda Aydin, aaydin@umd.edu
Teaching arrangements:
Class times: TuTh 12:30-1:45, AJC2119
Discussion sessions: F 11:00-11:50 MTH B0429
TA Office hours: Monday 5-7pm, AVW 3182
Instructor availability outside class hours: after class (preferred), or send me an email
Canvas/ELMS is used for (1) submission of homework and exam papers; (2) posting of lecture notes, discussion materials.
Grading: Several (5-6) home assignments (20%), Max(midterm1, midterm2) 30%, Min(midterm1,midterm2) 20%, final (30%). All exams are take home.
This course does not rely on a single textbook. In preparing the lectures I use multiple sources including the books listed below and web resources. References are provided in the detailed outline of the course, and lecture notes will be posted on Canvas are we progress.
Lecture notes on probability theory:
Lect. # | Topics | Main sources | Further reading | HW | Solutions |
---|---|---|---|---|---|
Mathematical foundations of probability theory | |||||
1 (8/29) | Course description. Mathematical prerequisites. What is probability, by example: Borel's Normal Numbers |
Billingsley [B] Sec.1 | |||
2 (8/31) | Random points in (0,1] and normal numbers. WLLN and SLLN. Axioms of probability, algebras and σ-algebras | [B] Sec.1 | [V], Sec.V.1 - V.3 | ||
3 (9/5) | σ-algebras; Caratheodory's extension; Borel sets Continuity and σ-additivity; Borel-Cantelli lemmas |
[V], Sec.IV.4 [V], Sec.XI.1-2 [S], Sec.II.3 | [H], Sec.1.1 | ||
4 (9/7) | Random Variables (RVs), Distribution functions, PDFs | [V], Sec.XI.1-2; XII.1-3 [B], Sec.5 | [H], Sec.1.3 | ||
5 (9/12) | Expectation of an RV (motivation and approach to a general definition) |
[V], Ch.XIII.3-5 [B], Sec.5 and 21 | [H], Sec.1.5 [S], II.6 | HW1 | Solutions |
6 (9/14) | Properties of the expectation. Interchanging E and lim. |
[V] Sec.XIII.4, XIII.8 [S], Sec.II.6 | [R], Ch.5; [Ro] Ch.4 | ||
7 (9/19) |
Jointly distributed RVs. Cauchy-Schwarz. Fubini's theorem. Modes of convergence of RVs | [V], XIV.4-5; [B], Sec.18 [H], Sec.2.1 | [V], Sec.XII.5 [S], Sec.II.10 | ||
8 (9/21) | Modes of convergence. Convergence in distribution | [H], Sec.2.1 | [B], XII.5 [S]. Sec. II.10, III.1 | HW2 | Solutions |
9 (9/26) | Modes of convergence, continued. Convergence in distribution | [H], Sec.2.1 | [B], XII.5 [S]. Sec. II.10, III.1 | ||
10 (9/28) | Cauchy sequences of RVs Laws of Large Numbers. |
[S], Sec.II.10; [H], Sec. 2.2, 2.3 | [Ro],Ch.5, [V] Ch.XVI.2 [B], Sec. 7 | ||
11 (10/3) | Convergence of series of RVs and SLLN. Uniform laws of large numbers. Glivenko-Cantelli theorem. |
[S], Sec.II.10; [H], Sec. 2.2, 2.3 | [Ro],Ch.5, [V] Ch.XVI.2 [B], Sec. 7 | ||
Random Processes: Markov chains | |||||
12 (10/5) | Hoeffding's inequality. Random processes. | [B], Sec.36; [S], Sec.2.9 Markov Chains notes | [B], Sec.8 | ||
13 (10/10) | Kolmogorov's existence theorem. Discrete-time finite-state Markov chains: Basic properties. |
[B], Sec.36; [S], Sec.2.9 Markov Chains notes | [B], Sec.8 | ||
14 (10/17) | Recurrent and transient states
(MIT recorded lecture) Stationary and limiting distributions. Convergence analysis using eigenvalues of P. Rate of convergence to steady state. |
[G], Sec.4.3,4.4 | |||
15 (10/19) |
Markov chains with countably many states. Probability and expected time of return.
Strong Markov property
Limiting distributions and steady-state (equilibrium) distributions. Positive- and null-recurrent states. |
Markov Chains notes | [B], Sec.8 Random walks Null-recurrent random walk | ||
16 (10/24) | Lec. 15 continued | Markov Chains notes | [G], Sec.6.1, 6.2,6.5 | HW3 | Solutions |
17 (10/26) |
Ergodic theorem for Markov chains Reversible Markov chains. |
Markov Chains notes | [G], Sec.6.1, 6.2,6.5 | ||
18 (10/31) | Reversible Markov chains and random walks on graphs | Lecture notes | Generating functions Percolation, Ch 5 | ||
19 (11/2) | Branching processes. The Galton-Watson tree. Extinction probability. Percolation on a regular tree | Lecture notes | Generating functions Percolation, Ch 5 | HW4 | Solutions |
Martingales, convergence, and examples | |||||
20 (11/7) | Conditional expectation, examples, definition. |
[D1], Sec.4.1 | [B], Sec.34 [Gut] Sec.10.1 | ||
21 (11/9) | Conditional expectation. Martingales: Definition and examples | [D1], Sec.4.2 [B], Sec. 35 | [Gut], Sec.10.6,10.7,10.10 [G], Sec.9.8, 9.9 | ||
22 (11/14) | Martingale convergence theorem | [D1], Sec.4.2 [B], Sec. 35 | [Gut], Sec.10.6,10.7,10.10 [G], Sec.9.8, 9.9 | ||
23 (11/28) | Optional stopping theorem, examples |
[D1], Sec. 4.8 | [Gut], Sec.10.9, 10.10 | HW5 | Solutions |
Gaussian properties and Brownian motion | |||||
24 (11/30) | Wiener process (standard Brownian motion)
Paul Levy's construction of Brownian motion. |
[V], Sec.X.10-X.12 [B], Sec.37 | |||
25 (12/5) | Brownian motion from Haar wavelets. Properties of the Brownian motion | [D], Sec. 6.1,6.2 [D1], Sec.7.3,7.4 | [B], Sec.37 | ||
26 (12/7) | Brownian motion: Strong Markov property, Reflection principle, zeros. Integrating against B(t). | [D], Sec. 6.1,6.2 [D1], Sec.7.3,7.4 | [B], Sec.37 | ||
10/12 | Midterm1 (with solutions) Earlier exams:Midterm 1 (S21) Midterm 1 (F20) Solutions |
||||
11/16 | Midterm2 (with solutions) Midterm 2 (S21) | Midterm 2 (2020) | Midterm 2 (2019) |
||||
12/18 | Final exam | Solutions
Final exam S21 Solutions | Final exam F20 Solutions |
In preparing the lectures I use some parts of the following texts, listed in no particular order:
[B] P. Billingsley, Probability and Measure, 2nd Ed., New York: J. Wiley & Sons, 1986
[V] S. Venkatesh, The Theory of Probability, Cambridge University Press, 2013
[S] A. Shiryaev, Probability, 2nd Ed. Springer, 1996
[D] R. Durrett, Essentials of Stochastic Processes, 2nd Ed., Springer 2011. [pdf]
[D1] R. Durrett, Probability: Theory and Examples, 5th Ed., 2019, [pdf]
[G] R.G. Gallager, Stochastic Processes: Theory and Applications, Cambridge University Press, 2014
Web link
[Gut] A. Gut, Probability: A Graduate Course, Springer, 2005.
[Ro] J.S. Rosenthal, A First Look at Rigorous Probability Theory [web]
[H] B. Hajek, Random Processes for Engineers, Cambridge University Press, 2015