Inferring Markov chains: Bayesian estimation, model comparison, entropy rate, and out-of-class modeling

Markov chains are a natural and well understood tool for describing one-dimensional patterns in time or space. We show how to infer $k\text{th}$ order Markov chains, for arbitrary $k$, from finite data by applying Bayesian methods to both parameter estimation and model-order selection. Extending existing results for multinomial models of discrete data, we connect inference to statistical mechanics through information-theoretic (type theory) techniques. We establish a direct relationship between Bayesian evidence and the partition function which allows for straightforward calculation of the expectation and variance of the conditional relative entropy and the source entropy rate. Finally, we introduce a method that uses finite data-size scaling with model-order comparison to infer the structure of out-of-class processes.

Figure 1

A deterministic hidden Markov chain for the golden mean process. Edges are labeled with the output symbol and the transition probability: symbol ∣ probability.

Figure 2

A plot of the inference of $M_1$ model parameters for the golden mean process. For each data sample size $N$, the marginal posterior is plotted for the parameters of interest: $p(0\mid 1)$ in the top panel and $p(1\mid 0)$ in the lower panel. The true values of the parameters are $p(0\mid 1)=1∕2$ and $p(1\mid 0)=1$.

Figure 3

Model comparison for Markov chains of order $k=1–4$ using average counts from the golden mean process. Sample sizes from $N=100$ to $N=1000$ in steps of $\Delta N=5$ are used to generate these plots. The top panel displays the model probabilities using a uniform prior over orders $k$. The bottom panel displays the effect of a penalty for model size. Note: For most values of $N$ the data from $M_3$ and $M_4$ overlap.

Figure 4

The convergence of ${\mathbf{E}}_{\mathrm{post}}\left[E(Q,P)\right]$ to the true entropy rate $h_{\mu }=2∕3\text{bits}$ per symbol (indicated by the gray horizontal line) for the golden mean process. As demonstrated in Eq. (41), the conditional relative entropy $D[Q\parallel P]\to 0$ as $1∕N$. This results in the convergence of $h_{\mu }\left[Q\right]$ to the true entropy rate.

Figure 5

Deterministic hidden Markov chain representation of the even process. This process cannot be represented as a finite-order (nonhidden) Markov chain over the output symbols 0s and 1s. The set of irreducible forbidden words $\mathcal{F}=\{{01}^{2n+1}0:n=0,1,2,\dots \}$ reflects the fact that the process generates blocks of 1s, bounded by 0s, that are even in length, at any length.

Figure 6

A plot of the inference of $M_1$ model parameters for the even process. For a variety of sample sizes $N$, the marginal posterior for $p(0\mid 1)$ (top panel) and $p(1\mid 0)$ (bottom panel) are shown. The true values of the parameters are $p(0\mid 1)=1∕4$ and $p(1\mid 0)=1∕2$.

Figure 7

Model comparison for Markov chains of order $k=1–4$ for average data from the even process. The top panel shows the model comparison with a uniform prior over the possible orders $k$. The bottom panel demonstrates model comparison with a penalty for the number of model parameters. In both cases, the $k=4$ model is chosen over lower orders as the amount of data available increases.

Figure 8

The convergence of ${\mathbf{E}}_{\mathrm{post}}[D[Q\parallel P]+h_{\mu }\left[Q\right]]$ to the true entropy rate $h_{\mu }=2∕3\text{bits}$ per symbol for the even process. The true value is indicated by the horizontal gray line. Experience shows that a $k=10$ Markov chain and sufficient data is needed to effectively approximate the true value of $h_{\mu }$.

Figure 9

A hidden Markov chain representation of the simple nondeterministic process. This example also cannot be represented as a finite-order Markov chain over output 0 and 1 sequences. It is however, more complicated than the two previous examples: Only the observation of a 0 provides the observer with information regarding the internal state of the underlying process; observing a 1 leaves the internal state ambiguous.

Figure 10

Marginal density for $M_1$ model parameters for the simple nondeterministic process: The curves for each data size $N$ demonstrate a well behaved convergence to the correct values, $p(0\mid 1)=1∕3$ and $p(1\mid 0)=1$.

Figure 11

Model comparison for Markov chains of order $k=1–4$ for data from the simple nondeterministic process. The top panel shows the model comparison with a uniform prior over the possible orders $k$. The bottom panel demonstrates model comparison with a penalty for the number of model parameters. Note the scale on the horizontal axis—it takes much more data for the model comparison to pick out higher orders for this process compared to the previous examples.

Figure 12

The convergence of ${\mathbf{E}}_{\mathrm{post}}[D[Q\parallel P]+h_{\mu }\left[Q\right]]$ to the true entropy rate $h_{\mu }\approx 0.677867\text{bits}$ per symbol for the simple nondeterministic source. The true value is indicated by the gray horizontal line.

Figure 13

A plot of model comparison, with a penalty for model size, for a single time series of length 1000 from the even process. Model comparison is performed on subsamples of the time series, starting with the first 100 symbols and increasing the data size considered in increments of 2 until the full sample is analyzed. Although noisy, the results are consistent with the bottom panel of Fig. 7 and demonstrate a preference for even $k$ over odd.