Instructor

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

Jong Soo Lee

        According to the official Rice web page.
        Tuesday Thursday   9:25-10:40 am, Room RH 305 in Rayzor Hall

Problem sessions (weekly)

Office hours:

    Monday 5:15 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

20%  QUIZ
30%  Midterm EXAM
30%  Last EXAM
20%  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 proof)
    
• 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 proof0
    
• Branching processes
  • definition, extinction probability (in terms of 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
      
  • Ergodicity: Know:
    
    • time-average property for: f(x) bounded, irreducible pos recurrent MC (with proof using LLN)
    • def of Ergodicity, Mixing property and implication on ergodicity
      
• 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 life time and 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 for all and Chapman-Kolmogorov for first two)
    
    • Poisson renewal process (independent increments)
    • Wiener process  / Brownian motion via Gaussian transition densities
    • Ornstein/Uhlenbeck as contin-time Gauss-Markov process
  • Continuous-time Markov Chains
    
    • Definition, holding times
    • Know and handle in simple applications: Condition for stability (no explosion)
      
    • Ex: Birth-Death process
      • Definition, transition proba matrix, holding times
      • understand the minimum of two independent exponential r.v.
        
    • state and solve backward and forward equations for Birth-Death-process
      
• Brownian motion Bt
  
  • Definition; auto-covariance function  E[ Bt Bs ] = sigma^2 min(t,s)
    
  • Construction via mid-points:
    • know the idea of mid-point replacement is a dyadic iterative refinement
      
    • know that the limit a.s. has a continuous paths
      
  • Simple properties
    • Markov (with proof, using independent increments)
    • B(t+s) - Bs; -Bt  are again Brownian motions (with proof, using defining properties)
    • state the reflection principle
    • know the distribution of  Mt = sup( Bs: 0<s<t )