Math 564 (Stat 555), Applied Stochastic Processes, Fall 2016

Professor:Kay Kirkpatrick
Office:231 Illini Hall
Course site:
Lectures: MWF 1:00-1:50pm in 347 Altgeld Hall (will be videorecorded)
Office hours: Mondays and Wednesdays, 2:00-2:50, or by appointment. I would be happy to answer your questions in my office anytime as long as I'm not otherwise engaged, and before and after class are good times to catch me either in my office or in the classroom.
Textbook: The main text will be "Markov Chains" by J. R. Norris, available here and also here.
Grading policy: Homework: 40% of the course grade
Midterm: 30%, scheduled for Nov. 4. Please let me know ASAP if you need any accommodation.
Final Project: 30%, a paper or talk or webpage (your choice, though we'll have limited time for talks) on a topic of your choice related to the course. If you choose a webpage, it could have an interactive simulation. Our assigned final exam time is 7:00-10:00pm, Wednesday, December 14.
Classroom policy: I support individuals with diverse backgrounds, experiences, and ideas across a range of social groups including race, ethnicity, gender identity, sexual orientation, abilities, economic class, religion, and their intersections. I expect that we will all treat each other with respect. Please contact me to request disability accommodations.

Homework (due Fridays in class or to my mailbox in AH 250 by the end of class): You are encouraged to work together on the homework, but I ask that you write up your own solutions and turn them in separately.

Late homework will not be graded, so I will drop your lowest homework score.

HW #1 is due the second Friday in class: info sheet handed out on first day, also available here.

HW #2 is due Fri 9/9 in class: available here.

HW #3 is due Fri 9/16 in class: available here. All items except the last should be done on paper and handed in the usual way, and the last item is to email me (with copy to Shiya) about your final project, indicating whether you’ll pick a talk or a paper, which topics you’re considering and why, and 2 or 3 references you will work from (books, articles, and technical websites are all fine). Talks will be 15 minutes each, subject to time constraints. Papers will be 3-10 pages, possibly more if you would like to include a complete chapter of your thesis. Another option is a webpage that is 2-5 screens long, with an interactive simulation that you program.
(P.S. Here's an idea for a fun project: Markov chain random music.)

HW #4 is due Fri 9/23, paper part due in class, email part due by 5pm available here. The last item is to read "How to give a good colloquium" by John McCarthy, attend a colloquium, and email us (both Kay and Shiya) a few sentences describing a) one slide or section of the talk that you thought worked well, and b) how you would improve another part. You should cite the McCarthy reading at least once, and include photo(s) or notes on the parts of the talk you're analyzing. Some options: Math, ECE, Physics, CS, etc.

HW #5 is due Fri 9/30 in class available here. Note that the first item includes reading John Lee's essay "Some Remarks on Writing Mathematical Proofs" before doing the remaining HW problems.

HW #6, your project proposal, is due Fri 10/7 via email to both Kay and Shiya by 5pm. Please type this and aim for a length between 3/5 of a page and a full page (your references can spill over into a second page), addressing each of the following prompts:
1. In the introductory paragraph, identify your topic and your main message, also known as a thesis statement (see the link) or a motivating question that your final project will answer.
2. Think about your audience: your classmates, not just me; people in STEM, not just in your field. Write a paragraph addressing some or all of the following questions: Why should your audience care? What do you want them to take away from your project? How can you clarify the benefits of your project to your audience?
3. Specifics: What kinds of audiovisual aids will you be choosing to use? Your project should have at least one item of visual interest (picture, simulation, etc.), and at least one item of technical interest (theorem, algorithm, etc.). Which two or three definitions or key ideas will you introduce to your audience? What is a good example (think n=2) that illustrates the main point of your project? Can you find a story that's related to your topic?
Items 1-3 combined should be about 3 paragraphs, within the 3/5 to 1 page limit.
4. Annotated bibliography: can go beyond the 1 page limit, and should contain at least 3 references, or 1 more than you included in the pre-proposal email that was due 9/16. Please annotate each reference by indicating which sections of the references are most relevant to your project and what their main messages are.
P.S. Another option for the final project is to read the introduction and several chapters of Cathy O'Neil's book Weapons of Math Destruction and connect it to a probability article. Please find some way to estimate among yourselves how many books we will need: I want to be efficient by sharing n books among m people, where n < m :)
P.P.S. Math 564 field trip on Fri 10/7 at 1pm to attend the CM seminar by Nobel winner Tony Leggett in 190 ESB. Please see the email for details about how to get credit for participating in this.

HW #7 is due Friday 10/14 by the end of class (in-class participation and notes) or 5pm (email summary to both of us): Read some advice on communication, e.g., "How to Talk Mathematics" by Paul Halmos, though you can also find another reading that's relevant to your field of study and favorite medium of communication. Then prepare notes for explaining one of the following concepts: 1) sigma-algebras and partitions, 2) information and filtrations, 3) stopping/hitting/return times, 4) the Markov properties, and 5) recurrence vs. transience. To get full credit for this HW, you should turn in your (written) prepared explanation of your chosen concept and do one of the following: summarize your reading in 3-5 paragraphs in an email (with citation/link if you find your own reading), or present a concept explanation in class at the blackboard.
The in-class structure will be: deciding with your group (grouped by number 1-5 as above) which 2 or 3 of you will present 2 minutes on which aspects of the concepts (e.g., one gives definition, another gives example, and third draws a picture), and then getting through at least 2 or 3 of the concepts. Between this review session and a later one, our expectation is that most of you will present at the blackboard.
Also: Quiz on Friday 10/14, similar to HWs that have been graded and returned by then. If you do well on the quiz, it will replace a low HW score; if not, I'll drop the quiz. HW solutions for studying are available here, here, and here, with different problem numbering.

HW #8 is due Friday 10/21 in class: available here. Note that some of the problems have solutions available above, which you are welcome to consult.

HW #9 is due Friday 10/28 in class: available here. You are welcome to email part of the assignment if that's suitable. Also, I'm gone Wed 10/26 and Fri 10/28, one of which will be a review day and one of which will be a discussion day based on the extra lecture video, available here. For the review session prepare notes again, explaining one of the following concepts that you have not prepared before: 1) sigma-algebras and partitions, 2) information and filtrations, 3) stopping/hitting/return times, 4) the Markov properties, 5) recurrence and transience, 6) invariant/equilibrium distributions, 7) time reversal and detailed balance, 8) ergodicity. To get full credit for this HW, you should turn in your prepared notes or present an explanation in class at the blackboard.

No HW due the day of the midterm, Friday 11/4.

HW #10, due Friday 11/11 in class: available here. One item should be added, to look at Bloom's taxonomy of learning and indicate what skills you practice in school, and indicate the two or three levels on which you spend most of your learning time. Also for this item, write a sentence about how your final project will challenge you to learn at a higher level.

HW #11, due Friday 11/18 in class or email to both of us by 5pm: Attend a talk and revise two slides. Also, there will be a short in-class writing assignment that will be graded.
1. Read this downloadable booklet on slide design for scientific talks or "Slides are not all evil"--both written by Jean-luc Doumont.
2. Attend a talk and take pictures of two slides or ask the speaker for slides/code. The two slides should be a) one that you think needs improvement, and b) one that you like, which you're welcome to tweet. Revise both slides according to the principles that you've learned, drawing or texing up your suggested changes. This may include finding or drawing a picture to illustrate the main point of the slide, or making the wording more efficient. Improve the better slide b) in at least one small way. The homework that you turn in should look something like this example, with four slides: two originals and two improved versions (at least hand-drawn, not necessarily texed).

