Driving Markov Chains to Desired Equilibria via Linear Programming
Harish S. Bhat, Li-Hsuan Huang, Sebastian Rodriguez · 2019
Categorical time series arise frequently in both biomedical and sports analytics settings. For instance, [1] considers EEG measurements of infants' sleep states, where each state is an element of {"quiet sleep", "indeterminate sleep", "active sleep", "awake"}. In our previous work [2] , we have modeled substitutions of players in NBA basketball games-here each state corresponds to a group of five players on the court. We consider modeling such systems using Markov chains. We must then estimate the entries of either the transition matrix, for discrete-time Markov chains (DTMCs), or the transition rate matrix, for continuous-time Markov chains (CTMCs). In both cases, we have access to closed-form maximum likelihood estimators (MLEs). If we decide to use a DTMC model, to estimate the transition probability from state i to state j , we simply count the number of transitions from i to j present in the data, and divide by the total number of transitions from i to any state. This is the MLE. The MLE is consistent: assume the data is generated by an irreducible, recurrent DTMC with transition probabilities p ij . Then, given time series of length N , as N → ∞, the MLE estimates ${\hat p_{ij}}$ converge to p ij with probability 1. We have stated these results for DTMCs; for CTMCs, the story is analogous.