Clock and data recovery circuits are essential components in communication systems. They directly influence the bit-error-rate performance of communication links. It is desirable to predict the rate of occasional detection errors and the loss of synchronization due to the non-ideal operation of such circuits. In high-speed data networks, the bit-error-rate specification on the system can be very stringent, i.e., 1014. It is not feasible to predict such error rates with straightforward, simulation based, approaches. This work introduces a stochastic model and an efficient, analysis-based, non-Monte-Carlo method for performance evaluation of digital data and clock recovery circuits. The analyzed circuit is modeled as finite state machines with inputs described as functions on a Markov chain state-space. System performance measures, such as probability of bit errors and rate of synchronization loss, can be evaluated through the analysis of a larger resulting Markov system. A dedicated multi-grid method is used to solve the very large associated linear systems. The method is illustrated on a real industrial clock-recovery circuit design.