Decoder is completely deterministic. In fact the normative part of most MPEG standards is implementation of the decoder in C-like pseudocode (which is horribly

Decoder is completely deterministic. In fact the normative part of most MPEG standards is implementation of the decoder in C-like pseudocode (which is horribly slow because it is not optimized in any way and mostly deals with discrete bits). On the other hand how encoder works is not specified at all apart from the obvious requirement that it has to produce something decodable by the above mentioned decoder.