  We address the problem of delay in an arithmetic coding system. Due to the
nature of the arithmetic coding process, source sequences causing arbitrarily
large encoding or decoding delays exist. This phenomena raises the question of
just how large is the expected input to output delay in these systems, i.e.,
once a source sequence has been encoded, what is the expected number of source
letters that should be further encoded to allow full decoding of that sequence.
In this paper, we derive several new upper bounds on the expected delay for a
memoryless source, which improve upon a known bound due to Gallager. The bounds
provided are uniform in the sense of being independent of the sequence's
history. In addition, we give a sufficient condition for a source to admit a
bounded expected delay, which holds for a stationary ergodic Markov source of
any order.
