Markov Processes and Applications Algorithms, Networks, Genome and Finance

by Pardoux, Etienne

• ISBN13: 9780470772713
• ISBN10: 0470772719
• Edition: 1st
• Format: Hardcover
• Copyright: 2009-01-07
• Publisher: Wiley

Summary

"This well-written book provides a clear and accessible treatment of the theory of discrete and continuous-time Markov chains, with an emphasis towards applications. The mathematical treatment is precise and rigorous without superfluous details, and the results are immediately illustrated in illuminating examples. This book will be extremely useful to anybody teaching a course on Markov processes." Jean-FranYois Le Gall, Professor at Universit_ de Paris-Orsay, France.Markov processes is the class of stochastic processes whose past and future are conditionally independent, given their present state. They constitute important models in many applied fields.After an introduction to the Monte Carlo method, this book describes discrete time Markov chains, the Poisson process and continuous time Markov chains. It also presents numerous applications including Markov Chain Monte Carlo, Simulated Annealing, Hidden Markov Models, Annotation and Alignment of Genomic sequences, Control and Filtering, Phylogenetic tree reconstruction and Queuing networks. The last chapter is an introduction to stochastic calculus and mathematical finance.Features include:The Monte Carlo method, discrete time Markov chains, the Poisson process and continuous time jump Markov processes. An introduction to diffusion processes, mathematical finance and stochastic calculus. Applications of Markov processes to various fields, ranging from mathematical biology, to financial engineering and computer science. Numerous exercises and problems with solutions to most of them

Author Biography

Etienne Pardoux, Centre for Mathematics and Informatics, University of Provence, Marseille, France
Professor Pardoux has authored more than 100 research papers and three books, including the French version of this title. A vastly experienced teacher, he has successfully taught all the material in the book to students in Mathematics, Engineering and Biology.

Table of Contents

