Pinsky Karlin 2.4.3 Solutions
MATH 180B (Winter quarter 2017). Introduction to Stochastic Processes
Instructor: David A. MEYER
Office hours: AP&M 7218, W 11:00am-12:00nn, or by appointment (AP&M 7256)
Lecture: Ledden Auditorium, MWF 10:00am-10:50am
Email: dmeyer "at" math "dot" ucsd "dot" edu
Teaching assistant: Artem MAVRIN
Office hours: AP&M 5412, M 11:00am-12:00nn, Tu 12:00nn-1:00pm
Section A01: Center Hall 217B, M 5:00pm-5:50pm
Section A02: Center Hall 217B, M 6:00pm-6:50pm
Email: amavrin "at" ucsd "dot" edu
Teaching assistant: Daniel COPELAND
Office hours: AP&M 5801, Th 2:00pm-4:00pm
Section A03: Center Hall 217B, M 7:00pm-7:50pm
Email: drcopela "at" ucsd "dot" edu
Teaching assistant: Ning MA
Office hours: AP&M 6436, M 4:00pm-5:00pm
Section A04: Center Hall 217B, M 8:00pm-8:50pm
Email: nima "at" ucsd "dot" edu
Teaching assistant: Ching-Wei HO
Office hours: AP&M 5760, M 1:00pm-3:00pm, W 3:00pm-5:00pm
Section A05: AP&M B402A, M 3:00pm-3:50pm
Section A06: AP&M B402A, M 4:00pm-4:50pm
Email: cwho "at" ucsd "dot" edu
Course description
This course is an introduction to stochastic processes. Such processes are used to model systems that evolve in time, or have some spatial dependence, in a way that is partly random. These kinds of models are used in (at least) biology, physics, engineering, economics, and political science.
Math 180B is intended for students who have already completed a course in probability comparable to Math 180A. The additional prerequisites for this course are Math 20D (ordinary differential equations), Math 20F or Math 31AH (linear algebra), and Math 109 (introduction to proof). The textbook is Mark A. Pinsky and Samuel Karlin, An Introduction to Stochastic Modeling (Burlington, MA: Academic Press 2011). We will cover most of chapters 2, 3, 4 and 5. (In the Spring quarter Math 180C will cover additional topics in this text.)
There will be weekly homework assignments, due in section on Mondays, or before 8:50pm Monday in the appropriate drop box in the basement of AP&M. Students are allowed to discuss the homework assignments among themselves, but are expected to turn in their own work — copying someone else's is not acceptable. Homework scores will contribute 15% to the final grade. Occasional extra credit problems are due by specific dates, turned in to Professor Meyer, not in section; each worth not more than 5% of the final grade.
There will be two midterms, currently planned for Week 4 and Week 8. The final is scheduled for 8:00am Friday, March 24. Scores on the two midterms and final will contribute 25%, 25% and 35% to the final grade, respectively. There will be no makeup tests.
Syllabus (subject to modification)
| Jan 9 | overview of stochastic processes |
| Jan 11 | §2.1. Conditional probability in the discrete case definition binomial/binomial example binomial/Poisson example conditional expectation values HWK (for Tuesday, Jan 17). Ex. 2.1.5; Pr. 2.1.8 Ex. 2.3.3; Pr. 2.3.1, 2.3.4 [solutions] |
| Jan 13 | binomial/binomial example properties §2.3. Sums of random numbers of random variables mixed conditional probabilities E[X1 + ... + XN ] Var[X1 + ... + XN ] |
| Jan 16 | No lecture; Martin Luther King, Jr. Day |
| Jan 18 | §2.4. Conditioning on continuous random variables definition, example §2.5. Martingales definition etymology [1] constant expectation value Markov's inequality applied to Martingale HWK (for Monday, Jan 23). Ex. 2.4.2, 2.4.3; Pr. 2.4.2 Ex. 2.5.2, 2.5.3; Pr. 2.5.1, 2.5.2, 2.5.5 [solutions] |
| Jan 20 | the maximum Markov inequality for nonnegative Martingales gambling example bivariate normal distributions [notes] |
| Jan 23 | Chap. 3. Introduction to Markov chains §3.1. Definitions Markov process discrete time Markov chain matrix of 1-step transition probabilities §3.3. Ehrenfest urn example §3.2. Transition probability matrices HWK (for Monday, Jan 30). [problem about bivariate normal distribution] Ex. 3.1.2, 3.1.5; Pr. 3.1.2 Ex. 3.2.2, 3.2.6; Pr. 3.2.2, 3.2.5 Ex. 3.3.1; Pr. 3.3.2, 3.3.7 [solutions] |
| Jan 25 | matrix of n-step transition probabilities Theorem: P (n) = Pn §3.4. First step analysis examples |
| Jan 27 | absorbing and transient states general absorbing Markov chain |
| Jan 30 | maze example review for exam [practice exam] [practice solutions] HWK (for Monday, Feb 6). Ex. 3.4.1, 3.4.4; Pr. 3.4.1, 3.4.2, 3.4.7, 3.4.8, 3.4.15 [solutions] |
| Feb 1 | Midterm 1. Will cover material through §3.3. Please bring a bluebook and your student ID. You may bring a page of handwritten notes, but nothing else. [seat assignments] [exam] [solutions] [results] |
| Feb 3 | expectation values of functionals of states §3.5. Some special Markov chains 2 state Markov chain diagonalization of transition matrix P to compute Pn equilibrium/stationary distribution |
| Feb 6 | review of evolution of probability distribution by transition probability matrix Extra Credit 1 (for Monday, Feb 13). [problem] [solution] Markov random fields [notes] definition Extra Credit 2 (for Tuesday, Feb 21). [problem] [solution] §3.5. Some special Markov chains Markov chains from independent random variables HWK (for Monday, Feb 13). Ex. 3.5.4, 3.5.8; Pr. 3.5.1, 3.5.4, 3.5.5 Ex. 3.6.1 [solutions] |
| Feb 8 | comments on Midterm 1 [2] examples one dimensional random walks |
| Feb 10 | §3.6. Functionals of random walks Gambler's ruin problem solution by analogy with ODE |
| Feb 13 | §3.8. Branching processes definition examples mean and variance extinction probability HWK (for Tuesday, Feb 21). Ex. 3.8.1, 3.8.4; Pr. 3.8.2, 3.8.3 Ex. 3.9.1, 3.9.2; Pr. 3.9.1, 3.9.3, 3.9.6 [solutions] |
| Feb 15 | §3.9. Generating functions definition properties application to branching process extinction probabilities §4.1. Regular transition probability matrices definition Perron-Frobenius theorem |
| Feb 17 | limit distribution as unique eigenvalue 1 (left) eigenvector examples doubly stochastic matrix limit distribution of regular doubly stochastic matrix is constant limit distribution as average visit fraction |
| Feb 20 | No lecture; Presidents Day |
| Feb 22 | §4.2. Examples increasing state space to make Markov PageRank [3] HWK (for Tuesday, Feb 28). Ex. 4.1.3, 4.1.8; Pr. 4.1.2, 4.1.3 Ex. 4.2.5; Pr. 4.2.6 Ex. 4.3.2; Pr. 4.3.1 [solutions] |
| Feb 24 | §4.3. Classification of states definition of state j being accessible from state i definition of states i and j communicating communicates with is an equivalence relation irreducible means only a single equivalence class definition of period of a state, aperiodic |
| Feb 27 | period is a class function first return probabilities definition of recurrent and transient states conditions for recurrence recurrence/transience is a class function unbiased random walk on Z is recurrent review for exam [practice exam] [practice solutions] |
| Mar 1 | Midterm 2. Will cover material through §4.3. Please bring a bluebook and your student ID. You may bring a page of handwritten notes, but nothing else. [seat assignments] [exam] [solutions] [results] |
| Mar 3 | §4.4. Basic Limit Theorem of Markov chains mean duration between visits positive and null recurrent stationary distribution is eigenvalue 1 (left) eigenvector unbiased random walk on Z is null recurrent recurrence/transience in higher dimensional random walks HWK (for Tuesday, March 7). Ex. 4.4.3; Pr. 4.4.7 |
| Mar 6 | §5.1. Poisson processes review of Poisson distribution definition of Poisson process example nonhomogeneous/nonstationary Poisson process §5.2. Rare events connection between Poisson process and sums of Bernoulli random variables |
| Mar 8 | Poisson approximation theorem for sums of Bernoulli random variables with differing probabilities Poisson point process HWK (for Tuesday, Mar 14). Ex. 5.1.3, 5.1.5, 5.1.9; Pr. 5.1.2, 5.1.3, 5.1.9 Ex. 5.2.4; Pr. 5.2.4, 5.2.5, 5.2.11 [solutions] |
| Mar 10 | §5.5. Generalization to higher dimensions §5.3. Distributions for random variables associated with Poisson processes definition of waiting times probability density functions for waiting times definition of sojourn times joint probability density function for sojourn times |
| Mar 13 | §5.4. Uniform distribution and Poisson process Poisson process conditioned on X(t) = n equivalent to n i.i.d. uniform samples from (0,t] application to order statistics |
| Mar 15 | application to expected discounted future value application to estimated failure rate Practice problems. Ex. 5.3.2, 5.3.4; Pr. 5.3.1, 5.3.4 Ex. 5.4.2, 5.4.5; Pr. 5.4.1, 5.4.7 Ex. 5.5.1; Pr. 5.5.3 Ex. 5.6.2, 5.6.4; Pr. 5.6.2, 5.6.3 [solutions] [more solutions] |
| Mar 17 | §5.6. Marked Poisson processes definition compound Poisson process expectation value and variance example of binary marks generalization to N-valued marks inhomogeneous spatial Poisson process example of continuous valued marks Course overview [practice exam] [practice solutions] |
| Mar 24 | Final: 8:00am-11:00am. Please bring bluebooks and your student ID. You may bring a page of handwritten notes, but nothing else. [seat assignments] [exam] [solutions] [results] |
Suggested reading
| [1] | R. Mansuy, "Histoire de martingales", Mathématiques & Sciences Humaines/Mathematical Social Sciences (2005) 105-113; translated by R. Sverdlove, "The origins of the word 'martingale'", Electronic Journ@l for History of Probability and Statistics 5 (2009) 1-10 . |
| [2] | E. T. Jaynes, Probability Theory: The Logic of Science, G. L. Bretthorst, ed. (Cambridge: Cambridge University Press 2003). |
| [3] | L. Page, S. Brin, R. Motwani and T. Winograd, "The PageRank citation ranking: bringing order to the web", Stanford InfoLab Technical Report (1999). |
Last modified: 2017 Mar 30.
Source: http://www.math.ucsd.edu/~dmeyer/teaching/180Bwinter17.html