**Module leader**: Dr Zorana Lazic **Lectures**: Monday 9-10am, OC1.05; Thursday 9-10am, OC1.05 **Example Classes**: Tuesday 2pm/ Friday 4pm, Weeks 2, 4, 6, 8, 10 **Tutorials**: Term 2, week 3; week 5; week 7; week 9, Thu 13:00 - 14:00, OC0.05 **Assessment**: 8 assignments due on Thursday 1pm weeks 3 - 10. Questions released on Thursday weeks 2- 9. **Workspace**: [[ST227 Stochastic Processes Workspace.canvas|ST227 Stochastic Processes Workspace]]. **Course Summary**: TBC ---- # 1. Introduction to Stochastic Processes # 2. (Discrete-time, time homogeneous) Markov Chains See [[Discrete-time Markov chains]]. # 3. Properties of Markov Chains Definitions 3.1.1 - 3.1.4: [[Communicating classes in discrete-time Markov Chain]]. Lemma 3.1.2.: Proposition 2.1: [[Communicating states in Markov Chains have Equal Period]]. [[Expected number of visits in discrete-time Markov chains]]. # 4. Long Term Behaviour of Markov Chains An irreducible transient chain does no admit stationary distribution as any invariant measure of it is zero. A state $j\in S$ is transient if and only if, starting from $j$, the expected number of visits to $j$ is finite or equivalently, $\sum_{n=0}^{\infty} P_{jj}^{n}< \infty$. Now for all $i\in S$, $P_{ii}^{n+1} \geq P_{ji}P_{ij}^{n}$ yields that $\sum_{n=0}^{\infty} P_{ij}^{n} < \infty$ which implies $P_{ij}^{n} \to 0$ as $n\to \infty$. Suppose $\pi$ is a invariant measure on $P$. Then for all natural numbers $n$, $\pi = \pi P^{n}$ which means for $\pi_{j} = \lim_{ n \to \infty } \sum_{i \in S}\pi_{i}P_{ij}^{n} = \sum_{i\in S} \pi_{i} \lim_{ n \to \infty }P_{ij}^{n} = 0$(don't you need uniform convergence or something like this to take limit inside? summation is integration wrt to the counting measure). Combining **Proposition 4.1.1/2** with [[Finite, irreducible discrete-time Markov chains are recurrent]] yields that finite, irreducible DTMCs are positive recurrent. **Proposition 4.1.3/4**. [[Existence and uniqueness of stationary distribution for irreducible, positive recurrent discrete-time Markov chains]]. We now consider the $P^{n}$ in the limit. Note that if an irreducible chain is periodic then limit of $P^{n}$ does not exist. Otherwise, regardless of the initial distribution $\lambda$, $\mathbb{P}_{\lambda}(X_{n}=j) = \frac{1}{m_{j}}$. **Proposition 4.2.1/2.** [[Long term behaviour of discrete-time Markov chains]]. **Theorem 4.3.1.** [[Ergodic theorem for discrete-time Markov chains]]. Compare and contrast 4.3.1 and 4.2.1/2. # 5. Branching Processes **Definition 5.1.1.** [[Branching Process]]. # 6. Time Reversal **Proposition 6.1.1/2**: [[Time-Reversal of irreducible discrete-time Markov Chains with Stationary Initial Distribution]]. **Proposition 6.2.1/2.** [[Equivalence of detailed balance and reversibility for discrete-time Markov chains]]. ### 6.3 Random walks on graphs (optional)