ANNOUNCEMENT: there will be a guest lecture on Fri 12/2 (in our usual class meeting time and place) by Prof. Stephen Levinson (Illinois ECE) about Hidden Markov Models. Attendance/participation will be graded.

HW #12, due Friday 12/2 in class and/or email (title/abstract/rough draft) to both of us by 5pm: available here. Here are links for the readings--please pick the ones that are relevant to your final project:
"How to give a good 20-minute math talk" by William Ross
"The Science of Scientific Writing" by Gopen and Swan

On the last day of class, Wed Dec 7, there will be a graded in-class writing assignment. It will be to compare and contrast for DTMCs and CTMCs one of the following topics: 1) absorption/hitting/return times, 2) the Markov properties, 3) recurrence/transience, 4) invariant distributions, 5) time reversal and detailed balance, 8) explosion/non-explosion 9) more to follow...?

Extra Credit Opportunity (due by email before the final exam time, Dec. 14 at 7pm): Translate part of Blackwell's dissertation into modern notation and terminology, and connect it to the literature since then (e.g., renewal theory). I have paper copies, and it's available electronically with your netID at

Research Opportunity for Spring 2017: I have research ideas that would involve some subset of machine learning, computer vision, and natural language processing. Background in these areas would be ideal, but a willingness to learn them quickly could suffice. Please let me know if you're interested.

