Markov Chain Detection

From Google page ranking to plagiarism detection, Markov Chains are hard at work all around us. While these stochastic processes are immensely useful, identifying them as Markovian is not a trivial matter; a Markov Chain is defined to be a stochastic process which describes a sequence of possible states where each probability only depends on the previous state. We investigated the key properties of Markov Chains in order to produce an efficient algorithm which detects whether or not a given stochastic process is Markov with reasonable accuracy. We used MATLAB to generate a variety of Markov Chains and Higher-Order Markov Models and then scored their Markovianess based on their entropy, transition matrix variance, and adherence to the Markov Property. We found the Markov Property itself to be the most useful tool in our determinations and were ultimately able to successfully construct our Markov Chain Detection algorithm.