Preface	p. xi
Simulations and the Monte Carlo method	p. 1
Description of the method	p. 2
Convergence theorems	p. 3
Simulation of random variables	p. 5
Variance reduction techniques	p. 9
Exercises	p. 13
Markov chains	p. 17
Definitions and elementary properties	p. 17
Examples	p. 21
Random walk in E = Zd	p. 21
Bienaymé-Galton-Watson process	p. 21
A discrete time queue	p. 22
Strong Markov property	p. 22
Recurrent and transient states	p. 24
The irreducible and recurrent case	p. 27
The aperiodic case	p. 32
Reversible Markov chain	p. 38
Rate of convergence to equilibrium	p. 39
The reversible finite state case	p. 39
The general case	p. 42
Statistics of Markov chains	p. 42
Exercises	p. 43
Stochastic algorithms	p. 57
Markov chain Monte Carlo	p. 57
An application	p. 59
The Ising model	p. 61
Bayesian analysis of images	p. 63
Heated chains	p. 64
Simulation of the invariant probability	p. 64
Perfect simulation	p. 65
Coupling from the past	p. 68
Rate of convergence towards the invariant probability	p. 70
Simulated annealing	p. 73
Exercises	p. 75
Markov chains and the genome	p. 77
Reading DNA	p. 77
CpG islands	p. 78
Detection of the genes in a prokaryotic genome	p. 79
The i.i.d. model	p. 79
The Markov model	p. 80
Application to CpG islands	p. 80
Search for genes in a prokaryotic genome	p. 81
Statistics of Markov chains Mk	p. 82
Phased Markov chains	p. 82
Locally homogeneous Markov chains	p. 82
Hidden Markov models	p. 84
Computation of the likelihood	p. 85
The Viterbi algorithm	p. 86
Parameter estimation	p. 87
Hidden semi-Markov model	p. 92
Limitations of the hidden Markov model	p. 92
What is a semi-Markov chain?	p. 92
The hidden semi-Markov model	p. 93
The semi-Markov Viterbi algorithm	p. 94
Search for genes in a prokaryotic genome	p. 95
Alignment of two sequences	p. 97
The Needleman - Wunsch algorithm	p. 98
Hidden Markov model alignment algorithm	p. 99
A posteriori probability distribution of the alignment	p. 102
A posteriori probability of a given match	p. 104
A multiple alignment algorithm	p. 105
Exercises	p. 107
Control and filtering of Markov chains	p. 109
Deterministic optimal control	p. 109
Control of Markov chains	p. 111
Linear quadratic optimal control	p. 111
Filtering of Markov chains	p. 113
The Kalman - Bucy filter	p. 115
Motivation	p. 115
Solution of the filtering problem	p. 116
Linear-quadratic control with partial observation	p. 120
Exercises	p. 121
The Poisson process	p. 123
Point processes and counting processes	p. 123
The Poisson process	p. 124
The Markov property	p. 127
Large time behaviour	p. 130
Exercises	p. 132
Jump Markov processes	p. 135
General facts	p. 135
Infinitesimal generator	p. 139
The strong Markov property	p. 142
Embedded Markov chain	p. 144
Recurrent and transient states	p. 147
The irreducible recurrent case	p. 148
Reversibility	p. 153
Markov models of evolution and phylogeny	p. 154
Models of evolution	p. 156
Likelihood methods in phylogeny	p. 160
The Bayesian approach to phylogeny	p. 163
Application to discretized partial differential equations	p. 166
Simulated annealing	p. 167
Exercises	p. 173
Queues and networks	p. 179
M/M/ 1 queue	p. 179
M/M/ 1/ K queue	p. 182
M/M/ s queue	p. 182
M/M/s/s queue	p. 184
Repair shop	p. 185
Queues in series	p. 185
M/G/∞ queue	p. 186
M/G/ 1 queue	p. 187
An embedded chain	p. 187
The positive recurrent case	p. 188
Open Jackson network	p. 190
Closed Jackson network	p. 194
Telephone network	p. 196
Kelly networks	p. 199
Single queue	p. 202
Multi-class network	p. 203
Exercises	p. 203
Introduction to mathematical finance	p. 205
Fundamental concepts	p. 205
Option	p. 206
Arbitrage	p. 206
Viable and complete markets	p. 207
European options in the discrete model	p. 208
The model	p. 208
Admissible strategy	p. 208
Martingales	p. 210
Viable and complete market	p. 211
Call and put pricing	p. 213
The Black-Scholes formula	p. 214
The Black-Scholes model and formula	p. 216
Introduction to stochastic calculus	p. 217
Stochastic differential equations	p. 223
The Feynman-Kac formula	p. 225
The Black-Scholes partial differential equation	p. 225
The Black-Scholes formula (2)	p. 228
Generalization of the Black-Scholes model	p. 228
The Black-Scholes formula (3)	p. 229
Girsanov's theorem	p. 232
Markov property and partial differential equation	p. 233
Contingent claim on several underlying stocks	p. 235
Viability and completeness	p. 237
Remarks on effective computation	p. 238
Historical and implicit volatility	p. 239
American options in the discrete model	p. 239
Snell envelope	p. 240
Doob's decomposition	p. 242
Snell envelope and Markov chain	p. 244
Back to American options	p. 244
American and European options	p. 245
American options and Markov model	p. 245
American options in the Black-Scholes model	p. 246
Interest rate and bonds	p. 247
Future interest rate	p. 247
Future interest rate and bonds	p. 248
Option based on a bond	p. 250
An interest rate model	p. 251
Exercises	p. 252
Solutions to selected exercises	p. 257
Chapter 1	p. 257
Chapter 2	p. 262
Chapter 3	p. 275
Chapter 4	p. 277
Chapter 5	p. 278
Chapter 6	p. 279
Chapter 7	p. 282
Chapter 8	p. 289
Chapter 9	p. 291
Reference	p. 295
Index	p. 297
Table of Contents provided by Ingram. All Rights Reserved.