Lecture information 2017

• Lecture 8 (21/4)

  Slides and lecture notes.

  We continued the discussion on dynamical systems and recalled Birkhoff's theorem. An ergodic dynamical system was defined as one for which the σ-field of invariant sets is trivial and an invariant distribution π was called P-ergodic if the law of the canonical chain induced by π yields an ergodic dynamical system with respect to the shift operator. It was left as an exercise to the students to show that the limit in Birkhoff's theorem is deterministic in the ergodic case. A Birkhoff theorem for Markov chains was obtained readily under the assumption that the initial distribution is P-ergodic, and the rest of the lecture aimed at finding conditions for P-ergodicity. The main result of the lecture was the conclusion that the presence of non-trivial invariant sets allows mutually singular invariant distributions to be constructed. As a direct corollary, the existence of a unique invariant distribution implies P-ergodicity. A key ingredient of the proof was an elegant lemma stating a zero-one law for invariant sets. Finally, we used the central limit theorem for square integrable martingale difference sequences to derive a central limit theorem for Markov chain path averages under the assumptions of a unique invariant distribution and the existence of a solution of the Poisson equation associated to the objective function. Here the Birkhoff theorem for Markov chains derived in the first part of the lecture was (in the shape of the law of large numbers) used for deriving the asymptotic variance.

• Lecture 7 (20/4)

  Lecture notes.

  During the exercise class preceding this lecture I spent some time on completing the proof of the existence of an invariant measure for general phi-irreducible recurrent chains. I also discussed briefly Harris recurrence, which is a stronger notion of recurrence than that considered so far. The aim of Lecture 7 was twofold: to find conditions guaranteeing the existence of a unique invariant probability measure and to introduce dynamical systems. The latter form an important tool for the derivation of the limit results obtained in the coming lecture. When it concerns the first aim it was established, via Kac's formula, that a sufficient condition for positive recurrence is a uniform bound on the expected return time to an accessible small set. Even though this condition appears to be hard to check, it is indeed implied by a considerably more straightforward condition assuming the drift towards a small set. The proof of the sufficiency of this drift condition, which can be checked readily for many models of interest, was based on Doob's optional stopping theorem for super martingales.

• Lecture 6 (17/3)

  Lecture notes.

  Continued the discussion on the split chain and established that the pseudo-atom is indeed accessible as long as the underlying small set is so (otherwise, the splitting construction would not be very useful). The proof is found in the notes of Lecture 5. In addition, using the split chain embedding, we established the recurrence-transience dichotomy for general phi-irreducible chains. Not surprisingly, it turned out that the embedded chain is recurrent if and only if the split chain is recurrent (and transient otherwise). Moreover, we started to discuss the existence of invariant measures for recurrent phi-irreducible chains, and stated an important theorem saying that such an invariant measure π always exists and that any other invariant measure assigning a finite mass to the small set C is propotional to π; however, due to lack of time, the proof was postponed to the next meeting.

• Lecture 5 (16/3)

  Lecture notes.

  Until now we have dealt exclusively with atomic chains. However, many Markov chains used in practice do not possess atoms, and in order to deal with the general case we introduced in this lecture the notion of small sets. It can in fact be shown [Jain, N and Jamison, B. (1967). Contributions to Doeblin's theory of Markov processes. Z. Wahrsch. Verw. Geb., 8, 19-40] that all phi-irreducible chains admit accessible small sets. For our running example, the Metropolis-Hastings sampler, all compact sets are small if the target and proposal transition densities are positive and continuous (see the lecture notes). Based on such a small set C it is possible to embed the chain of interest into a larger split chain admitting an atom (sometimes referred to as "pseudo-atom") based on C. Using this atomic split chain we will in the coming lectures be able to establish a number of fundamental stability properties of the embedded chain on interest. The purpose of this lecture was to grasp conceptually the splitting construction (which was a part of the PhD thesis of Esa Nummelin!) and to establish mathematically the embedding. I planned to establish the accessibility of the pseudo-atom, but postponed this to Lecture 6 due to lack of time.

• Lecture 4 (3/3)

  Lecture notes.

  Continued the discussion on atomic chains with focus on the existence of invariant measures. It turned out that for a phi-irreducible chain with an accessible atom, we can always construct an invariant measure using a measure of the expected time spent in the atom (the occupation time). In addition, the invariant measure is unique in the sense that all invariant measures giving finite mass to the atom can be shown to be proportional to this occupation measure. During the coming lectures, this fundametal result will be extended to general phi-irreducible chains using splitting techniques and pseudo-atoms. In addition, we will also provide conditions for positivity, i.e., the existence of a unique probability measure.

• Lecture 3 (2/3)

  Lecture notes.

  Introduced the concepts of accessibility and phi-irreducibility, and related these to the notion of irreducibility as we know it from the countable case. In addition, we showed that it is always possible to obtain a maximal irreducibility measure by transforming an irreducibility measure by the resolvent kernel. Introduced recurrent and transient sets. The main result for irreducible chains is the co-called recurrence-transience dichotomy saying that for a phi-irreducible chain, either all the accessible sets are recurrent - in which case we call the chain recurrent - or the state space of the chain can be covered by a countable collection of transient sets - in which case we call the chain transient. As a first step towards a proof of the dichotomy for general phi-irreducible chains, we established ditto in the case of an accessible atom, which is a set of states from which transtions follow the same distribution. During the next lectures this result will be extended to general chains using splitting techniques and pseudo-atoms.

• Lecture 2 (17/2)

  Slides and lecture notes.

  Introduced the notions of invariance, stationarity and reversibility. Recalled the concepts of stopping times and coordinate processes. Stated an existence theorem saying that for a given Markov kernel P and a given initial distribution μ on some measurable space, there exists a unique law on the canonical space under which the coordinate process is a Markov chain with kernel P and initial distribution μ. This Markov chain is referred to as the canonical chain. The proof, which is based on Caratheodory's existence theorem, is beyond the scope of the course, but is found in the appendix of the notes above. Introduced the shift operator and established the weak and strong Markov properties. The latter will be a key ingredient in the coming developments.

• Lecture 1 (16/2)

  Slides and lecture notes.

  Provided som general course information (see the slides) and recalled the notions of stochastic processes and filtrations. Introduced the concept of kernels and described 4 kinds of kernel operations. Defined homogeneous Markov chains with kernel P and established that a stochastic process is a Markov chain with kernel P and initial distribution μ if and only if the finite dimensional distributions of the process are of form μ⊗P^⊗n, where ⊗ denotes tensor product (sufficiency was left as an exercise). Planned to say something about invariance, stationarity and reversibility, but saved this to Lecture 2.