A new upper hound

and lower hound

are developed for the rate-distortion function of a binary symmetric Markov source with respect to the frequency of error criterion. Both hounds are explicit in the sense that they do not depend on a blocklength parameter. In the interval

, where

is Gray\´s critical value of distortion,

is convex downward and possesses the correct value and the correct slope at both endpoints. The new lower bound

diverges from the Shannon lower bound at the same value of distortion as does the second-order Wyner-Ziv lower bound. However, it remains strictly positive for all

and therefore eventually rises above all the Wyner-Ziv lower bounds as

approaches

. Some generalizations suggested by the analytical and geometrical techniques employed to derive

and

are discussed.