An Efficient Algorithm for Applied Implementation of Higher-Order Markov Models for Time Series Forecasting
Екатерина Эдуардовна Белоусова, Anton A. Rakitskiy · 2024
Markov chains can be used to predict the next state of a stationary time series with discrete time. This method models the probability distribution of future states based on one current state or a few previous states without knowing the complete history of the stochastic system. A naive implementation of such a model has some disadvantages, including the rapid increase in the size of the probability transition matrix, the possibility of zero transitions, and the potential changes in transition probabilities over time. In this paper, the paper proposes an effective method for implementing Markov chains. The article describes an algorithm for training the model and proposes the use of a sliding window technique to reevaluate probabilities. Additionally, the paper proposes optimization techniques associated with matrix multiplication and exponentiation as well as the introduction of artificial noise in the model for prediction purposes. First, this paper presents the basic concepts of Markov chains. Then, it reviews the native approach to implementing a Markov chain-based forecasting technique and proposes an improved implementation algorithm. Finally, the experimental results are presented to demonstrate the potential of the proposed method.