Solution 9 available

Last update Dec 1. 2006

Instructor

Dr. Rudolf Riedi
Duncan Hall 2082, 713 / 348 3020,
Email for appointments

Alireza Keshavarz-Haddad

TR 09:25AM - 10:40AM HZ 119  (Hermann Brown)     

see also Time (official Rice page)
Location (Rice map)

Office hours:

    Monday 1-2 pm pm  (DH 2082), or by appointment

Outline and suggested topics

• Preliminaries (incl. probability generating functions, simple random walks and branching processes, stopping times, Wald equality)
• QUIZ (allowed: one sheet = two pages of personal notes)
• Discrete-time Markov chains (joint distributions, transition probability, irreducibility, absorbing, transient and recurrent states, invariant measures, stationarity and equilibrium, ergodicity (time averages, mixing))
• Poisson Processes (including thinned and marked Poisson processes)
• Midterm EXAM (open-notes, closed-books)
• Renewal Processes (more on Poisson processes, Renewal theorem)
• Continuous-time Markov chains (Holding times, Chapman-Kolmogorov and Consistency, backward and forward equations)
• Brownian motion (construction via mid-points, self-similarity and scaling, Brownian bridges)
• Second EXAM (open-notes)

Textbook

• S. Resnick, `Adventures in Stochastic Processes'.

The course will closely follow this book; it is available at the campus bookstore.
Also, Amazon quotes currently (4/2005) a prize reduction by 14%

• Ross, `Introduction to Probability Models'
• A. Papoulis, `Probability, Random Variables, and Stochastic Processes'
• W. Davenport, `Probability and Random Processes'
• W. Feller, `An Introduction to Probability Theory and Its Applications'
• P. Billingsley, `Probability and Measure'

Grading

15%  QUIZ
30%  Midterm EXAM
30%  Last EXAM
25%  Homework

Classes and Reading assignments
 

This doubles as a calendar for the course.

Homework
(tex-source and solutions restricted to Rice University)
This file is needed to latex the source.

Late Homework Policy
 

Homework is due at the beginning of class on the due date. After the due date, but before solutions are handed out, homework can be turned in for 50% credit. In this case, please slip your homework under the instructors's office door, or bring it to class. After solutions are handed out, 0% credit will be issued. You are encouraged to work in groups for homeworks but you will hand in your own solution which you are expected to understand.

Tests
 

Knowledge Milestones aquired in this course

• Probability generating functions (pgf)
  
  • Definition, Radius of convergence, relation to mean and higher moments
  • Compounding formula (with derivation)
    
• Simple random walk
  • Definition
  • first hit at 1, first return to 0
    • be able to derive pgf
    • Know and derive formula for mean
  • Wald identity for stopping times (with proof)
    
• Branching processes
  • definition, be able to compute extinction probability from pgf
    
• Discrete-time Markov chains 
  • Definition, transition probability,
    
  • know: def of stationary, time-homogenous, Chapman-Kolmogorov (with proof)
    
  • Def: accessible, commuting state; Class; Irreducibility; Closed set of states.
    
  • Formulate: Dissection Principle
  • def: Absorbing, transient and recurrent (null / positive) states
  • Equivalent conditions for recurrent and for transient in terms of n-step transitions
  • def of  Canonical representation and Solidarity properties
    
  • Know:
    
    • recurrent classes are closed;
      
    • example of closed transient classes
    • Finite, closed sets contain recurrent states
    • Classification of states for Simple Random Walk and for Branching Processes
      
  • Invariant measures
    • Definition of invariant measures and of stationary distributions
    • Know criteria for existnence and/or for uniqueness of invariant measures and/or stat. distr.
    • Know formula for stat distr in terms of mean return times for irred. pos recurrent MC
  • Limiting distribution
    • definition
    • relation to stationary distribution
    • computation of limiting distribution using invariance properties
  • Time-averages for f(x) bounded, irreducible pos recurrent MC
    • understand connection to LLN and Dissection Principle
    • compute limits of time averages in terms of the stationary distribution
• Poisson Point Processes
  
  • Definition of a Point Process (PP)
    
  • Notion of randomly scattered PP, special case of Poisson Point Process (PRM)
    
  • Transformation property
    
    • formula for the transformed process (with proof)
    • transform inhomogeneous PRM on the real line to a homogeneous PRM
      
  • Marked  and Thinned Poisson processes
    
    • proof that they are PRM (using the conditioning on the number of points)
    • formula's for their intensity measures
  • Solve simple queueing problems from Resnick/lecture notes
  • Laplace functional for PRM
    • formula in terms of the control measure (with proof)
    • know construction of PRM via iid points conditioned on their number
    • on positive line: know order statistics property of points conditioned on their number
  • Compound Poisson Process: Laplace functional
• Renewal Processes Nt  with interarrival times Xn
  
  • Definition, pure and delayed;
    
  • pgf of Nt
  • renewal equations (with derivation) for
    
    • mean function
    • distribution of life time
    • distribution of residual life time
  • state theorem on existence and uniqueness of solutions of renewal equations
  • hom. Poisson process on the positive line: know formulas for
    
  • mean function,
    
  • interarrival times (expon)
  • distrib. of residual life time (expon)
    
  • renewal version SLLN (with proof using standard SLLN):  Nt / t  ->   1/ E[ X1 ]
    
  • State Renewal Theorem
    • basic: E[Nt] / t  -> 1 / E[ X1 ]
    • Blackwell:  E[ N(t+b) - Nt ]  -> b / E[ X1 ]
  • Stationary renewal sequence
    • definition in terms of residual life
      
    • equivalent condition: E[Nt]  = t / E[ X1 ]
    • equivalent condition: form of initial delay distribution
      
• Continuous-time Markov processes
  
  • Definition
  • explain and compute conditional probabilities in discrete and continuous cases
    
  • explain and compute Chapman-Kolmogorov discrete and continuous cases
  • relate Chapman-Kolmogorov to Consistency (existence of contin-time MC)
  • Examples (verify Markov property and Chapman-Kolmogorov)
    
    • Poisson renewal process (independent increments)
    • Wiener process  / Brownian motion via Gaussian transition densities
  • Continuous-time Markov Chains
    
    • Definition, holding times
    • Ex: Birth-Death process
      • Definition, transition proba matrix, holding times
      • understand the minimum of two independent exponential r.v.