Topic outline

  • General

    Collapse all Expand all
    • Announcements Forum
    • Student Forum

      This forum is available for everyone to post messages to. You can raise mathematical and organisational questions related to the module. You are encouraged to post to this forum and I will check it regularly and respond. You should also feel free to reply to other students.

    • Summary of Learning Sessions

      • Lectures: Tuesday 12-1, Thursday 3-5 in Skeel LT. Large group session with interactive elements. Main place for delivery of mathematical material. In-person attendance strongly encouraged but will be recorded and live-streamed as a back-up.
      • Seminars: See your timetable for your allocated session. Smaller group session to go through examples which illustrate the theory, give more explanations, and review material. Tell me what you want to cover in these.
      • Learning Support Hour: Thursday 1:00-2:00 in Maths Social Hub (as part of the Learning Cafe). An opportunity for individual help and feedback. Come along with any questions or issues about the module.
    • Module Information File

      Key information about how the module will run.

      54.4 KB

  • Lecture Notes

    Notes covering all the material in the module will appear here. The document of notes will grow as we move through the module, with sections added in advance of the corresponding lectures.

    Please let me know if you spot any mistakes or things which could be explained more clearly.


  • Week 1 - Markov Chain Basics

    • The lectures are based on sections 1 and 2 of the notes. The key topics are:

      • The definition of (discrete-time, homogeneous) Markov chain
      • Transition probabilities
      • Representing Markov chains with transition graphs and transition matrices
    • Warm-up Problems File

      This module builds on your first and second year probability modules. Have a go at this sheet to check you are up to speed with the background material you will need. This sheet will be used in the Week 1 seminars.

      45.2 KB
    • Mini-quiz 1

      Mini-quiz on Markov chain basics (transition probabilities and transition matrices) based on the material in Week 1.

    • Problem Sheet 1 File

      This sheet will not be assessed. We will discuss selected parts in the seminars in Week 2.

      112.4 KB
    • Problem Sheet 1 Solutions File
      144.9 KB

  • Week 2 - First Step Analysis

    • The lectures are based on section 3 of the notes. The key topics are:

      • The idea of an absorbing state
      • Using first step analysis to find expectations and probabilities related to absorption

    • Mini-quiz 2

      Mini-quiz on absorbing states and first-step analysis based on the material in Week 2.

    • Problem Sheet 2 File

      This sheet will not be assessed. We will discuss selected parts in the seminars in Week 3.

      73.6 KB
    • Problem Sheet 2 Solutions File
      130.4 KB

  • Week 3 - Long-term Behaviour I

    • The lectures are based on sections 4.1-4.4 of the notes. The key topics are:

      • Multi-step transition probabilities and their connection to matrix powers
      • The definition of limiting and equilibrium distributions

    • Mini-quiz 3

      Mini-quiz on limiting and equilibrium distributions based on the material in Week 3.

    • Problem Sheet 3 File

      This sheet will not be assessed (but see below for one part to submit). We will discuss selected questions in the seminars in Week 4.

      89.3 KB
    • Problem Sheet 3 Solutions File
      115.5 KB
    • Problem Sheet 3 Question 1 Assignment

      This is the place to enter your answer to Question 1 from problem Sheet 3 by 5pm Friday 20 October 2023.


  • Module Description

    This is an advanced module in probability. It covers the mathematical analysis of processes which evolve randomly over time. For example, imagine a person wandering randomly through a maze; we can't predict their exact route but we can consider questions such as `What is the expected time it takes to reach the centre?'. One important class of processes studied are Markov chains. Roughly speaking, these are processes where the next step depends only on your current state but not how you got there. The module will cover both discrete-time processes (which evolve at fixed time steps) and continuous-time processes (which evolve continuously through time). The content is mainly theoretical but we will get a taste of how the models discussed do have applications in physical and life sciences and economics.  This module is probabilistic rather than statistical. Analysing processes which evolves over time from a statistical perspective is covered in the module Time Series. The content will build on previous probability modules; you will need to be comfortable with conditional probability and the basic of random variables. We will also see (perhaps surprisingly) that linear algebra and differential equations appear as tools to analyse random processes.

  • Week 4 - Long-term behaviour II

    • The lectures are based on sections 4.5-4.9 of the notes. The key topics are:

      • Irreducible and regular Markov chains
      • Conditions for existence of limiting and equilibrium distributions

    • Mini-quiz 4

      Mini-quiz on regular and irreducible chains based on the material in Week 4.

    • Problem Sheet 4 File
      83.4 KB
    • Problem Sheet 4 Solutions File
      125.8 KB

  • Week 5 - More on limiting and equililbrium distributions/Recurrence and Transience

    • This week we will finish off the section on limiting and equilibrium distributions (Theorem 4.9 and Section 4.10 of the notes) and start the next topic which is recurrence and transience (sections 5.1-5.2 of the notes). The key topics are:

      • Equilibrium distributions and expected proportion of time in each state
      • Limiting and equilibrium distributions for infinite S
      • Communicating classes of a chain
      • First return probabilities, recurrence and transience

    • Mini-quiz 5

      Mini-quiz on communicating classes, recurrence and transience based on the material in Week 5.

    • Problem Sheet 5 File
      102.5 KB
    • Problem Sheet 5 Solutions File
      167.1 KB
    • Assessment 1 (small update to 1(b) 26/10/2023) File

      This is the first sheet for Assessment. Details of what you need to do are in the document. Submission will be via the tool in the Week 7 topic (to appear). This assessment contributes 10% towards your mark for the module.

      115.7 KB
    • Solutions to Assessment 1 File
      103.5 KB

  • Week 6 - Recurrence and Transience

    • This week we will finish off the topic of recurrence and transience (sections 5.3-5.6 of the notes). The key topics are:

      • Properties of recurrence and transience
      • Positive recurrence and null recurrence
      • First return times and their connection with the equilibrium distribution

    • Mini-quiz 6

      Mini-quiz on positive recurrence, null recurrence and transience, and the connection with equilibrium distributions based on the material in Week 6.

    • Problem Sheet 6 File
      107.7 KB
    • Problem Sheet 6 Solutions File
      147.0 KB

  • Week 7 - The Week formerly known as Reading Week

    • This week there are no timetabled teaching activities.

      Here are some things you could do:

      • Submit your solution to Assessment 1.
      • Make sure your notes for the first half of the module are in good shape and you have attempted most of the problem sheet questions and mini-quizzes.
      • Read the Exam Guidance document. Have a go at the task described in the last section of the section on Preparation.
      • Reflect on how the first half of term went for you. Are there things you should do differently  in the second half of term? Can you identify some concrete actions to help you study more effectively?
      • Attend the Year Programme Director session on Wednesday 8 November (see email from Hugo Maruri-Aguilar)
      • Spend some time doing things which you find restful and fun so you are full of energy and enthusiasm for the second half of term.
    • Assessment 1 (Submit Solutions for Feedback) Assignment

      Please upload your solutions to Assessment 1 here by 5:00pm on Tuesday 7 November 2023.

      You should submit your work as a PDF file which can be either a scan of a handwritten document or electronically written on a tablet (but not typed in a word processor).

      This Assessment component will contribute 10% of your final mark for the module.

      Late submissions will not be accepted.

  • Week 8 - Poisson Process Definition

    • In the second half of term we study continuous-time processes.

      This week we look at our first (and the most fundamental) continuous-time stochastic process the Poisson process (sections 7.1-7.3 of the notes). The key topics are:

      • Definition of the Poisson process (in two equivalent ways)
      • Simple calculations of probabilities relating to the Poisson process
      • New processes from old: Superposition and thinning

    • Mini-quiz 7

      Mini-quiz on continuous-time stochastic processes and the basics of the Poisson process based on the material in Week 8.

    • Problem Sheet 7 File
      62.5 KB
    • Problem Sheet 7 Solutions File
      124.4 KB

  • Week 9 - More on the Poisson Process

    • This week we continue to study the Poisson process looking at some more properties of it (sections 7.4-7.4 of the notes). The key topics are:

      • Arrival and Interarrival times -- their definition and calculations involving  them.
      • The evolution of the process in time \([0,t]\) conditioned on \(X(t)=n\)


    • Mini-quiz 8

      Mini-quiz on more properties of the Poisson process based on the material in Week 9.

    • Problem Sheet 8 File
      119.3 KB
    • Problem Sheet 8 Solutions File
      131.6 KB
    • Assessment 2 (small update to Question 1 30/11/2023) File

      This is the second sheet for Assessment. Details of what you need to do are in the document. Submission will be via the tool in the Week 11 topic (to appear). This assessment contributes 10% towards your mark for the module.

      See the Student Forum for posts answering some student questions on this Assessment.

      126.4 KB
    • Solutions to Assessment 2 File
      49.9 KB

  • Week 10 - Birth Processes

    • This week we generalise the Poisson process to our second continuous-time random process, the birth process. We will see two ways of thinking of this process (both related to the Poisson process) and and see some properties. This is in sections 8.1-8.5 of the notes. The key topics are:

      • The Birth process as a way of modelling growth of a population
      • Definition in terms of infinitesimal description
      • Distribution of interarrival times for a birth process
      • Deriving differential equations for a birth process


    • Mini-quiz 9

      Mini-quiz on more properties of the Birth process based on the material in Week 10.

    • Problem Sheet 9 File
      106.6 KB
    • Problem Sheet 9 Solutions File
      145.4 KB

  • Week 11 - Continuous-time Markov Chains

    • This week we define continuous-time Markov chains. As for the Poisson process and birth process we will see two ways of thinking of these (infinitesimal generators and exponential holding times). This is in sections 9.1-9.4 of the notes. The key topics are:

      • Definition of continuous-time Markov chains in terms of infinitesimal generator
      • Description in terms of holding times and a discrete-time chain
      • Chapman-Kolmogorov relations in continuous time
      • Deriving the forwards and backwards differential equations


    • Mini-quiz 10

      Mini-quiz on continuous-time Markov chains based on the material in Week 11 and 12.

    • Problem Sheet 10 File
      142.1 KB
    • Problem Sheet 10 Solutions File
      141.5 KB
    • Problem Sheet 10 Question 1 Assignment

      This is the place to enter your answer to Question 1 from Problem Sheet 10 by 5pm Friday 15 December 2023.


    • Assessment 2 (Submit Solutions for Feedback) Assignment

      Please upload your solutions to Assessment 2 here by 5:00pm on Friday 8 December 2023.

      You should submit your work as a PDF file which can be either a scan of a handwritten document or electronically written on a tablet (but not typed in a word processor). Make sure that you follow all the instructions about the form your answers should take in the Assessment task document.

      This Assessment component will contribute 10% of your final mark for the module.

      Late submissions will not be accepted.

  • Module aims and learning outcomes

    • ACADEMIC CONTENT

      This module covers:

      • Markov chains 
      • Poisson processes.
      • Continuous-time stochastic processes.


      DISCIPLINARY SKILLS

      At the end of this module, students should be able to:

      • Specify a given discrete-time Markov chain in terms of a transition matrix and a transition diagram.
      • Calculate n-step transition probabilities.
      • Apply first-step analysis to calculate absorption probabilities and mean time to absorption for a discrete-time Markov chain.
      • State and apply the definition of irreducible and regular Markov chain, and calculate the equilibrium and limiting distributions as appropriate.
      • Assess whether states are recurrent or transient in simple cases.
      • State and apply the definition of the Poisson process, in both axiomatic and infinitesimal form.
      • State and apply a number of definitions and basic results concerning the Poisson process.
      • For pure Birth processes such as the Poisson process, state and use results about interarrival times.
      • For a birth-death process or finite state space continuous time Markov process, derive and apply the backwards and forwards equations, and find the equilibrium distribution. State and use results about sojourn times and the jump chain.


      ATTRIBUTES

      At the end of this module, students should have developed with respect to the following attributes:

      • Explain and argue clearly and concisely.
      • Apply their analytical skills to investigate unfamiliar problems


  • Week 12 - More on Continuous-time Markov Chains

    • This week we finish off continuous-time Markov chains by looking at some examples of using the forwards and backwards differential equations to determine information about the chain. This is in section 9.4-9.5 of the notes. The key topics are:

      • Writing down the forwards and backwards differential equations from the generator
      • Solving them in simple cases
      • Examples of finding limiting behaviour from the differential equations
      This material should fill the Tuesday lecture and half of the Thursday lecture. I will use the remaining time to talk about exam preparation and revision. Let me know if you have any particular requests using the poll below.

      There is no problem sheet this week. Problem Sheet 10 covers this material.



  • Assessment information

    • Assessment Pattern -  Coursework 1 (10%), Coursework 2 (10%), Final Exam (80%)

      Format and dates for the in-term assessments - Coursework 1 due Week 7, Coursework 2 due Week 11 (details to follow)

      Format of final assessment - Your final examination will be on campus.  It will be 3 hours in duration with SpLD accommodations handled separately.  You will be allowed 3 sheets of handwritten A4 notes to bring to the exam.

      Link to past exam papers -  QMPlus Exam Paper repository

      Feedback - 
      • Weekly mini-quizzes for instant formative feedback
      • Written feedback on two substantial Assessed coursework

      Revision and Exam preparation support - See Module Announcement from 28 November 2023

       
    • Exam Guidance File
      148.1 KB

    • Here are solutions to the most recent two past exams (you can find the papers on the repository linked above). You are strongly encouraged to attempt the paper and to check your solutions without looking at these solutions. However, if you get really stuck on a question then it may be useful to have these. For some questions there may be several equally valid answers or aproaches so your answer might be correct even if it doesn’t look exactly the same as mine.

    • January 2022 Exam Solutions File
      117.3 KB
    • January 2023 Exam Solutions File
      139.3 KB

  • Q-Review

  • Lecture Chat

  • Reading List Online