Hidden Markov models (HMMs) are widely used by many applications for forecasting purposes. They are increasingly becoming popular models as part of prediction systems in finance, marketing, bio-informatics, speech recognition, signal processing, and so on. Given an HMM, an application of HMMs is to choose a state sequence so that the joint probability of an observation sequence and a state sequence given the model is maximized. Although this seems an easy task if the model is given, it becomes a challenge when the model is distributed between various parties. The parties can combine their models for better services. However, due to privacy, financial, and legal reasons, the model owners might not want to integrate their split models.