This paper presents an optimal control algorithm for linear systems with measurement noise which has a Markov dependent statistical property. Ordinarily, the optimal control for this problem involves a very large number of sequences, and the usual calculation method becomes impractical. In the algorithm proposed here, the optimal control is calculated with a relatively small number of sequences, sampled at random from the set of all the sequences.