Learn Before
Concept

First-Order and k-th Order Markov Models

When a sequence satisfies a Markov condition with au=1 au = 1, the data is characterized by a first-order Markov model. In this case, the factorization of the joint probability simplifies to a product of probabilities for each element given only the immediately preceding element: P(x1,,xT)=P(x1)t=2TP(xtxt1)P(x_1, \ldots, x_T) = P(x_1) \prod_{t=2}^T P(x_t \mid x_{t-1}). When au=k au = k, the data is characterized by a kextrmthk^{ extrm{th}}-order Markov model, which conditions on the kk previous time steps. For discrete data like language, a true Markov model estimates P(xtxt1)P(x_t \mid x_{t-1}) by counting the relative frequency of each word occurring in each context, allowing the most likely sequence to be computed efficiently using dynamic programming.

0

1

Updated 2026-05-13

Contributors are:

Who are from:

Tags

D2L

Dive into Deep Learning @ D2L