ECE 534: RANDOM PROCESSES, FALL 2018

• Class time and place: 11:00-12:20 TTh, 3017 ECEB

  Instructor: Prof. Olgica Milenkovic 311 CSL, milenkov at illinois dot edu
  Office Hours: Tuesdays 1:30-3:00pm in 311 CSL

  Teaching Assistants: Sankagiri, Suryanarayana, ss19 at illinois dot edu
  Office Hours: Wednesdays 3-4:30pm, Room 3020 ECEB.
  Puoya Tabaghi, tabaghi2 at illinois dot edu
  Office Hours: Monday, 1-2:30pm, Room CSL 114.
  There will be weekly recitations: 3-4:30pm, Friday. Room 3020 ECEB.

Announcements

• Please try to attend the first recitation on August 31st, as Surya will go over some topics in elementary probability theory.
• The second recitation this semester: Bertrand's paradox, Buffon's needle, and additional problems.
• The Background Material Quiz will be held in class on Thursday, September 13. The quiz will cover material in basic probability theory, including the axioms of probability, combinatorial approaches to computing probability, conditional probability, independence of events, Bayes' formula, random variables, CDFs, PMFs and pdfs, expectations of random variables, functions of random variables.
• Grading policy for the homework: The TA will randomly select half of the problems for grading and your score will be solely based on your solutions for the selected problems. Please make sure to attempt to solve every problem!  
• There will be one quiz, two midterms and one final exam.
• Exam 1 will be held on October 18th, starting at 6pm, Room ECEB 3017 (our classroom). You will be allowed one sheet of notes (8.5''x11'', both sides) for the exam. Otherwise the exam is closed book.
• Exam 2 HAS BEEN MOVED TO TUESDAY, November 27th, DUE TO INCLEMENT WEATHER IN CHICAGO. It will start at 6pm, Room 2013 ECEB. You will be allowed two sheets of notes (8.5''x11'', both sides) for the exam. Otherwise the exam is closed book.
• The Final Exam will be a take home-exam.

---

Class Handouts and Supplements

• Reading material:    Prof. Leveque's lecture notes I.     
• Reading material:    Prof. Leveque's lecture notes II.     
• Lecture 1, Topic 1:    Peano axioms.     
• Lecture 1, Topic 2:    Godel's Incompleteness Theorems.     
• Lecture 1, Topic 3:    Cantor's theorem.     
• Lecture 1, Topic 4:    Aleph numbers and the Continuum hypothesis.     
• Lecture 1, Topic 5:    Cardinality of the Borel sigma-algebra.  
• Lecture 2, Topic 1:    Kolmogorov's axioms: Prof. Hajek's text, Chapter 1.  
• Lecture 2, Topic 2:    Continuity of probability, Prof. Hajek's book, Page 3.
• Lecture 2, Topic 3:    Length as a measure and Vitali sets: Prof. Hajek's text, Problem 1.37.    
• Lecture 3, Topic 1:    The Cantor set.     
• Lecture 3, Topic 2:    Cylinder sets.  
• Lecture 3, Topic 3:    Product Measures, Example from Prof. Hajek's book, Page 3.  
• Homework 1: Issued Sept. 4th, Due Sept. 18th.  
• Quiz Review Session:    Spring 2017 Quiz. ; Solutions.  
• Lecture 4, Topic 1:    Random variables and Measurable Functions.  
• Lecture 4, Topic 2:    Cumulative distribution functions, Prof. Hajek's book, Page 9.  
• Lecture 4, Topic 3:    Outer measures. Lebesgue measure.  
• Lecture 5, Topic 1:    Continuity, Uniform continuity, absolute continuity; pdf's.  
• Lecture 5, Topic 2:    Cantor function.  
• Lecture 5, Topic 3:    Riemann and Lebesgue integrals.  
• Lecture notes - advanced probability and measure theory (A. Dembo).  
• Lecture notes - elementary probability (C. Grinstead).  
• Lecture notes - advanced calculus (J. Muldowney).  
• Lecture 6, Topic 1:    Dirichlet function.  
• Lecture 6, Topic 2:    Covariance, correlation. Prof. Hajek's text, pg. 27-28.  
• Lecture 6, Topic 3:    Moments of RVs, moment generating and characteristic functions, Prof. Hajek's book, 16-20.  
• Homework 2: Issued Sept. 20th, Due Oct. 4th.  
• Lecture 6, Topic 4:    Characteristic functions always exist.  
• Lecture 7, Topic 1:    Holder's inequality.  
• Lecture 7, Topic 2:    Minkowski's inequality.  
• Lecture 8, Topic 1:    limsup, liminf.  
• Lecture 8, Topic 2:    limsup, liminf of sets.  
• Lecture 8, Topic 3:    Borel-Cantelli Lemma, Prof. Hajek's book, Page 7.  
• Lecture 9, Topic 1:    Almost sure convergence and convergence in probability. Prof. Hajek's text, pg. 40-42.  
• Lecture 9, Topic 2:    Understanding the difference between almost sure and convergence in probability.  
• Lecture 9, Topic 3:    Almost sure convergence: limsups and Borel-Cantelli lemma application.  
• Lecture 9, Topic 4:    Relationships between various modes of convergence - proofs. See also Prof. Hajek's book, pages 40-52.  
• Lecture 9, Topic 5:    Markov's inequality.  
• Homework 3: Issued Oct. 8th, Due Oct. 18th.  
• Lecture 10, Topic 1:    Jensen's inequality, Prof. Hayek, pg. 58.  
• Lecture 10, Topic 2:    Alternative characterizations of convergence in distribution (Prof. Hayek, pg. 46, Portmanteau lemma).  
• Lecture 10, Topic 3:    Examples of convergence in distribution: Extremal order statistics.  
• Lecture 11, Topic 1:    LLNs (Prof. Hayek, pp. 56-58).  
• Lecture 11, Topic 2:    Terry Tao's blog on the strong LLNs.  
• Lecture 12, Topic 1:    Central limit theorem (CLT), Prof. Hayek's text.
• Lecture 12, Topic 2:    Lindeberg's CLT.
• Lecture 12, Topic 3:    Berry-Essen theorem.
• Lecture 13, Topic 1:    Chernoff bound and large deviations, Prof. Hajek's text, page 60.
• Lecture 13, Topic 2:    Cramer's theorem, Prof. Hajek's text, page 61.
• Lecture 13, Topic 3:    Chernoff bound for a sum of independent, nonidentically distributed Bernoulli variables.
• Lecture 14, Topic 1:    Hoeffding and McDiarmid's inequality.
• Lecture 14, Topic 2:    Martingales, Doob Martingales and Azuma's inequality.
• Lecture 15, Topic 1:    Talagrand's inequality.
• Lecture 15, Topic 2:    Random Processes, Chapter 4, Prof. Hajek's text: Definitions, Second order processes, mean and correlation/covariance function. Gaussian processes.
• Lecture 15, Topic 2:    Random Processes, Chapter 4, Prof. Hajek's text: Gambler's ruin problem.
• Lecture 16, Topic 1:    Polya's urn model.
• Lecture 16, Topic 2:    Galton-Watson process.
• Lecture 16, Topic 1:    Polya's urn model.
• Homework 4: Issued Oct. 26th, Due November 8th.  
• Lecture 17, Topic 1:    Random Processes, Chapter 4, Prof. Hajek's text: Brownian motion, Poisson processes, Martingale processes, Stationarity.
• Homework 5: Issued Nov. 10th, Due November 26th.  
• Lecture 17, Topic 2:    Markov Chains.
• Lecture 18, Topic 1:    Perron-Frobenius Theory.
• Lecture 18, Topic 2:    PageRank.
• Homework 6: Issued Nov. 27th, Due December 11th.  
• Lecture 19, Topic 1:    Random vectors, minimum mean square error estimation: Chapter 3, Prof. Hajek's text.
• Lecture 19, Topic 2:    Chapter 3, Prof. Hajek's text: Innovation sequences.
• Lecture 20, Topic 1:    How Kalman filtering works.
• Lecture 21, Topic 1:    Random Matrices.

