Markov Processes & Markov Chains

Source: Unit 3 §11

From IID to dependence

A random sample is a sequence of IID random variables: independent and identically distributed.

≡FactsWhat the two letters mean

• Identically distributed - no trends over the sequence; every draw comes from the same distribution.
• Independent - P(X=a, Y=b) = P(X=a)·P(Y=b); the samples are not connected to each other.

Drawing balls from an urn with replacement is IID. Drawing without replacement is not: the distribution is the same each time, but the draws are dependent.

⚠GotchaThe independence assumption of Naive Bayes is very strong

It often fails outright. If it has rained for the last 48 hours, today is more likely to be rainy - one feature's value affects another. When that happens you need a model with finite-state-machine-like structure, not a product of independent terms.

Random variables become random processes

≡FactsThe vocabulary

• The domain of a random variable is its set of possible outcomes. A die has domain {1, …, 6} with P = 1/6 each.
• Random variables are discrete or continuous - tomorrow's stock price lives in $\mathbb{R}^{+}$.
• A random process is a set of random variables over time, such as the stock price at each hour. All of them share the same domain.
• A deterministic process has its state fully determined by the initial conditions and the parameters - a dropped ball.
• A stochastic process has a state that cannot be determined even given the initial conditions and parameters.

The Markov property

A stochastic process is a Markov process if the next state depends only on the current state, not on the history. Such systems are memoryless: the future depends only on the present.

$$P(X_{n+1} \mid X_n, X_{n-1}, \dots, X_1) = P(X_{n+1} \mid X_n)$$

That is the first-order Markov property. An n-th order Markov process conditions the next state on the previous $n$ states.

≡FactsProperties of a discrete Markov process, or Markov chain

• No single defined start state - the chain can start from any state, which is why a starting distribution is part of the model.
• It is irreducible if any state is reachable from any other.
• State j is accessible from i if there exists some n ≥ 0 for which the probability of reaching j from i in n steps is nonzero.

Graphical representation and parameters

In a probabilistic graphical model, nodes are random variables and edges are conditional probability distributions between them, so the graph shows the causal relationships directly.

≡FactsParameters of a discrete Markov model λ = (P, A)

• P is the vector of starting probabilities, since the chain can begin in any state.
• aᵢⱼ is the transition probability of moving from state i to state j.
• Constraint: the sum of all transition probabilities out of a state is 1.
• All the transitions together form the transition matrix A.

From \ To	S	C	R
S	a₁₁	a₁₂	a₁₃
C	a₂₁	a₂₂	a₂₃
R	a₃₁	a₃₂	a₃₃

⚠GotchaRow is FROM, column is TO

Each row of $A$ is a probability distribution over next states and therefore sums to 1. Columns do not sum to anything in particular. Transposing the matrix by accident is the single most common way to get a Markov question wrong.

Worked example 1: the probability of a weather sequence

Three states, {Sunny, Cloudy, Rainy}, with this transition matrix:

From \ To	S	C	R
S	0.6	0.2	0.2
C	0.2	0.5	0.3
R	0.1	0.4	0.5

The transition matrix and this picture are the same object. Every arrow leaving a circle, self-loop included, is one row of the matrix, which is why those arrows must sum to 1.

Question: what is the probability of the sequence C, S, R, C, R, given that the chain starts in Cloudy with $P_C = 0.3$?

$$P(CSRCR \mid P, A) = P_C \cdot P(S \mid C) \cdot P(R \mid S) \cdot P(C \mid R) \cdot P(R \mid C)$$

→StepsReading each factor off the matrix

1. Start: $P_C = 0.3$.
2. C → S is row C, column S: $0.2$.
3. S → R is row S, column R: $0.2$.
4. R → C is row R, column C: $0.4$.
5. C → R is row C, column R: $0.3$.
6. Multiply: $0.3 \times 0.2 \times 0.2 \times 0.4 \times 0.3 = \mathbf{0.00144}$.

Worked example 2: estimating the parameters from a trellis

Given an observed sequence over 14 days, estimate the model rather than being handed it.

→StepsCounting a model out of observations

1. Starting probabilities are the frequency of each state appearing as a starting state.
2. Transition matrix: count the transitions i → j, then divide by the total number of transitions out of i.
3. Dividing by the out-degree total, rather than by the grand total, is what keeps each row summing to 1.