All final projects are due via email by the final exam time, Dec. 14 at 7pm (for speakers, this means emailing final slides before 7pm). Attendance/participation will be graded during the final exam period, estimated to run from 7pm to 8:30pm on Dec. 14, in the usual classroom.

Here's an example of a project webpage:

Here are some class videos:
Mon 8/22 Double pendulum, sets, and sequences
Wed 8/24 Partitions and sigma algebras
Fri 8/26 Measures, probability spaces, independence of events, and random variables
Mon 8/29 Conditional probability and expectation, independence of RVs
Wed 8/31 Law of total expectation, filtrations, moment generating functions, and Jensen's inequality
Fri 9/2 Background on linear algebra, transition probability matrices, spectrum of a matrix, Gershgorin Circle Theorem
Wed 9/7 Gershgorin application to stochastic matrices, cumulative distribution functions, Inverse Transform method
Fri 9/9 Monte Carlo Methods, Law of large numbers, definition of discrete-time Markov chain, Markov property
Mon 9/12 Stochastic Processes, transition matrices, Markov property
Wed 9/14 Markov chains, probability density functions and cumulative distribution functions, hitting/stopping/absorption time and probability, mean stopping/hitting/absorption time, Lemma 1 and proof
Fri 9/16 Example of E(X) infinite but X always finite, Theorem with linear system for the stopping probability, Lemma 2 and proof, Theorem for mean stopping time, statement of phi-Theorem
Mon 9/19 Proof of phi-Theorem, Lemma and proof, special cases of phi-Theorem
Wed 9/21 Moments of stopping/hitting times, another special case of phi-Theorem, the Markov chain at successive return times, Strong Markov property
Fri 9/23 Constructing a Markov chain with certain properties, proof of Strong Markov, communicating class structure
Mon 9/26 Irreducibility, recurrent and transient, Dichotomy Theorem.
9/28 Return probability
9/30 Recurrent classes

Mon 10/31
Wed 11/2


This is a graduate course on applied stochastic processes, and measure theory is not a prerequisite for this course. The goal of this course is a good understanding of the basic stochastic processes and their applications. This course is designed for those graduate students who are going to need to use stochastic processes in their research but do not have the measure-theoretic background to take the Math 561-562 sequence. The materials covered in this course include the following: (1: a couple of weeks) background on probability, linear algebra, and set theory (2: about 5 weeks) discrete time Markov chains; (3: about 5 weeks) continuous time Markov chains; (4: a couple of weeks) discrete time martingales, and (5) stationary processes and applications to queuing theory and other fields (your projects contribute here). This course can be tailored to the interests of the audience.

Why might you want to study probability?

Two main reasons: uncertainty and complexity. Uncertainty is all around us and is usefully modeled as randomness: it appears in call centers, electronic circuits, quantum mechanics, medical treatment, epidemics, financial investments, insurance, games (both sports and gambling), online search engines, for starters. Probability is a good way of quantifying and discussing what we know about uncertain things, and then making decisions or estimating outcomes. Some things are too complex to be analyzed exactly (like weather, the brain, social science), and probability is a useful way of reducing the complexity and providing approximations. And the reason I study probability: statistical mechanics, which combines both the uncertainty of quantum mechanics, and the complexity of zillions of particles interacting.

Why work on your communication skills?

"It usually takes me more than three weeks to prepare a good impromptu speech." --Mark Twain

I think that success in your career (any career) depends in part on how well you communicate your ideas and persuade other people, so I am giving you a chance to learn and practice good writing or presenting skills. Some of the homework assignments will lead up to the final project, for which you will have a choice of topic (related to the course) and of communication format (paper or talk). The homework will be graded partly on clarity, brevity, and coherence. This is a great opportunity to improve your writing or presenting skills, in order to make your ideas more clear and persuasive--and to succeed.

"I am sorry I have had to write you such a long letter, but I did not have time to write you a short one." --Blaise Pascal

Emergency information link and the new one.

Some more resources for writing and speaking:

Halmos: How to Write Mathematics
Gopen and Swan: The Science of Scientific Writing
Williams: Style: The Basics of Clarity and Grace (book, any edition), Longman.

Gallo: Public-Speaking Lessons from TED Talks
Lerman: Math job talk advice
Steele: Speaking tips organized in categories that includes this great but little-known tip about graphs on slides

Fun picture of queues.