Reconstruction of a sequence generated by a Markov chain - reference request Let S be a finite sequence of symbols from a finite alphabet, with gaps - that is on some known locations an unknown number of symbols are missing. Assuming that the sequence , including the symbols in the "gaps", is generated by a Markov chain on the alphabet's symbols with an unknown transition matrix, the problem is to design an efficient algorithm that will fill (almost) correctly the gaps , with high probability . More formally , the output sequence must be close (in edit distance , for example) to one of the most  probable sequences, given S and the model. The algorithm receive only the sequence S and must output a new sequence S' generated by filling the gaps in S .

Was this problem or a close variation of it solved ? 

This seems to be an important and solvable problem, but I was not able to find any reference . I have some ideas on how to proceed , but I don't want to waste my time on some known result. 

I'm imagining the problem can have occurred in bioinformatics or communication theory.
If the number of gaps is small, you can do the following brute force approach. Try every possible way of filling those gaps (there will be exponentially many possibilities, in the number of the gaps). For every "guess", fill in the gaps accordingly and train a maximum-likelihood Markov chain on the full sequence. You can even guarantee something about the convergence of the MLE estimator for MC's:
http://proceedings.mlr.press/v98/wolfer19a.html

Having computed the maximum likelihood model -- together with its likelihood score -- pick the highest-scoring possibility of filling the gaps.

I don't know if there's an efficient (say, dynamic-programming-based) algorithm for doing this when the number of gaps is large.