ENEE 620: Random Processes


Fall 2024

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: Geyang Wang, wanggy@umd.edu

Teaching arrangements:
    Class times: TuTh 12:30-1:45, AJC2119
    Discussion sessions: Th 5:00pm - 5:50pm (MTH0102) and Friday 11:00-11:50 (EGR 0135)
    TA Office hours: Fri 8:45-10:45 am, AVW 1109
    Instructor availability outside class hours: Wed. 11:00-12:30 or after class (preferred)
    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.

Main topics:

  • Mathematical foundations of probability theory
  • Convergence of sequences of random variables; Laws of large numbers
  • Discrete-time Markov chains: Ergodic theorems, examples
  • Discrete-time martingales; Convergence and inequalities
  • Gaussian processes and the Wiener process

    Lect. #TopicsMain sourcesFurther readingHWSolutions
    Mathematical foundations of probability theory
    1 (8/27) History of probability. Mathematical prerequisites.
    What is probability, by example: Borel's Normal Numbers    		 Billingsley [B] Sec.1
    2 (8/29) 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/3) σ-algebras; Caratheodory's extension; Borel sets
    Continuity and σ-additivity; Borel-Cantelli lemmas
    		[V], Sec.IV.4
    [V], Sec.XI.1-2
    		 [D], Sec.1.1, A.1;2.3
    [S], Sec.II.3
    4 (9/5) Random Variables (RVs), Distribution functions, PDFs [V], Sec.XI.1-2; XII.1-3
    [D] Sec.1.2, 1.3    		 [B], Sec.5 HW1 Solutions
    5 (9/10) Expectation of an RV
    (motivation and approach to the general definition)    		 [V], Ch.XIII.3-5
    [D], Sec. 1.4, 1.5    		[B], Sec.5 and 21
    [S], II.6
    6 (9/12) Properties of the expectation.
    		 [V] Sec.XIII.4, XIII.8
    [D], Sec.1.6     		[S], Sec.II.6, [Ro] Ch.4
    7 (9/17) Interchanging E and lim
    Modes of convergence of RVs
    		[V], XIV.4-5;
    [D] Sec.1.7     		[V], Sec.XII.5
    [S], Sec.II.10
    8 (9/19) Jointly distributed RVs. Cauchy-Schwarz. Fubini's theorem. Modes of convergence. [D], Sec.2.1, 1.7[B], XII.5
    [S]. Sec. II.10, III.1    		HW2Solutions
    9 (9/24) Modes of convergence, continued. Convergence in distribution [B], XII.5
    [S]. Sec. II.10, III.1
    10 (9/26) Cauchy sequences of RVs
    Laws of Large Numbers.     		[S], Sec.II.10;
    [D], Sec.2.2, 2.4    		[Ro],Ch.5, [V] Ch.XVI.2
    [B], Sec. 7
    11 (10/1) Convergence of series of RVs and SLLN.
    		 [S], Sec.II.10;
    [D],Sec.2.4,2.5    		[Ro],Ch.5, [V] Ch.XVI.2
    [B], Sec. 7
    Random Processes: Markov chains
    12 (10/3) Hoeffding's inequality. Random processes. [B], Sec.36; [S], Sec.2.9
    Markov Chains notes    		[B], Sec.8
    13 (10/8) Kolmogorov's existence theorem.
    Discrete-time finite-state Markov chains: Basic properties.    		 [D], Sec.A.3; [S], Sec.2.9
    Markov Chains notes    		[B], Sec.8
    14 (10/10) 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/17) 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/22) Lec. 15 continued Markov Chains notes[G], Sec.6.1, 6.2,6.5HW3 Solutions
    17 (10/24) Ergodic theorem for Markov chains
    Reversible Markov chains.     		Markov Chains notes[G], Sec.6.1, 6.2,6.5
    18 (10/29) Reversible Markov chains and random walks on graphs Lecture notesGenerating functions
    Percolation, Ch 5
    19 (10/31) Branching processes. The Galton-Watson tree.
    Extinction probability. Percolation on a regular tree    		 Lecture notesGenerating functions
    Percolation, Ch 5    		 HW4 Solutions
    Martingales, convergence, and examples
    20 (11/5) Conditional expectation, examples, definition.
    		 [D], Sec.4.1[B], Sec.34
    [Gut] Sec.10.1
    21 (11/7) Conditional expectation. Martingales: Definition and examples [D], Sec.4.2
    [B], Sec. 35    		[Gut], Sec.10.6,10.7,10.10
    [G], Sec.9.8, 9.9
    22 (11/12) Martingale convergence. theorem
    Optional stopping theorem, examples     		[D], Sec.4.2
    [B], Sec. 35    		[Gut], Sec.10.6,10.7,10.10
    [G], Sec.9.8, 9.9
    23 (11/19) Doob's martingales and OST. Reverse martingales. [Gut] Sec. 10.7
    [D] Sec 4.7    		[Gut], Sec.10.9, 10.10
    Gaussian properties and Brownian motion
    24 (11/21) Wiener process (standard Brownian motion)
    Paul Levy's construction of Brownian motion.     		[V], Sec.X.10-X.12
    [B], Sec.37     		HW5 Solutions
    25 (11/26) Properties of the Brownian motion [DS], Sec. 6.1,6.2
    [D], Sec.7.3,7.4     		[B], Sec.37
    26 (12/3) Brownian motion: Strong Markov property, Reflection principle, zeros. [DS], Sec. 6.1,6.2
    [D], Sec.7.3,7.4     		[B], Sec.37
    27 (12/5) Zeros of Brownian motion. Brownian motion and random walks
    10/15 Midterm1 Solutions
    Earlier exams: 1 | 2 | 3 solutions |
    11/14 Midterm2 Solutions
    Earlier exams: 1 | 2 | 3 | 4
    12/16 Final exam Solutions
    Earlier exams: 1 | 2 Solutions | 3 Solutions

    In preparing the lectures I use some parts of the following texts:
    Main:
    [B] P. Billingsley, Probability and Measure, 2nd Ed., New York: J. Wiley & Sons, 1986
    [D] R. Durrett, Probability: Theory and Examples, 5th Ed., 2019 [pdf]
    [V] S. Venkatesh, The Theory of Probability, Cambridge University Press, 2013
    [S] A. Shiryaev, Probability, 2nd Ed. Springer, 1996.
    Supplementary:
    [DS] R. Durrett, Essentials of Stochastic Processes, 2nd Ed., Springer 2011. [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]

    There are many online Lecture notes on probability theory. Here are some good sets:

  • Lecture notes - advanced probability and measure theory (A. Dembo).  
  • Lecture notes - elementary probability (C. Grinstead).