Markov Networks

Read Rabiner (1987) which will be given.

You may find it helpful to start experimenting with my HMM Mini-Toolkit at this stage.

Consider a state machine with N states: $S_1, S_2, \cdots, S_N$

Suppose that it regularly undergoes a state-change at multiples of a certain constant period of time according to a set of probabilities associated with its current state.

Let's denote the times at which state changes take place by $t = 1, 2, 3, \cdots$ and denote the state at time t by q_t.

It is reasonable to suppose that P(q_t = S_j) depends upon the history of the system before reaching q_t, i.e. $q_{t-1}, q_{t-2}, \cdots, q_1$ (Consider the weather example).

But an analysis of this kind is too tedious (intractable).

So we simplify our model and consider a discrete first order Markov chain instead which says that P(q_t) only depends upon P(q_t-1), i.e. $P(q_t = S_j \vert q_{t-1} = S_i, q_{t-2} = S_k, \cdots) = P(q_t = S_j \vert q_{t-1} = S_i)$

Also, we only consider those processes in which the state transition probabilities do not change with time, i.e. P(q_t = S_j | q_t-1 = S_i) = a_ij = the probability of transiting from State i to State j at any time.

Obviously we can make other assumptions that are true of probabilities in general, for instance, $0 \le a_{ij} \le 1$ and

$$\sum\limits_{j=1}^{N} a_{ij} = 1$$

To completely specify the MM we also need to specify the probabilities of originating in each state - the initial probabilities. Let $\pi = \{\pi_1, \pi_2, \cdots, \pi_N\}$ be the set of initial state probabilities. Then the MM is defined by $\lambda = (A, \pi)$. (PS: Assume that N is implicitly specified in A)

Assume you are modeling the weather and that the weather on any particular day can be represented by one of three possible states: S₁ = Rainy, S₂ = Cloudy and S₃ = Fine.

You are now given the following State Transition matrix representative of a 1st order Markov Model:

$$A = \{a_{ij}\} = \left[ \begin{array}{lll} 0.4 & 0.3 & 0.3 \\ 0.2 & 0.6 & 0.2 \\ 0.1 & 0.1 & 0.8 \\ \end{array} \right]\\$$

and asked to find the probability that the next 7 days will be, in exact order, fine, fine, rainy, rainy, fine, cloudy, fine, given that today is a fine day.

We want to determine the probability of the observation sequence O = S₃, S₃, S₃, S₁, S₁, S₃, S₂, S₃. Thus

$$\begin{eqnarray*}P(O\vert Model) &=& P(S_3) \cdot P(S_3\vert S_3) \cdot P(S_3\ve... ...\times 0.3 \times 0.1 \times 0.2\\ &=& 1.536 \times 10^{-4}\\ \end{eqnarray*}$$

where $\pi_i$ is the probability of being in state i at t=1.

What is the probability that we will have a full January of fine days given that New Year's day is fine (p₃(30))? What if we specify in addition that Feb 1 is not a fine day?

What is the expected number of consecutive fine days? Rainy days? Cloudy days? The expected duration d_i in state i is given by:

$$\overline{d_i} = \sum_{x=1}^\infty x p_i(x) = \sum_{x=1}^\infty x a_{ii}^{x-1}(1-a_{ii})$$

Prove that this is equal to 1/(1-a_ii)