Transcription of Markov Chains Compact Lecture Notes and Exercises
1 Markov ChainsCompact Lecture Notes and ExercisesSeptember 2009 ACC CoolenDepartment of MathematicsKing s College London~ @@@R@@@R@@@R @@@R @@@R part of course 6 CCM320 Apart of course 6 CCM380A21 Introduction32 Definitions and properties of stochastic Stochastic processes .. Markov Chains .. Examples .. 113 Properties of homogeneous finite state space Markov Simplification of notation & formal solution .. Simple properties of the transition matrix and the state probabilities .. Classification definitions based on accessibility of states.
2 Graphical representation of Markov Chains .. 194 Convergence to a stationary Simple general facts on stationary states .. Fundamental theorem for regular Markov Chains .. Examples .. 275 Some further developments of the Definition and physical meaning of detailed balance .. Definition of characteristic times .. Calculation of characteristic times .. 34 Appendix AExercises36 Appendix BProbability in a nutshell38 Appendix CEigenvalues and eigenvectors of stochastic matrices4031. Introduction Random walksA drunk walks along a pavement of width 5.
3 At each time step he/she moves one positionforward, and one position either to the left or to the right with equal : when in position 5 can only go to 4 (wall), when in position 1 and going to theright the process ends (drunk falls off the pavement).0 1 2 3 4 12345{wall @@R@@R@@R @@R @@R How far will the walker get on average? What is the probability for the walker to arrivehome when his/her home isKpositions away? The trained mouseroom Aroom Broom CA trained mouse lives in the house shown. A bellrings at regular intervals, and the mouse is trainedto change rooms each time it rings.}
4 When it changesrooms, it is equally likely to pass through any ofthe doors in the room it is in. Approximately whatfraction of its life will it spend in each room? The fair casinoYou decide to take part in a roulette game, starting with a capital ofC0pounds. Ateach round of the game you gamble 10. You lose this money if the roulette gives aneven number, and you double it (so receive 20) if the roulette gives an odd the roulette is fair, the probabilities of even and odd outcomes are exactly1/2. What is the probability that you will leave the casino broke?
5 The gambling bankerConsider two urns A and B in a casino game. Initially A contains two white balls, andB contains three black balls. The balls are then shuffled repeatedly at discrete timesteps according to the following rule: pick at random one ball from each urn, and swap4them. The three possible states of the system during this (discrete time and discretestate space) stochastic process are shown below:ABiiyyystate 1 ABiyyiystate 2 AByyiyistate 3A banker decides to gamble on the above process. He enters into the following bet: ateach step the bank wins 9M if there are two white balls in urn A, but has to pay1M if not.
6 What will happen to the bank? Mutating virusA virus can exist inNdifferent strains. At each generationthe virus mutates with probability (0,1) to anotherstrain which is chosen at random. Very (medically) relevantquestion: what is the probability that the strain in then-thgeneration of the virus is the same as that in the 0-th? Simple population dynamics (Moran model)We imagine a population ofNindividuals of two types,Aanda. Birth : at each stepwe select at random one individual and add a new individual of the same type. Death :we then pick at random one individual and remove it.
7 What is the probability to haveiindividuals of typeaat stepn? (subtlety: in between birth and death one hasN+ 1individuals) Google s fortuneHow did Google displace all the other search engines about ten years ago? (Altavista,Webcrawler, etc). They simply had more efficient algorithms for defining the relevanceof a particular web page, given a user s search request. Ranking of webpages generatedby Google is defined via a random surfer algorithm (stochastic process, Markov chain !).Some notation:N= nr of webpages, Li= links away from pagei, Li {1.}
8 , N}Random surfer goes from any pageito a new pagejwith probabilities:with probabilityq:pick any page from{1, .. , N}at randomwith probability 1 q: pick one of the links inLiat random5 This is equivalent toj Li: Prob[i j] =1 q|Li|+qN,j / Li: Prob[i j] =qNNote: probabilities add up to zero:N j=1 Prob[i j] = j LiProb[i j] + j / LiProb[i j]= j Li(1 q|Li|+qN)+ j / LiqN=|Li|(1 q|Li|+qN)+(N |Li|)qN= 1 q+q= 1 Calculate the fractionfiof times the site will be visited asymptotically if the aboveprocess is iterated for a very large number of iterations.
9 Thenfiwill define Google sranking of the pagei. Can we predictfi? What can one do to increase one s ranking? Gene regulation in cells - cell types & stabilityThe genome contains the blueprint of an gene in the genome is a code for theproduction of a specific protein. All cells in anorganism contain the same genes, but not all genesare switched on ( expressed ), which allows fordifferent cell types. Let i {0,1}indicate whethergeneiis switched on. This is controlled by othergenes, via a dynamical process of the typeProb[ i(t+1)=1] =f( jJ+ij j(t) activators jJ ij j(t) repressors) (A)cell type at timet: (t) = ( 1(t).)
10 , N(t))evolution of cell type: (0) (1) (2) ..?multiple stationary states of the dynamics?stable against perturbations (no degenerated runaway cells )?dependence on activation & suppression efficaciesJ ij?6 Many many other real-world processes ..Dynamical systems with stochastic (partially or fully random) are really fundamentally random, others are practically physics: quantum mechanics, solids/liquids/gases at nonzero temperature, diffusion biology: interacting molecules, cell motion, predator-prey models, medicine: epidemiology, gene transmission, population dynamics, commerce: stock markets & exchange rates, insurance risk, derivative pricing, sociology: herding behaviour, traffic, opinion dynamics, computer science: internet traffic, search algorithms, leisure.
