Statistics 150: Stochastic Processes-- Spring 2009

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

Office hours: Thursdays 9:00 - 10:00 in 303 Evans

GSI: Jonathan Grib, Department of Statistics, U.C. Berkeley.

Office hours: Tuesday and Wednesday 5PM - 7PM. Evans 344.

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

Midterm Exam:   Thursday March 12, in class.
Final Exam:   Thursday 5/14/09 12:30-3:30pm   200 Wheeler. Two pages of notes allowed. Calculators OK but not necessary. [.pdf]

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 and Homework Schedule

Week 1

  • 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/29) P. 79: 3.3, 3.4. P. 85: 4.3, 4.4. 4.6

Week 2

  • 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/5) P. 94: 5.1, 5.2, 5.3, 5.4, 5.5

Week 3

  • 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/12) P. 100 1.3, 1.4. P 105 2.4. P 114 3.5. P 115 3.9

Week 4

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

Week 5

Week 6

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

Week 7

  • Lecture 13: Branching processes [.pdf]
  • Lecture 14: Branching processes and Random Walks [.pdf]
    • No Homework.

Week 8

  • Lecture 15: March 10: Midterm Review. Sample midterm exam: [.pdf]
  • Lecture 16: March 12: Midterm Exam. In class. [.pdf]
    Closed book. Bring one page (single side) of notes and turn in with the exam.
  • Midterm Scores [.pdf]
  • Homework 7: Provide solutions to all problems on the midterm [.pdf] which you did not solve during the exam. For those with only two or three problems left to solve, add the following:
  • Challenge Problem: In the setting of Problem 4 of the Midterm, let u(1) := 1/p(0) and u(j):= f(1,j)/f(j,j) for j = 2, 3, ..... Explain why u(j) is the expected number of hits on state j, starting in state 1. Deduce that the sum of u(j) over j = 1,2, ... equals 1/(1 - μ). Find u(j) as explicitly as you can for j = 1, 2, 3, .... in terms of p(0), p(1), .... Is there a pattern, a recursion, or a formula? As a check on your evaluations of the u(j), confirm algebraically that their partial sums remain less than 1/(1 - μ). Can you confirm the evaluation of the infinite sum by another method?

Week 9

  • 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/2: P 211 1.3 , P 214 1.13, p 256 4.3, P257 4.6, P258 4.8

Week 10

  • Lecture 19: Stationary Markov Chains [.pdf]
  • Lecture 20: Markov Chains: Examples [.pdf]
  • Homework 9: due 4/9: P 296 3.6, P 297 3.8 , P 309 4.4, p 315 5.2 p 329 6.3

Week 11

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

Week 12

  • 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/23: P 407 6.2, 6.3, 6.4 and P 556 2.4, 2.5

Week 13

  • Lecture 25: Renewal Theory [.pdf]
  • Lecture 26: Brownian motion [.pdf]
  • Homework 12: due 4/30: 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

Week 14

  • Lecture 27: Hitting Probabilities for Brownian Motion
    [.pdf]
  • Lecture 28: Brownian bridge
    [.pdf]
  • Homework 13: due 5/7: Page 489 1.5, Page 497 2.1, Page 506 3.1, Page 522 4.2 and 4.3

Week 15

  • Lecture 29: Review 2006 Final
  • Lecture 30: Review