Markov Chains Complex dependencies and/or feature functions only visible variables visible and invisible variables Markov Chains Markov Random Fields Hidden Markov Models Conditional Random Fields 1 Chains Introduction to probabilities
Def: Stochastic Process stochastic process  is a sequence of random variables , denoted as  . “initial  state” 2 “state at  time 
Def: Markov chain Markov chain  is a sequence of random variables such that The probability of  depends only on the value of the predecessor of  “The future is independent of the past,  given the present state.”   3
Example: Markov chain Let our named sets be the weather on consecutive days, with V={sun,rain}. This is a Markov chain, if P(D3|D1,D2) = P(D3|D2) The probability distribution of D3 given a value for D2 is the same as the probability distribution of D3 given values for D2 and D1 4 D1 D2 sun D3 sun sun sun sun rain ... ... ...
A Markov chain   is  homogeneous  if i.e., the conditional probability is the same for all days.   Def: Homogeneous Markov Chain 5 (We will consider only homogeneous Markov Chains for now)            e.g. we write  P(sunny|rainy)                            for  P(D2=sunny | D1=rainy) which is the same as  P(D3=sunny | D2=rainy) which is the same as  P(D4=sunny | D3=rainy) ... We write   for    
We can represent a Markov Chain as a graph, where the nodes are the values  , and the edge weights are  :       Markov Chains as graphs 6 sunny rainy
Wikipedia/Markov Chains Markov chains as matrices 7 rainy sunny sunny rainy Transition Matrix        sunny rainy
Wikipedia/Markov Chains Markov chains as matrices 8 0.9 0.1 0.5 0.5 0.9 0.1 0.5 0.5 sunny rainy rainy sunny sunny rainy Transition Matrix 
We are now interested in one particular sequence of events: Caring about the Joint Probability 9 Markov property Homogenity Recursion Definition of conditional probability
A joint probability corresponds to a path in the graph:   Joint Probability in the Graph 10 sunny rainy      
Example: Joint Probability in Graph 11 0.9 0.1 0.5 0.5 sunny rainy
Caring about the final state 12 We are now interested in the distribution of the final state: Definition of marginal probability Definition of conditional probability Homogenity
The final state and the Matrix 13 Transition Matrix  rainy sunny sunny rainy
The final state and the Matrix 14 = Now let’s look at the row vector  : That is:
Def: Stationary Distribution 15 = Now assume that  This means that  =>    is an eigenvector of   ! Such a distribution is called a  stationary distribution  of  . It implies that all future states will be equal to  .
Def: Irreducible Markov Chain 16 A Markov Chain given by a transition matrix   is  irreducible , if for any states  , there is an   such that  . In other words, the chain is able to move from any state   to any state  (in one or more steps).
Def: Period 17 A state   of a Markov Chain has period  if any return to   occurs at step  , for some  Formally: ) where   denotes the greatest common divisor. If   then state   is said to be  aperiodic .
For some Markov Chains, the stationary distribution exists and is unique: This is the case if  i.e.,  already if  . Then,    is  ergodic . Def: Ergodic Markov chains 18  is the  steady state  or  stationary distribution . If   exists, then this implies •   is independent of  •   is an eigenvector of 
Page Rank can be seen as a Markov Chain, where the values are the pages and   is the probability that a random surfer visits page  . Random variables:  Values:   (=the pages)  is the probability that the surfer is at page  after   hops.  is given by the links. Page Rank 19 p1 p2 p3 0.1 0.9
By adding random jumps from all pages to all pages the chain becomes ergodic, and the steady state exists. Page Rank 20 p1 p2 p3 0.1 0.9
Markov Chains Complex dependencies and/or feature functions only visible variables visible and invisible variables Markov Chains Markov Random Fields Hidden Markov Models Conditional Random Fields 21 Chains Introduction to probabilities