**Instructor: **Jim Pitman, Department of Statistics, U.C. Berkeley.

**Office hours:** TBD in 303 Evans

Weekly homework assignments are drawn from the text
*An Intro to Stochastic Modeling* (3rd ed) by Karlin and Taylor.

**Midterm Exam:**
Thursday March 11,
in class.

**Final Exam:** Thursday 5/13/10 3-6pm

GRADES: Overall
scores will be
computed as follows:

Larger of (0.1 * hwk + 0.4 * midterm + 0.5 * final) and (0.1 * hwk + 0.9 * final).

**Lecture 1:**Overview. Probability spaces, Expected value [.pdf].**Lecture 2:**Conditional Expectation. Wald's Identity. Gambler's ruin for fair coin [.pdf].**Homework 1:**(due 1/28) P. 79: 3.3, 3.4. P. 85: 4.3, 4.4. 4.6

**Lecture 3:**Martingales. Gambler's ruin for biased coin. [.pdf]. Similar notes from a previous year: [.pdf]**Lecture 4: Conditional independence and Markov chains [.pdf]****Homework 2:**(due 2/4) P. 94: 5.1, 5.2, 5.3, 5.4, 5.5

**Lecture 5:**Markov chains. First step analysis I. [.pdf]**Lecture 6:**Markov Chains. First step analysis II. [.pdf]**Additional notes (from a previous year):**Transition Probabilities. Death and Immigration Chain [.pdf]**Homework 3:**(due 2/11) P. 100 1.3, 1.4. P 105 2.4. P 114 3.5. P 115 3.9

**Lecture 7:**Limits of Random Variables [.pdf]**Lecture 8:**First passage and occupation times for random walk [.pdf]**Homework 4:**(due 2/18) P. 130 4.1, 4.2, 4.5, 4.6, 4.10

**Lecture 9:**Waiting for patterns. [.pdf] Reference: Shuo-Yen Robert Li. A Martingale Approach to the Study of Occurrence of Sequence Patterns in Repeated Experiments. Ann. Probab. Volume 8, Number 6 (1980), 1171-1176.**Lecture 10:**Mean occupation times, fundamental (Green) matrix [.pdf]**Homework 5:**(due 2/25) P 168, 6.1, 6.2, 6.3, P 175, 7.1; P 176 7.4.

**Lecture 11:**Return times for random walk [.pdf]**Lecture 12:**Probability Generating Functions [.pdf]**Homework 6:**(due 3/4) P 184, 8.4; P 195 9.4, 9.5, 9.7, 9.8

**Lecture 13:**Branching processes [.pdf]**Lecture 14:**Branching processes and Random Walks [.pdf]

No Homework. Midterm exam next week,

**Lecture 15:**March 10: Midterm Review. Sample midterm exams: 2006 [.pdf] 2009 [.pdf]

**Lecture 16:**March 12: Midterm Exam. In class. Closed book. OK to bring one page (single side) of notes.**Homework 7:**Provide solutions to all problems on the midterm.-
**Midterm:**Problems only: [.pdf]. Problems and solutions: [.pdf]. -
Here are the raw scores on the midterm (47 scores):

[48, 44, 43, 41, 38, 37, 37, 36, 36, 33, 33, 31, 31, 29, 28, 27, 27, 26, 26, 25, 24, 24, 23, 22, 22, 22, 21, 20, 20, 19, 19, 19, 18, 18, 17, 15, 14, 13, 13, 13, 12, 12, 11, 11, 10, 5, 5]

Divide your score by 48 and multiply by 100 to get the value of "midterm" which will be used to compute your overall score according to:

Larger of (0.1 * hwk + 0.4 * midterm + 0.5 * final) and (0.1 * hwk + 0.9 * final).

**Lecture 17:**Long run behaviour of Markov chains. [.pdf] Lecture from a previous course: [.pdf]**Lecture 18:**Long run behaviour of Markov chains: problems. [.pdf]**Homework 8:**due 4/1: P 211 1.3 , P 214 1.13, p 256 4.3, P257 4.6, P258 4.8

**Lecture 19:**Stationary Markov Chains [.pdf]**Lecture 20:**Markov Chains: Examples [.pdf]

**Homework 9:**due 4/8: P 296 3.6, P 297 3.8 , P 309 4.4, p 315 5.2 p 329 6.3

**Lecture 21:**Poisson processes [.pdf]

**Lecture 22:**Continuous time Markov chains [.pdf]**Homework 10:**due 4/15: P 343 1.7, p 354 2.1, p 365 3.1, p 376 ex 4.1, p 377 4.4

**Lecture 23:**Continuous time Markov chains: continued. Notes from a previous year (some overlap with Lec 22)[.pdf]

**Lecture 24:**Queuing models [.pdf]

**Homework 11:**due 4/22: P 407 6.2, 6.3, 6.4 and P 556 2.4, 2.5

**Lecture 25:**Renewal Theory [.pdf]**Lecture 26:**Brownian motion [.pdf]**Homework 12:**due 4/29: P 426 1.3. Deduce from this result the asymptotic equivalence of M(t) and t/E(X) as t tends to infinity, assuming to make the argument easy that F(T) = 1 for some finite T . P 436 3.4, P 456 5.1, P 457 5.4

**Lecture 27:**Hitting Probabilities for Brownian Motion

[.pdf]**Lecture 28:**Brownian bridge

[.pdf]**Homework 13:**(not graded) Page 489 1.5, Page 497 2.1, Page 506 3.1, Page 522 4.2 and 4.3