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:

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

    • Main topics:
  • Selective review of probability theory (Probability distributions, expectation)
  • Convergence of sequences of random variables; Laws of large numbers
  • Discrete-time Markov chains: Ergodic theorems, examples
  • The Poisson process; Continuous-time Markov chains
  • L2-theory of random processes; Gaussian processes and the Wiener process
  • Discrete-time martingales; Convergence and inequalities

    Lect. #TopicsMain sourcesFurther readingHWSolutions
    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    		HW2Solutions
    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.5HW3Solutions
    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 notesGenerating functions
    Percolation, Ch 5
    19 (11/2) Branching processes. The Galton-Watson tree. Extinction probability. Percolation on a regular tree Lecture notesGenerating functions
    Percolation, Ch 5    		HW4Solutions
    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 HW5Solutions
    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