Rate Distortion analysis is a branch of information theory that predicts the tradeoffs between rate and distortion in source coding. In this thesis, we present the rate distortion analysis for conditional motion estimation, a process that estimates motion based on a criterion that affects coding rate, complexity of coding scheme and quality of the reconstructed video. In order to guide the rate distortion analysis, we use a conditional motion estimation scheme that estimates motion for certain blocks selected based on significant changes. We begin by explaining the conditional motion estimation technique and the effect of decision criteria on the technique. We then model the motion vectors as Gaussian-Markov process and study the rate distortion tradeoffs in the video encoding scheme. The rate distortion bound derived in this manner is also validated with a practical approach.