ECE 534: RANDOM PROCESSES, FALL 2017

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

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

  Teaching Assistants: Mathew Halm, mhalm2 at illinois dot edu and Parisa Karimi, parisa2 at illinois dot edu
  Office hours: Matt - 3-5pm, Tuesdays, Room 3034; Parisa - 2-4pm, Wednesdays, Room 3034.

Announcements

• No recitations on the 26th of September.
• No recitations on the 19th of September.
• The Background Material Quiz will be held in class on Thursday, September 14. 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.
• First recitation this semester: Bertrand's paradox, Buffon's needle, and problem 1.1. in Prof. Hajek's text.
• New 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.
• Each Tuesday 6-7pm, starting from the 6th of September, there will be a Recitation section (one hour). Room 3017 ECEB. 
• Exam 1 will be held on October 17th, 2017, at 7pm. Room 2017ECEB. You will be allowed one sheet of notes (8.5''x11'', both sides) for the exam. Otherwise the exam is closed book.            
• Exam 2 will be held on November 30th, 2017, at 7pm. Room 2015ECEB. 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

• 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 2, Topic 1:    Length as a measure and Vitali sets: Prof. Hajek's text, Problem 1.37.    
• Lecture 2, Topic 2:    The Cantor set.     
• Lecture 2, Topic 3:    Kolmogorov's axioms: Prof. Hajek's text, Chapter 1.  
• Homework 1: Issued Sept. 5th, Due Sept. 14th.  
• Lecture 3, Topic 1:    Cardinality of the Borel sigma-algebra.  
• Lecture 3, Topic 2:    Cylinder sets.  
• Lecture 3, Topic 3:    Product Measures, Example from Prof. Hajek's book, Page 3.  
• Lecture 3, Topic 4:    Continuity of probability, Prof. Hajek's book, Page 3.
• Lecture 4, Topic 1:    limsup, liminf.  
• Lecture 4, Topic 2:    limsup, liminf of sets.  
• Lecture 4, Topic 3:    Borel-Cantelli Lemma, Prof. Hajek's book, Page 7.  
• Quiz Review Session:    Spring 2017 Quiz. ; Solutions.  
• Lecture 5, Topic 1:    Random variables and Measurable Functions.  
• Lecture 5, Topic 2:    Cumulative distribution functions, Prof. Hajek's book, Page 9.  
• Lecture 5, Topic 3:    Outer measures. Lebesgue measure.  
• Lecture 6, Topic 1:    Continuity, Uniform continuity, absolute continuity; pdf's.  
• Lecture 6, Topic 2:    Cantor function.  
• Lecture 6, Topic 3:    Riemann and Lebesgue integrals.  
• Lecture notes - advanced probability and measure theory (A. Dembo).  
• Lecture notes - elementary probability (C. Grinstead).  
• Homework 2: Issued Sept. 21st, Due Sept. 28th.  
• Lecture notes - advanced calculus (J. Muldowney).  
• Lecture 7, Topic 1:    Dirichlet function.  
• Lecture 7, Topic 2:    Moments of RVs, moment generating and characteristic functions, Prof. Hajek's book, 16-20.  
• Lecture 7, Topic 3:    Characteristic functions always exist.  
• Homework 3: Issued Sept. 29th, Due Oct. 10th.  
• Lecture 8, Topic 1:    Holder's inequality.  
• Lecture 8, Topic 2:    Minkowski's inequality.  
• Lecture 8, Topic 3:    Covariance, correlation. Prof. Hajek's text, pg. 27-28.  
• Lecture 8, Topic 4:    Almost sure convergence and convergence in probability. Prof. Hajek's text, pg. 40-42.  
• Lecture 9, Topic 1:    Understanding the difference between almost sure and convergence in probability.  
• Lecture 9, Topic 2:    Almost sure convergence: limsups and Borel-Cantelli lemma application.  
• Lecture 9, Topic 3:    Relationships between various modes of convergence - proofs. See also Prof. Hajek's book, pages 40-52.  
• Lecture 9, Topic 4:    Markov's inequality.  
• 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.  
• Homework 3: Issued Oct. 13th, Due Oct. 24th.  
• 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.
• Homework 5: Issued October 30th, Due November 9th.  
• 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.
• Lecture 17, Topic 1:    Random Processes, Chapter 4, Prof. Hajek's text: Brownian motion, Poisson processes, Martingale processes, Stationarity.
• Lecture 17, Topic 2:    Markov Chains.
• Homework 6: Issued November 13th, Due November 27th.  
• Lecture 18, Topic 1:    Perron-Frobenius Theory.
• Lecture 18, Topic 2:    PageRank.
• 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. 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.
   
• 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.05Q + 0.15H + 0.25MT1 +0.25 MT2+0.3F ,
  
  where Q, H, MT1, MT2 and F are normalized to 100.

---