We present three new bit allocation techniques, the MultiStage algorithm, the Ratio algorithm, and the Pseudo I-frame method. The MultiStage and Ratio algorithms are global interframe bit allocation algorithms for embedded video coders, which attempt to minimize the maximum distortion of any frame. The Pseudo I-frame method breaks a video into segments where bit allocation algorithms should be run, and segments where constant rate bit allocation will source. We present experiments, using the Group Testing for Video coder, that compare our techniques to constant rate allocation and to a bit allocation algorithm due to Yang and Hemami.