---

Course Details

• Syllabus: This is a graduate-level course on random (stochastic) processes, which builds on a first-level (undergraduate) course on probability theory, such as ECE 313. It covers the basic concepts of random processes at a fairly rigorous level, and also discusses applications to communications, signal processing, control systems engineering, and computer science. To follow the course, in addition to basic notions of probability theory, students are expected to have some familiarity with the basic notions of sets, sequences, convergence, linear algebra, linear systems, and Fourier transforms.

  Topics to be covered include:

  • Probability and Measure Theory Review;
  • Convergence of a Sequence of Random Variables;
  • Minimum Mean Squared Error Estimation;
  • Jointly Gaussian random variables and vectors;
  • Random Walks and Brownian Motion;
  • Discrete-Time Markov Chains;
  • Continuous-Time Markov Chains and Poisson Processes;
  • Stationarity, WSS and Ergodicity;
  • Martingales and the Azuma-Hoeffding Inequality;
  • Random Processes Through Linear Systems;
  • Kalman and Wiener Filtering;
  • Other topics as time permits.

   

  Required Text: B. Hajek, Random Processes for Engineers, Cambridge 2015. A soft copy of the book can be downloaded here. Preprints are also available through the ECE Store. I will also make frequent use of other texts, for example The Theory of Probability, by Santosh S. Venkatesh. See the Grainger Library reserves below.

  References in Grainger Library:
  Papoulis, A.; Probability, Random Variables, and Stochastic Processes
  Wong, Eugene; Introduction to Random Processes
  Wong, E./Hajek, B.; Stochastic Processes in Engineering Systems
  Stark, H./Woods, J.; Probability, Random Processes, and Estimation Theory
  Feller, W.M.; An Introduction to Probability Theory and its Applications
  Rudin, Walter; Principles of Mathematical Analysis
  Grimmett, G. R./Stirzaker, David R.; Probability and Random Processes
  Gallager; Discrete Stochastic Processes Santos Venkatesh, The Theory of Probability

  Exams, homework, grading, etc.:

• There will be approximately 7 Homework assignments. Collaboration on the homework is permitted, however each student must write and submit independent solutions. Homework is due within the first 5 minutes of the class period on the due date (usually Thursday, unless otherwise stated). No late homework will be accepted (unless an extension is granted in advance by the instructor).
   
• There will be two mid-term exams and one final. The dates will be announced shortly.
   
• Exam conflicts: You have the responsibility to contact the instructor and TA at least one week before the exam if you have any acceptable conflicts, such as another exam, a documented job interview etc. Not being prepared for the exam does not constitute a conflict, so please do not request alternative exam dates for this reason.
   
• You may bring one sheet of notes to the first hour exam, two to the second hour exam, and three to the final exam. You may use both sides of the sheets, the sheets are to be standard US (letter paper) or European (A4) size with font size 10 or larger printing (or similar handwriting size). The examinations are closed book otherwise. Calculators, laptop computers, tables of integrals, etc. are not permitted.
   
• Your course grade will be determined by your performance in the H, M1, M2 and F, according to the formula:
  
  Score = 0.15H + 0.25MT1 +0.25 MT2+0.35F ,
  
  where H, MT1, MT2 and F are normalized to 100.

---