Alignment graph analysis of embedded discrete-time Markov Chains
Dimitar I. Radev, Svetla Radeva · 2004
A stochastic method for optimal graph alignment at analysis of embedded discrete-time Markov chain is presented. The method works by generating paths through a graph according to a Markov chain. Each path is assigned a score, and these scores are used to modify the transition probabilities of the Markov chain. This procedure converges to a fixed path through the graph, corresponding to the optimal (or near optimal) sequence alignment. Simulation and numerical results for the entrance probability vectors for tandem queue performance are shown.