Markov Processes and Applications

Cover Title page PREFACE 1 Simulations and the Monte Carlo method Introduction 1.1 Description of the method 1.2 Convergence theorems 1.3 Simulation of random variables 1.4 Variance reduction techniques 1.5 Exercises 2 Markov chains Introduction 2.1 Definitions and elementary properties 2.2 Examples 2.2.1 Random walk in E = Z^d 2.2.2 Bienayme–Galton–Watson process 2.2.3 A discrete time queue 2.3 Strong Markov property 2.4 Recurrent and transient states 2.5 The irreducible and recurrent case 2.6 The aperiodic case 2.7 Reversible Markov chain 2.8 Rate of convergence to equilibrium 2.8.1 The reversible finite state case 2.8.2 The general case 2.9 Statistics of Markov chains 2.10 Exercises 3 Stochastic algorithms Introduction 3.1 Markov chain Monte Carlo 3.1.1 An application 3.1.2 The Ising model 3.1.3 Bayesian analysis of images 3.1.4 Heated chains 3.2 Simulation of the invariant probability 3.2.1 Perfect simulation 3.2.2 Coupling from the past 3.3 Rate of convergence towards the invariant probability 3.4 Simulated annealing 3.5 Exercises 4 Markov chains and the genome Introduction 4.1 Reading DNA 4.1.1 CpG islands 4.1.2 Detection of the genes in a prokaryotic genome 4.2 The i.i.d. model 4.3 The Markov model 4.3.1 Application to CpG islands 4.3.2 Search for genes in a prokaryotic genome 4.3.3 Statistics of Markov chains Mk 4.3.4 Phased Markov chains 4.3.5 Locally homogeneous Markov chains 4.4 Hidden Markov models 4.4.1 Computation of the likelihood 4.4.2 The Viterbi algorithm 4.4.3 Parameter estimation 4.5 Hidden semi-Markov model 4.5.1 Limitations of the hidden Markov model 4.5.2 What is a semi-Markov chain? 4.5.3 The hidden semi-Markov model 4.5.4 The semi-Markov Viterbi algorithm 4.5.5 Search for genes in a prokaryotic genome 4.6 Alignment of two sequences 4.6.1 The Needleman–Wunsch algorithm 4.6.2 Hidden Markov model alignment algorithm 4.6.3 A posteriori probability distribution of the alignment 4.6.4 A posteriori probability of a given match 4.7 A multiple alignment algorithm 4.8 Exercises 5 Control and filtering of Markov chains Introduction 5.1 Deterministic optimal control 5.2 Control of Markov chains 5.3 Linear quadratic optimal control 5.4 Filtering of Markov chains 5.5 The Kalman–Bucy filter 5.5.1 Motivation 5.5.2 Solution of the filtering problem 5.6 Linear–quadratic control with partial observation 5.7 Exercises 6 The Poisson process Introduction 6.1 Point processes and counting processes 6.2 The Poisson process 6.3 The Markov property 6.4 Large time behaviour 6.5 Exercises 7 Jump Markov processes Introduction 7.1 General facts 7.2 Infinitesimal generator 7.3 The strong Markov property 7.4 Embedded Markov chain 7.5 Recurrent and transient states 7.6 The irreducible recurrent case 7.7 Reversibility 7.8 Markov models of evolution and phylogeny 7.8.1 Models of evolution 7.8.2 Likelihood methods in phylogeny 7.8.3 The Bayesian approach to phylogeny 7.9 Application to discretized partial differential equations 7.10 Simulated annealing 7.11 Exercises 8 Queues and networks Introduction 8.1 M/M/1 queue 8.2 M/M/1/K queue 8.3 M/M/s queue 8.4 M/M/s/s queue 8.5 Repair shop 8.6 Queues in series 8.7 M/G/∞rqueue 8.8 M/G/1 queue 8.8.1 An embedded chain 8.8.2 The positive recurrent case 8.9 Open Jackson network 8.10 Closed Jackson network 8.11 Telephone network 8.12 Kelly networks 8.12.1 Single queue 8.12.2 Multi-class network 8.13 Exercises 9 Introduction to mathematical FInance Introduction 9.1 Fundamental concepts 9.1.1 Option 9.1.2 Arbitrage 9.1.3 Viable and complete markets 9.2 European options in the discrete model 9.2.1 The model 9.2.2 Admissible strategy 9.2.3 Martingales 9.2.4 Viable and complete market 9.2.5 Call and put pricing 9.2.6 The Black–Scholes formula 9.3 The Black–Scholes model and formula 9.3.1 Introduction to stochastic calculus 9.3.2 Stochastic differential equations 9.3.3 The Feynman–Kac formula 9.3.4 The Black–Scholes partial differential equation 9.3.5 The Black–Scholes formula (2) 9.3.6 Generalization of the Black–Scholes model 9.3.7 The Black–Scholes formula (3) 9.3.8 Girsanov’s theorem 9.3.9 Markov property and partial differential equation 9.3.10 Contingent claim on several underlying stocks 9.3.11 Viability and completeness 9.3.12 Remarks on effective computation 9.3.13 Historical and implicit volatility 9.4 American options in the discrete model 9.4.1 Snell envelope 9.4.2 Doob’s decomposition 9.4.3 Snell envelope and Markov chain 9.4.4 Back to American options 9.4.5 American and European options 9.4.6 American options and Markov model 9.5 American options in the Black–Scholes model 9.6 Interest rate and bonds 9.6.1 Future interest rate 9.6.2 Future interest rate and bonds 9.6.3 Option based on a bond 9.6.4 An interest rate model 9.7 Exercises 10 Solutions to selected exercises 10.1 Chapter 1 Exercise 1.5.1 Exercise 1.5.2 Exercise 1.5.5 Exercise 1.5.7 Exercise 1.5.8 10.2 Chapter 2 Exercise 2.10.2 Exercise 2.10.5 Exercise 2.10.6 Exercise 2.10.7 Exercise 2.10.8 Exercise 2.10.9 Exercise 2.10.10 Exercise 2.10.12 Exercise 2.10.14 Exercise 2.10.16 Exercise 2.10.18 Exercise 2.10.19 Exercise 2.10.22 10.3 Chapter 3 Exercise 3.5.1 Exercise 3.5.2 10.4 Chapter 4 Exercise 4.8.1 10.5 Chapter 5 Exercise 5.7.2 10.6 Chapter 6 Exercise 6.5.2 Exercise 6.5.4 Exercise 6.5.6 10.7 Chapter 7 Exercise 7.11.1 Exercise 7.11.3 Exercise 7.11.5 Exercise 7.11.6 Exercise 7.11.7 Exercise 7.11.8 Exercise 7.11.9 10.8 Chapter 8 Exercise 8.13.2 10.9 Chapter 9 Exercise 9.7.1 Exercise 9.7.3 References Index