Video coding schemes designed based on sequential or predictive coding models are vulnerable to the loss of encoded frames at the decoder end. Motivated by this observation, in this thesis we propose two new coding models: robust sequential coding and robust predictive coding. For the Gauss-Markov source with the mean squared error distortion measure, we characterize certain supporting hyperplanes of the rate region of these two coding problems. The proof is divided into three steps: 1) it is shown that each supporting hyperplane of the rate region of Gaussian robust sequential coding admits a max-min lower bound; 2) the corresponding min-max upper bound is shown to be achievable by a robust predictive coding scheme; 3) a saddle point analysis proves that the max-min lower bound coincides with the min-max upper bound. Furthermore, it is shown that the proposed robust predictive coding scheme can be implemented using a successive quantization system. Theoretical and experimental results indicate that this scheme has a desirable \self-recovery" property. Our investigation also reveals an information-theoretic minimax theorem and the associated extremal inequalities.