Convex Optimization · Problem 7.5

Geometric problems — Boyd & Vandenberghe

Mathematics — Optimization · markov-chain-estimation

Problem

Markov chain estimation. Consider a Markov chain with

n

states, and transition probability matrix

P \in \mathbf{R}^{n \times n}

defined as

P_{ij} = \mathbf{prob}(y(t+1) = i \mid y(t) = j).

The transition probabilities must satisfy

P_{ij} \geq 0

and

\sum_{i=1}^n P_{ij} = 1

j = 1, \ldots, n

. We consider the problem of estimating the transition probabilities, given an observed sample sequence

y(1) = k_1, y(2) = k_2, \ldots, y(N) = k_n

. (a) Show that if there are no other prior constraints on

P_{ij}

, then the ML estimates are the empirical transition frequencies:

\hat{P}_{ij}

is the ratio of the number of times the state transitioned from

j

into

i

, divided by the number of times it was

j

, in the observed sample. (b) Suppose that an equilibrium distribution

p

of the Markov chain is known, i.e., a vector

q \in \mathbf{R}^n_+

satisfying

\mathbf{1}^T q = 1

and

Pq = q

. Show that the problem of computing the ML estimate of

P

, given the observed sequence and knowledge of

q

, can be expressed as a convex optimization problem.