Bounded Expected Delay in Arithmetic Coding
Dept. of EE-Systems
Tel Aviv 69978
Israel
We address the problem of delay in an arithmetic coding system. Due to the nature of the arithmetic coding process, source sequences causing {\em 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. %We address the problem of delay in an arithmetic coding system. %Due to the nature of the arithmetic coding process, source %sequences causing {\em arbitrarily large} encoding or decoding %delays exist. This phenomena gives rise to 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, how many source %letters should be further encoded on the average to enable full %decoding of that sequence. In this paper, we provide several new %uniform upper bounds on the expected delay for a memoryless %source, which improve upon a known bound due to Gallager. In %addition, we give a sufficient condition for a source to admit a %bounded expected delay, which is shown to hold for a stationary %ergodic Markov source of any order.
AC_delay_isit.tex
\documentclass[10pt,conference]{IEEEtran}
\usepackage{amsmath,epsfig}


\input{new_shorts.tex}
%\pagestyle{empty}
%\bibliographystyle{plain}


\begin{document}

\title{Bounded Expected Delay in Arithmetic Coding}


\author{\authorblockN{Ofer Shayevitz, Ram Zamir, and Meir Feder }
\authorblockA{Tel Aviv University, Dept. of EE-Systems\\
         Tel Aviv 69978, Israel \\
         Email: \{ofersha, zamir, meir \}@eng.tau.ac.il}}

\maketitle


%%%%%%%%%%%%%%%%%% Main %%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{abstract}
We address the problem of delay in an arithmetic coding system.
Due to the nature of the arithmetic coding process, source
sequences causing {\em 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.


%We address the problem of delay in an arithmetic coding system.
%Due to the nature of the arithmetic coding process, source
%sequences causing {\em arbitrarily large} encoding or decoding
%delays exist. This phenomena gives rise to 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, how many source
%letters should be further encoded on the average to enable full
%decoding of that sequence. In this paper, we provide several new
%uniform upper bounds on the expected delay for a memoryless
%source, which improve upon a known bound due to Gallager. In
%addition, we give a sufficient condition for a source to admit a
%bounded expected delay, which is shown to hold for a stationary
%ergodic Markov source of any order.
\end{abstract}

\section{Introduction}
Arithmetic coding has been introduced by Elias
\cite{arithmetic_coding_jelink}, as simple means to sequentially
encode a source at its entropy rate, while significantly reducing
the extensive memory usage characterizing non-sequential schemes.
The basic idea underlying this technique is the successive mapping
of growing source sequences into shrinking intervals of size equal
to the probability of the corresponding sequence, and then
representing those intervals by a binary expansion. Other coding
schemes reminiscent of Elias' arithmetic coding have been
suggested since, aimed mostly to overcome the precision problem of
the original scheme
\cite{arithmetic_coding_rissanen}\cite{arithmetic_coding_pasco}.

Delay in the classical setting of arithmetic coding stems from the
discrepancy between source intervals and binary intervals, which
may prohibit the encoder from producing bits (encoding delay) or
the decoder from reproducing source letters (decoding delay). On
top of its usual downside, delay also increases memory usage, and
therefore a large delay may turn the main advantage of arithmetic
coding on its head. As it turns out, for most sources there exists
infinite number of source sequences for which the delay is
infinite, where each sequence usually occurs with probability
zero. A well known example demonstrating this phenomena is that of
a uniform source over a ternary alphabet $\{0,1,2\}$. The source
sequence $111\ldots$ is mapped into shrinking intervals that
always contain the point $\frac{1}{2}$, and so not even a single
bit can be encoded. This observation leads to the question of just
how large is the expected delay (and consequently, the expected
memory usage) of the arithmetic coding process for a given source,
and if it is bounded at all.


The problem of delay can be practically dealt with by insertion of
a fictitious source letter into the stream to ``release'' bits
from the encoder or letters from the decoder, whenever the delay
exceed some predetermined threshold. Another possibility is coding
of finite length sequences, so that a prefix condition is
satisfied at the expense of a slightly higher redundancy, and
blocks can be concatenated \cite{IT_cover}. Nevertheless, it is
still interesting to analyze the classical sequential setting in
terms of expected delay.

In his lecture notes \cite{gallager_lecture_notes}, Gallager has
provided an upper bound for the expected delay in arithmetic
coding for a memoryless source, which was later generalized to
coding over cost channels \cite{arithmetic_coding_savari}.
Gallager's bound is given by
\begin{equation*} \Expt(D) \leq \frac{\log(8e^2\slash
\beta)}{\log(1\slash \alpha)}
\defn \mathcal{D}_g(\alpha,\beta)
\end{equation*}
where $\alpha$ and $\beta$ are the maximal and minimal source
letter probabilities respectively. Notice that this bound is
independent of the sequence's history, as shall be the case with
all the bounds presented in this paper. In Theorem
\ref{thrm:memoryless} (section \ref{sec:memoryless}) we derive a
new upper bound for the expected delay, given by
\begin{equation*}
\Expt(D) \leq 1+\frac{4\alpha\big{(}1-\alpha+ \log(1\slash
\alpha)\big{)}}{(1-\alpha)^2} \defn \mathcal{D}_1(\alpha)
\end{equation*}
which depends only on the most favorable source letter. Following
that, we show that the dependence on the least favorable letter in
Gallager's bound is unnecessary, and provide (section
\ref{sec:improving_gallager}) a uniformly tighter version of the
bound given by $\mathcal{D}_{mg}(\alpha)
\defn \mathcal{D}_g(\alpha,\alpha)$. In Theroem \ref{thrm:memoryless_tighter} (section
\ref{sec:improving_bound}) we derive another bound
$\mathcal{D}_2(\alpha)$ uniformly tighter than
$\mathcal{D}_1(\alpha)$, which is also shown to be tighter than
$\mathcal{D}_{mg}(\alpha)$ for most sources, and looser only by a
small multiplicative factor otherwise.

Our technique is extended to sources with memory, and in Theorem
\ref{thrm:memory} (section \ref{sec:memory}) we provide a new
sufficient condition for a source to have a bounded expected delay
under arithmetic coding. Specifically, this condition is shown to
hold for any stationary ergodic Markov source over a finite
alphabet.

%The paper is organized as follows. In section
%\ref{sec:perliminaries} we briefly describe the arithmetic coding
%process, and provide some notations used in the sequel. In section
%\ref{sec:memoryless} we derive a new upper bound on the expected
%delay of arithmetic coding for a memoryless source. In section
%\ref{sec:improving_gallager} we improve the Gallager bound. Our
%own bound is also improved in section \ref{sec:improving_gallager}
%and compared to the modified Gallager bound. In section
%\ref{sec:memory} we generalize the exposition to include sources
%with memory and derive a sufficient condition for a bounded
%expected delay. A short summary is provided in section
%\ref{sec:summary}.

\section{Arithmetic Coding in a Nutshell}\label{sec:perliminaries}

Consider a discrete source over a finite alphabet $\mathcal{X} =
\{0,1,\ldots,K-1\}$ with positive letter probabilities
$\{p_0,p_1,\ldots,p_{K-1}\}$. A finite source sequence is denoted
by $x_m^n = \{x_m,x_{m+1},\ldots,x_n\}$ with $x^n = x_1^n$, while
an infinite one is denoted by $x^\infty$. An arithmetic coder maps
the sequences $x^n,x^{n+1},\ldots$ into a sequence of nested
\textit{source intervals}
$\mathcal{I}(x^n)\supset\mathcal{I}(x^{n+1})\supset\ldots$ in the
unit interval that converge to a point $y(x^\infty) =
\cap_{n=1}^\infty \mathcal{I}(x^n)$ . The mapping is defined as
follows:
\begin{eqnarray*}
f_1(i) &=& \sum_{j=0}^{i-1}p_j\,,\quad f(x^1) = f_1(x_1) \\
f(x^n) &=& f(x^{n-1}) +
f_1(x_n)\Pr(x^{n-1}) \\
\mathcal{I}(x^n) &=& \left[f(x^n),f(x^n)+\Pr(x^n)\right)
\label{eq:encode}
\end{eqnarray*}
Notice that $|\mathcal{I}(x^n)| = \Pr(x^n)$ and that source
intervals corresponding to different sequences of the same length
are disjoint.
%Notice that this mapping satisfies
%\begin{equation*}
%\bigcup_{x^n\in\mathcal{X}^n}\mathcal{I}(x^n) = [0,1)\,,\quad
%\mathcal{I}(x^n)\cap \mathcal{I}(\tilde{x}^n) = \phi \quad \forall
%x^n\neq \tilde{x}^n
%\end{equation*}
%and also $|\mathcal{I}(x^n)| = \Pr(x^n)$ as required.
Following that, a random source sequence $X^n$ is mapped into a
random interval $\mathcal{I}(X^n)$, which as $n$ grows converges
to a random variable $Y(X^\infty)$ that is uniformly distributed
over the unit interval.

For any sequence of binary digits $b^k = \{b_1,b_2,\ldots,b_k\}$
we define a corresponding \textit{binary interval}
\begin{equation}
\mathcal{J}(b^k) = \big{[} 0.b_1b_2,\ldots b_k0,\; 0.b_1b_2,\ldots
b_k1 \big{)} \label{eq:decode}
\end{equation}
and the midpoint of $\mathcal{J}(b^k)$ is denoted by $m(b^k)$.

The process of arithmetic coding is performed as follows. The
encoder maps the input letters $x^n$ into a source interval
according to (\ref{eq:encode}), and outputs the bits representing
the smallest binary interval $\mathcal{J}(b^k)$ containing the
source interval $\mathcal{I}(x^n)$. This process is performed
sequentially so the encoder produces further bits whenever it can.
The decoder maps the received bits into a binary interval, and
outputs source letters that correspond to the minimal source
interval that contains that binary interval. Again, this process
is performed sequentially so the decoder produces further source
letters whenever it can.

\section{Memoryless Source}\label{sec:memoryless}
In this section, we provide a new bound for the expected delay of
an arithmetic coding system for a memoryless source, as a function
of the probability of the most likely source letter
\begin{equation*}
\alpha\defn\max p_k .
\end{equation*}
All logarithms in this paper are taken to the base of 2.
\begin{theorem}\label{thrm:memoryless}
\textit{Assume a sequence of $n$ source letters $x^n$ has been
encoded, and let $D$ be the number of extra letters that need to
be encoded to allow $x^n$ to be fully decoded. Then
\begin{equation}\label{eq:delay_prob}
\Pr(D > d) \leq 4\alpha^d\left (1 + d \log(1\slash \alpha)\right)
\end{equation}
independent of $x^n$. The expected delay is correspondingly
bounded by
\begin{equation}\label{eq:delay_s}
\Expt(D) \leq 1+\frac{4\alpha\big{(}1-\alpha+ \log(1\slash
\alpha)\big{)}}{(1-\alpha)^2} \defn \mathcal{D}_1(\alpha).
\vspace{0.1cm}\end{equation}}
\end{theorem}

Let us first outline the idea behind the proof. The sequence $x^n$
has been encoded into the binary sequence $b^k$ which represents
the minimal binary interval $\mathcal{J}(b^k)$ satisfying
$\mathcal{I}(x^n) \subseteq \mathcal{J}(b^k)$. The decoder has so
far been able to decode only $m<n$ letters, where $m$ is maximal
such that $\mathcal{J}(b^k) \subseteq \mathcal{I}(x^m)$. After $d$
more source letters are fed to the encoder, $x^{n+d}$ is encoded
into $b^{k'}$ where $k'\geq k$ is maximal such that
$\mathcal{I}(x^{n+d})\subseteq \mathcal{J}(b^{k'})$. Thus, the
entire sequence $x^n$ is decoded if and only if
\begin{equation}\label{eq:interval_cond}
\mathcal{I}(x^{n+d}) \subseteq \mathcal{J}(b^{k'}) \subseteq
\mathcal{I}(x^n).
\end{equation}

Now, consider the middle point $m(b^k)$, which is always contained
inside $\mathcal{I}(x^n)$ as otherwise another bit could have been
encoded. If $m(b^k)$ is contained in $\mathcal{I}(x^{n+d})$ (but
not as an edge), then condition (\ref{eq:interval_cond}) cannot be
satisfied, and the encoder cannot yield even one further bit. This
observation can be generalized to a set of points which, if
contained in $\mathcal{I}(x^{n+d})$, $x^n$ cannot be completely
{\em decoded}. For each of these points the encoder outputs a
number of bits which may enable the decoder to produce source
letters, but not enough to fully decode $x^n$. The encoding and
decoding delays are therefore treated here simultaneously, rather
than separately as in \cite{arithmetic_coding_savari}.

We now introduce some notations and prove a Lemma, required for
the proof of Theorem \ref{thrm:memoryless}. Let $[a,b)\subseteq
[0,1)$ be some interval, and $p$ some point in that interval. In
the definitions that now follow we sometime omit the dependence on
$a,b$ for brevity. We say that $p$ is {\em strictly contained} in
$[a,b)$ if $p\in [a,b)$ but $p\neq a$. We define the
\textit{left-adjacent} of $p\,$ w.r.t. $[a,b)$ to be
\begin{equation*}
\ell(p) \defn \min\left \{x\in [a,p)\,:\,\exists k\in\IntF^+ ,\, x
= p-2^{-k} \right \}
\end{equation*}
and the \textit{t-left-adjacent} of $p\;$ w.r.t. $[a,b)$ as
\begin{equation*}
\ell^{(t)}(p) \defn
\overbrace{(\ell\circ\ell\circ\cdots\circ\ell)}^t(p)\;,\quad
\ell^{(0)}(p) \defn p
\end{equation*}
Notice that $\ell^{(t)}(p) \rightarrow a$ monotonically with $t$.
We also define the \textit{right-adjacent} of $p\,$ w.r.t $[a,b)$
to be
\begin{equation*}
r(p) \defn \max\left \{x\in (p,b)\,:\,\exists k\in\IntF^+ ,\, x =
p+2^{-k} \right \}
\end{equation*}
and $r^{(t)}(p)$ as the \textit{t-right-adjacent} of $p\,$ w.r.t.
$[a,b)$ similarly, where now $r^{(t)}(p) \rightarrow b$
monotonically. For any $\delta < b-a$, the \textit{adjacent
$\delta$-set} of $p\;$ w.r.t. $[a,b)$ is defined as the set of all
adjacents that are not "too close" to the edges of $[a,b)$:
\begin{eqnarray*}
& S_\delta(p) & \defn \left \{ x\in[a+\delta,b-\delta)\,:\,
\exists\,t\in\IntF^+\cup \{0\}\,,\right. \\ & & \left.\qquad\qquad
x = \ell^{(t)}(p) \,\vee \,x = r^{(t)}(p) \right \}
\end{eqnarray*}
Notice that for $\delta > p-a$ this set may contain only
right-adjacents, for $\delta > b-p\;$ only left-adjacents, for
$\delta>\frac{b-a}{2}$ it is empty, and for $\delta=0$ it is
infinite.
\begin{lemma}\label{lem:delta_set}\textit{
The size of $S_\delta(p)$ is bounded by \vspace{-0.2cm}
\begin{equation}\label{eq_delta_set}
|S_\delta(p)|\leq 1+ 2\log{\frac{|b-a|}{\delta}}\vspace{0.2cm}
\end{equation}}
\end{lemma}
\begin{proof}
It is easy to see that the number of t-left-adjacents of $p$ that
are larger than $a+\delta$ is the number of ones in the binary
expansion of $(p-a)$ up to resolution $\delta$. Similarly, the
number of t-right-adjacents of $p$ that are smaller than
$b-\delta$ is the number of ones in the binary expansion of
$(b-p)$ up to resolution $\delta$. Defining $\lceil x \rceil^+
\defn \max (\lceil x \rceil,0 ) $, we get:
\begin{eqnarray}
\nonumber |S_\delta(p)| &\leq &
\lceil\log{\frac{p-a}{\delta}}\rceil^+ +
\lceil\log{\frac{b-p}{\delta}}\rceil^+ \\ \nonumber &\leq& \left
\{\begin{array}{ll}2+\log \frac{(p-a)(b-p)}{\delta^2} &
\,,\,\delta < p-a,b-p \\ 1+ \log{\frac{|b-a|}{\delta}} & \,,\,
o.w.
\end{array}\right.
\\ &\leq& 1+ 2\log{\frac{|b-a|}{\delta}}
\end{eqnarray}
as desired.
\end{proof}



\textit{Proof of Theorem \ref{thrm:memoryless}:} Assume the source
sequence $x^n$ has been encoded into the binary sequence $b^k$,
and let $Y = Y(x^\infty)$. Given $x^n$, $Y$ is uniformly
distributed over $\mathcal{I}(x^n)$, and thus for any interval
$\mathcal{T}$
\begin{equation}\label{eq:memoryless1}
\Pr(Y\in \mathcal{T} \,\big{|}\, x^n) = \frac{|\mathcal{T}\cap
\mathcal{I}(x^n)|}{|\mathcal{I}(x^n)|} \leq
\frac{|\mathcal{T}|}{|\mathcal{I}(x^n)|}
\end{equation}
The size of the interval $\mathcal{I}(x^{n+d})$ for $d\geq 0$ is
bounded by
\begin{eqnarray}
\nonumber\big{|}\mathcal{I}(x^{n+d})\big{|}  &=& \Pr(x^{n+d}) =
\Pr(x_{n+1}^{n+d} \big{|} x^n)\Pr({x^n}) \\ &=& \Pr(x_{n+1}^{n+d}
\big{|} x^n)|\mathcal{I}(x^n)|\leq \alpha^d
|\mathcal{I}(x^n)|\label{eq:memoryless2}
\end{eqnarray}
Combining (\ref{eq:memoryless1}) and (\ref{eq:memoryless2}), we
have that for any point $p\in \mathcal{I}(x^n)$
\begin{eqnarray}
\nonumber \Pr\Big{(}p\in \mathcal{I}(X^{n+d})\Big{|}\,x^n\Big{)}
&\leq& \Pr\Big{ (}|Y-p\,|
\leq {|}\mathcal{I}(x^n){|} \alpha^d\, \Big{|}\, x^n\Big{)} \\
&\leq& \frac{2\alpha^d|\mathcal{I}(x^n)|}{|\mathcal{I}(x^n)|} =
2\alpha^d\label{eq:memoryless3}
\end{eqnarray}
where the probabilities are taken w.r.t. to ``future'' source
letters. For any interval $\mathcal{T}\subseteq \mathcal{I}(x^n)$
that shares an edge with $\mathcal{I}(x^n)$ we have that
\begin{align}
\nonumber \Pr(\mathcal{T}\cap \mathcal{I}(X^{n+d})\neq \phi) \leq
\frac{\alpha^d|\mathcal{I}(x^n)| +
|\mathcal{T}|}{|\mathcal{I}(x^n)|} = \alpha^d +
\frac{|\mathcal{T}|}{|\mathcal{I}(x^n)|} \\ \label{eq:memoryless4}
\end{align}
For any $\delta\geq 0$, let $S_\delta$ denote the adjacent
$\delta$-set of $m(b^k)$ w.r.t. the interval $\mathcal{I}(x^n)$.
Given $x^n$, the probability that the delay $D$ is larger than $d$
is the probability that (\ref{eq:interval_cond}) is not satisfied,
which in turn is equal to the probability that the intersection
$S_0\cap\mathcal{I}(X^{n+d})$ is not empty. This fact is explained
as follows. As already shown, if $m(b^k)$ is strictly contained in
$\mathcal{I}(X^{n+d})$ then the encoder emits no further bits, and
the delay is larger than $d$. Otherwise, assume
$\mathcal{I}(X^{n+d})$ lies on the left side of $m(b^k)$.
Obviously, if $\mathcal{I}(X^{n+d})\subseteq
[\ell(m(b^k)),m(b^k))$, then $x^n$ is fully decoded since
(\ref{eq:interval_cond}) is satisfied. However, if $\ell(m(b^k))$
is strictly contained in $\mathcal{I}(X^{n+d})$ then
(\ref{eq:interval_cond}) is not satisfied, $x^n$ cannot be decoded
and the delay is larger than $d$. The same rationale also applies
to $r(m(b^k))$. Continuing the argument recursively, it is easy to
see that $x^n$ can be decoded if and only if no point of $S_0$ is
strictly contained in $\mathcal{I}(X^{n+d})$.

Now, notice that $S_\delta\subseteq S_0$, and that $S_0\backslash
S_\delta$ is contained in two intervals of length $\delta$ both
sharing an edge with $\mathcal{I}(x^n)$ (the situation is
illustrated in Figure \ref{fig1}). Letting $\mathcal{J}_B$ denote
a general binary interval, we bound the delay's tail probability:
\begin{eqnarray}\label{eq_delay1}
\nonumber \Pr(D > d\,\big{|}\, x^n) &=&
\Pr\left(\mathcal{I}(X^{n+d}) \not\subseteq
\mathcal{J}_B\,,\forall \mathcal{J}_B\subseteq \mathcal{I}(x^n)
\,\big{|}\,x^n\right)  \\ \nonumber &=& \Pr\left(S_0\cap
\mathcal{I}(X^{n+d}) \neq \phi\,\big{|}\,x^n\right) \leq
\\ \nonumber &\leq&  \Pr\left(S_\delta\cap \mathcal{I}(X^{n+d}) \neq
\phi\,\big{|}\,x^n\right) +\\ \nonumber &&+\;\Pr\left(\left
(S_0\backslash S_\delta\right)\cap \mathcal{I}(X^{n+d}) \neq
\phi\,\big{|}\,x^n\right) \\ \nonumber &\leq& 2\alpha^d|S_\delta
| + 2\left(\alpha^d + \frac{\delta}{|\mathcal{I}(x^n)|}\right) \leq \\
\nonumber &\leq&
\;2\alpha^d\left(1+2\log{\frac{|\mathcal{I}(x^n)|}{\delta}}\right)+
\\ &&+ 2\left(\alpha^d + \frac{\delta}{|\mathcal{I}(x^n)|}\right)
\end{eqnarray}
Lemma \ref{lem:delta_set} and equations
(\ref{eq:memoryless3}),(\ref{eq:memoryless4}) were used in the
transitions. Taking the derivative of the right-hand-side of
(\ref{eq_delay1}) w.r.t. $\delta$ we find that $\delta = 2\alpha^d
|\mathcal{I}(x^n)|$ minimizes the bound. We get:
\begin{eqnarray*}
\Pr(D > d\,\big{|}\, x^n) &\leq&
2\alpha^d\left(1+2\log{\frac{1}{2\alpha^d}}\right ) + 6\alpha^d
\\ &=& 4\alpha^d\left (1 + d \log(1\slash \alpha)\right)
\end{eqnarray*}
and (\ref{eq:delay_prob}) is proved. Now, the expectancy of $D$
given $x^n$ can be bounded accordingly
\begin{eqnarray}\label{eq:memoryless5}
\nonumber \Expt \,(D\big{|}\,x^n) &=& \sum_{d=1}^\infty
d\Pr(D=d\,\big{|}\,x^n) = \sum_{d=1}^\infty \Pr(D\geq d\,\big{|}\,
x^n) \\ \nonumber &\leq& 1+\sum_{d=1}^\infty \Pr(D > d\,\big{|}\,
x^n) \\ \nonumber &\leq& 1+4\sum_{d=1}^\infty \alpha^d\left (1 + d
\log(1\slash \alpha)\right) \\
%\nonumber &=& 1+ 4\sum_{d=1}^\infty
%\alpha^d + 4\log(1\slash \alpha)\sum_{d=1}^\infty d\alpha^d \\
&=& 1+\frac{4\alpha\big{(}1-\alpha+ \log(1\slash
\alpha)\big{)}}{(1-\alpha)^2}
\end{eqnarray}
and (\ref{eq:delay_s}) is proved. Notice that both of the bounds
above are uniform so the dependence on $x^n$ can be removed.
\begin{figure}[htbp]
  \begin{center}
    \leavevmode
    \epsfig{file=drawing1.eps, scale = 0.35}
    \caption{Source interval illustration}
    \label{fig1}
  \end{center}
  \vspace{-0.5cm}
\end{figure}
\endproof


\section{Improving Gallager's Bound}\label{sec:improving_gallager}
Gallager \cite{gallager_lecture_notes} provided an upper bound for
the expected delay in arithmetic coding of a memoryless source,
given by
\begin{equation*}
\Expt(D) \leq \frac{\log(8e^2\slash \beta)}{\log(1\slash \alpha)}
\defn \mathcal{D}_g(\alpha,\beta)
\end{equation*}
where $\alpha \defn \max p_k$ and $\beta \defn \min p_k$. Notice
that our bound $\mathcal{D}_1(\alpha)$ in (\ref{eq:delay_s})
depends only on the most likely source letter, while Gallager's
bound $\mathcal{D}_g(\alpha,\beta)$ depends also on the least
likely source letter. Moreover, holding $\alpha$ constant we find
that $\mathcal{D}_g(\alpha,\beta)\tendsto{\beta}{0}\infty$. This
phenomena is demonstrated in the following example.
%This intuitively suggests that none of the bounds will dominate
%the other. Consider the ratio of the two bounds:
%\begin{equation*}
%R(\alpha,\beta) = \frac{\mathcal{D}_1(\alpha)}{\mathcal{D}_g(\alpha,\beta)} =
%\frac{\big{(}4(1 -
%\alpha\log2\alpha)+(1-\alpha)^2\big{)}\log(1\slash
%\alpha)}{(1-\alpha)^2 \log(8e^2\slash \beta)}
%\end{equation*}
%Holding $\alpha$ constant, we easily see that
%$R(\alpha,\beta)\tendsto{\beta}{0} 0$, and thus for any
%probability assignment for the most likely source letter, there
%exists an assignment for the least probable letter for which the
%new bound is better than Gallager's bound.  Moreover, it is easily
%seen that $\mathcal{D}_g(\alpha,\beta)\tendsto{\beta}{0}\infty$, a fact which
%implies that Gallager's bound is not informative for small values
%of $\beta$ as demonstrated in the following example.

\textit{Example: Consider a ternary source with letter
probabilities $(p,\frac{1-p}{2},\frac{1-p}{2})$. Both bounds for
that source are depicted in Figure \ref{ternary2} as a function of
$p$, together with a modified bound derived in the sequel. As can
be seen, Gallager's bound is better for most values of $p$, but
becomes worse for small $p$, due to its dependence on the least
probable source letter. In fact, the bound {\em diverges} when
$p\rightarrow 0$, which is counterintuitive since we expect the
delay in this case will approach that of a uniform binary source
(for which $\mathcal{D}_g(\alpha,\beta)$ is finite). In contrast,
the new bound which depends only on the most likely letter tends
to a constant when $p\rightarrow 0$, which equals its value for
the corresponding binary case.}

Intuition suggests that least likely letters are those that tend
to accelerate the coding/decoding process, and that the dominating
factor influencing the delay should be the most likely source
letters. Motivated by that, we turn to examine the origin of the
term $\beta$ in Gallager's derivations.

%\begin{figure}[htbp]
%  \begin{center}
%    \leavevmode
%    \epsfig{file=fig1.eps, scale = 0.45}
%    \caption{Comparing the bounds for the ternary source}
%    \label{ternary1}
%  \end{center}
%\end{figure}
%\begin{figure}[htbp]
%  \begin{center}
%    \leavevmode
%    \epsfig{file=fig2.eps, scale = 0.45}
%    \caption{Comparing the bounds for the ternary source (small values of $p$)}
%    \label{ternary2}
%  \end{center}
%\end{figure}

%\begin{figure}[h]
%  \begin{center}
%$\begin{array}{@{\hspace{-0.4in}}c@{\hspace{0.3in}}c}  &
%    \\ [-0.53cm]
%\epsfxsize=2.5in \epsffile{fig1.eps} &
%    \epsfxsize=2.5in
%    \epsffile{fig2.eps} \\ [0.4cm]
%\mbox{\bf (a)} & \mbox{\bf (b)}
%\end{array}$
%  \end{center}
%\caption{Comparing the bounds for the ternary source example.
%({\bf a}) $0<p<\frac{1}{2},\,$ ({\bf b}) small values of $p$}
%\label{fig2}
%\end{figure}

Gallager's bound for the expected delay is derived via a
corresponding bound on the {\em information delay}, i.e., the
difference in self-information between a source sequence and an
extended source sequence needed to ensure that the original
sequence is completely decoded. We remind the reader that the self
information of a sequence $x^n$ is just $-\log{(\Pr(x^n))}$. We
now follow the derivations in \cite{arithmetic_coding_savari},
replacing notations with our own and modifying the proof to remove
the dependence on $\beta$. Notice that
\cite{arithmetic_coding_savari} analyzes the more general setting
of cost channels which reduces to that of
\cite{gallager_lecture_notes} and to ours and by setting $ N=2,
C=c_i=c_{max}=1$ (in the notation therein).

Consider a source sequence encoded by a binary sequence $b^k$. A
bound on the expected self-information of that sequence with the
last letter truncated is given by \cite[equations
10,11]{arithmetic_coding_savari}
\begin{equation}\label{eq:gallager1}
\Expt \big{(}I(x^{n(k)-1})\big{|} b^k\big{)} \leq k + \log (2e)
\end{equation}
where $n(k)$ is the number of source letters emitted by the
source, and $I(x^{n(k)-1})$ is the self-information of the
corresponding source sequence without the last letter. Using the
relation $I(x^n) \leq I(x^{n-1}) + \log (1\slash\beta)$, we get a
bound on the self-information of the sequence \cite[equation
14]{arithmetic_coding_savari}:
\begin{equation}\label{eq:gallager2}
\Expt \big{(}I(x^{n(k)})\big{|} b^k\big{)} \leq k + \log (2e\slash
\beta)
\end{equation}
This is the only origin of the term $\beta$. In order to obtain a
bound on the expected information delay, there seems to be no
escape from the dependence on $\beta$. However, we are interested
in the delay in source letters. We therefore continue to follow
\cite{arithmetic_coding_savari} but use (\ref{eq:gallager1}) in
lieu of (\ref{eq:gallager2}) to bound the information delay up to
one letter before the last needed for decoding. This approach
eliminates the dependence on the least likely letter, which if
appears last may increase the self-information considerably but
meanwhile contribute only a single time unit to the delay.

Consider a specific source sequence $x^n$. A bound on the expected
number of bits $k(n)$ required to decode that sequence is given by
\cite[equation 15]{arithmetic_coding_savari}:
\begin{equation}\label{eq:gallager3}
\Expt \big{(}k(n)\big{|}x^n\big{)} \leq I(x^n) + \log (4e)
\end{equation}
Now, let $b^{k(n)}$ be the binary sequence required to decode
$x^n$. Using (\ref{eq:gallager1}) (instead of (\ref{eq:gallager2})
used in \cite{gallager_lecture_notes} and
\cite{arithmetic_coding_savari}) we have that
\begin{equation}\label{eq15}
\Expt \big{(}I(x^{n+D-1})\big{|}b^{k(n)},x^n\big{)} \leq k(n) +
\log (2e)
\end{equation}
where $D$ is the number of extra letters needed to ensure the
encoder emits the necessary $k(n)$ bits. Using
(\ref{eq:gallager3}) and taking the expectation w.r.t. $k(n)$ we
find that
\begin{equation}\label{eq:gallager4}
\Expt \big{(}I(x^{n+D-1})\big{|}x^n\big{)} -I(x^n) \leq \log
(8e^2)
\end{equation}
and the modified bound for the delay in source letters follows
through by dividing (\ref{eq:gallager4}) by the minimal letter
self-information $\log (1\slash \alpha)$ and rearranging the
terms:
\begin{equation}\label{eq:gallager5}
\Expt \big{(}D\big{|}x^n\big{)} \leq 1+\frac{\log (8e^2)}{\log
(1\slash \alpha)} \defn \mathcal{D}_{mg}(\alpha)
\end{equation}
Notice that the modified Gallager bound
$\mathcal{D}_{mg}(\alpha)=\mathcal{D}_g(\alpha,\alpha)$ is
uniformly lower $\mathcal{D}_g(\alpha,\beta)$, and coincides with
it only for uniformly distributed sources.


%
%
%
%
%Consider a source sequence that is encoded by a given sequence
%$b^k$. A bound on the expected self-information of that sequence
%with the last letter truncated is given by \cite[equations
%10,11]{arithmetic_coding_savari}
%\begin{equation}\label{eq9}
%\Expt \big{(}I(x^{n(k)-1})\big{|} b^k\big{)} \leq k + \log (2e)
%\end{equation}
%where $n(k)$ is the number of source letters emitted by the
%source, and $I(x^{n(k)-1})$ is the self-information of the
%corresponding source sequence without the last letter. Now, using
%the relation $I(x^n) \leq I(x^{n-1}) + \log (1\slash\beta)$, we
%get a bound on the self-information of the sequence itself
%\cite[equation 13]{arithmetic_coding_savari}:
%\begin{equation}\label{eq10}
%\Expt \big{(}I(x^{n(k)})\big{|} b^k\big{)} \leq k + \log (2e\slash
%\beta)
%\end{equation}
%This is the (only) origin of the term $\beta$. Further, consider a
%specific source sequence $x^n$. A bound on the expected number of
%bits $k(n)$ required to decode that sequence is given by
%\cite[equation 15]{arithmetic_coding_savari}:
%\begin{equation}\label{eq11}
%\Expt \big{(}k(n)\big{|}x^n\big{)} \leq I(x^n) + \log (4e)
%\end{equation}
%Now, let $b^{k(n)}$ be the bit sequence required to decode $x^n$.
%Using (\ref{eq10}) we have that
%\begin{equation}\label{eq12}
%\Expt \big{(}I(x^{n+D})\big{|}b^{k(n)},x^n\big{)} \leq k(n) + \log
%(2e\slash \beta)
%\end{equation}
%where $D$ is the number of extra letters needed to ensure the
%encoder emits the necessary $k(n)$ bits. Using (\ref{eq11}) and
%taking the expectation w.r.t. $k(n)$ (given $x^n$) we find the
%bound for the expected information delay \cite[equation
%17]{arithmetic_coding_savari}:
%\begin{equation}\label{eq13}
%\Expt \big{(}I(x^{n+D})\big{|}x^n\big{)} -I(x^n) \leq \log
%(8e^2\slash \beta)
%\end{equation}
%and the bound for the delay in source letters follows through by
%dividing (\ref{eq13}) by the minimal letter self-information $\log
%(1\slash \alpha)$, thus \cite[equation
%18]{arithmetic_coding_savari}:
%\begin{equation}\label{eq14}
%\Expt \big{(}D\big{|}x^n\big{)}\leq \frac{\log (8e^2\slash
%\beta)}{\log (1\slash \alpha)}
%\end{equation}
%
%In order to obtain a bound on the expected information delay,
%there seems to be no escape from the dependence on $\beta$.
%However, we are interested in the delay in letters. We shall
%therefore use equation (\ref{eq9}) instead of equation
%(\ref{eq10}) in the derivations, and find a bound on the
%information delay up to one letter before the last needed for
%decoding. This approach eliminates the dependence on the least
%likely letter, which if appears last in the sequence may increase
%the self-information considerably but meanwhile contribute only a
%single time unit to the delay. That is, for a given source
%sequence $x^n$ with a corresponding bit sequence $b^{k(n)}$ needed
%for decoding it, we have (instead of (\ref{eq12})):
%\begin{equation}\label{eq15}
%\Expt \big{(}I(x^{n+D-1})\big{|}b^{k(n)},x^n\big{)} \leq k(n) +
%\log (2e)
%\end{equation}
%Using (\ref{eq11}) again and taking the expectation w.r.t. $k(n)$
%we find that
%\begin{equation}\label{eq16}
%\Expt \big{(}I(x^{n+D-1})\big{|}x^n\big{)} -I(x^n) \leq \log
%(8e^2)
%\end{equation}
%and dividing by $\log (1\slash \alpha)$ to obtain a bound on the
%expectation of $D-1$ and reorganizing the terms, we finally get
%the bound
%\begin{equation}\label{eq14}
%\Expt \big{(}D\big{|}x^n\big{)} \leq 1+\frac{\log (8e^2)}{\log
%(1\slash \alpha)} \defn \mathcal{D}_{mg}(\alpha)
%\end{equation}
%Notice that the modified Gallager bound $\mathcal{D}_{mg}(\alpha)$
%is uniformly lower than Gallager's bound
%$\mathcal{D}_g(\alpha,\beta)$, and coincides with it only for
%uniformly distributed sources.



\textit{Example (continued): The modified Gallager bound for the
ternary source converges for $p\rightarrow 0$, as illustrated in
Figure \ref{ternary2}. It is also easy to verify that it converges
to the same value it takes for a uniform binary source.}

\begin{figure}[htbp]
  \begin{center}
    \leavevmode
    \epsfig{file=fig3.eps, scale = 0.5}
    \caption{Bounds for the ternary source}
    \label{ternary2}
  \end{center}
  \vspace{-0.5cm}
\end{figure}

%
%We now turn to explore the general relation between our bound and
%the modified Gallager bound. Consider the ratio
%\begin{equation*}
%R(\alpha) = \frac{\mathcal{D}_1(\alpha)}{\mathcal{D}_{mg}(\alpha)} =
%\frac{1+\frac{4\alpha\big{(}1-\alpha+ \log(1\slash
%\alpha)\big{)}}{(1-\alpha)^2}}{1+\frac{\log(8e^2)}{\log(1\slash
%\alpha)}}
%\end{equation*}
%Using the relation $\log(1\slash\alpha) =
%\log(1+\frac{1-\alpha}{\alpha}) \leq \frac{1-\alpha}{\alpha\ln 2}$
%and defining $K=\log(8e^2)$  we can bound the ratio as follows:
%\begin{equation*}
%R(\alpha) \leq \frac{1+\frac{4\alpha(1 -\alpha
%+\frac{1-\alpha}{\alpha\ln 2})}{(1-\alpha)^2}}{1+\frac{K\alpha\ln
%2}{1-\alpha}} = \frac{1-\alpha + 4(1+\frac{1}{\ln
%2})}{1+\alpha(K\ln 2-1)} = \frac{5+ \frac{4}{\ln
%2}-\alpha}{1+\alpha(K\ln 2-1)} \defn \bar{R}(\alpha)
%\end{equation*}
%Taking the derivative of $\bar{R}(\alpha)$ we have that
%\begin{equation*}
%\frac{d\bar{R}(\alpha)}{d\alpha} = \frac{-1-\alpha(K\ln 2-1)-(K\ln
%2-1)(5+ \frac{4}{\ln 2}-\alpha)}{(1+\alpha(K\ln 2-1))^2} =
%\frac{-1-(K\ln 2-1)(5+ \frac{4}{\ln 2})}{(1+\alpha(K\ln 2-1))^2} <
%0
%\end{equation*}
%and so $\bar{R}(\alpha)$ is decreasing for a growing $\alpha$. It
%is easily verified that
%\begin{equation*}
%\bar{R}(\alpha=0) = 5 + \frac{4}{\ln 2}
%\end{equation*}
%and so we have that $R(\alpha) \leq \bar{R}(\alpha) \leq 5 +
%\frac{4}{\ln 2}$ and therefore the bounds satisfy
%\begin{equation}\label{eq_ratio}
%\mathcal{D}_1(\alpha) \leq (5 + \frac{4}{\ln 2})\mathcal{D}_{mg}(\alpha) =
%10.7708...\mathcal{D}_{mg}(\alpha)
%\end{equation}

The ratio of our bound to the modified Gallager bound is depicted
in Figure \ref{fig:ratios}, together with two tighter bounds
introduced in the following section. Comparing the bounds, we find
that $\mathcal{D}_1(\alpha)$ is at most $\sim 2.4$ times worse
than $\mathcal{D}_{mg}(\alpha)$, and is even better for small
(below $\sim 0.069$) values of $\alpha$. For $\alpha\rightarrow 0$
the ratio tends to unity, since both $\mathcal{D}_1(\alpha)$ and
$\mathcal{D}_{mg}(\alpha)$ approach 1, the minimal possible delay
for a source that is not 2-adic. Indeed, for a very small $\alpha$
it is intuitively clear that even when a single extra letter is
encoded, the source interval decreases significantly which enables
decoding of the preceding source interval with high probability.

\section{Improving Our Bound}\label{sec:improving_bound}
As we have seen, $\mathcal{D}_1(\alpha)$ is good for small values
of $\alpha$ (the probability of the most likely letter) and
becomes worse for larger values. The source of this behavior lies
in a somewhat loose analysis of the size of $S_\delta$ for large
$\delta$, and also since for large $\alpha$ and small $d$ the
bound (\ref{eq:delay_prob}) may exceed unity. A more subtle
analysis enables us to improve our bound for large $\alpha$, and
the result is now stated without proof.
\begin{theorem}\label{thrm:memoryless_tighter}
\textit{Let $d_0 = \left\lfloor
\frac{2}{\log(1\slash\alpha)}\right\rfloor$, and define $d_1\geq
d_0$ to be the largest such integer for which every integer $d_0 <
d\leq d_1$ (if there are any) satisfies
\begin{equation*}
2\alpha^d\left (1 + 2d \log(1\slash \alpha)\right) > 1
\end{equation*}
The expected delay of an arithmetic coding system for a memoryless
source is bounded by
\begin{eqnarray}
&&\Expt \,(D) \leq  \mathcal{D}_2(\alpha) \defn \\ &&\nonumber 1+
d_1 + \frac{2\alpha^{d_1+1}}{1-\alpha} +
\frac{4\alpha^{d_1+1}\big{(}d_1(1-\alpha)+1\big{)}\log(1\slash
\alpha)}{(1-\alpha)^2}
\end{eqnarray}}

\end{theorem}

%The bound on the size of $S_\delta(p)$ given in
%(\ref{eq_delta_set}) can be improved for
%$\delta\leq\frac{b-a}{2}$:
%\begin{equation*}
%|S_\delta(p)| \leq 2\log\frac{|b-a|}{\delta}\,,\quad \forall
%\delta \leq \frac{b-a}{2}
%\end{equation*}
%
%Following the derivation of equation (\ref{eq_delay1}) we now have
%that for $\delta\leq\frac{|\mathcal{I}(x^n)|}{2}$
%\begin{equation*}
%\Pr(D > d\,\big{|}\, x^n) \leq 2\alpha^d|S_\delta | +
%2\left(\alpha^d + \frac{\delta}{|\mathcal{I}(x^n)|}\right) \leq
%4\alpha^d\log{\frac{|\mathcal{I}(x^n)|}{\delta}} + 2\left(\alpha^d
%+ \frac{\delta}{|\mathcal{I}(x^n)|}\right)
%\end{equation*}
%The minimizing value is again $\delta = 2\alpha^d
%|\mathcal{I}(x^n)|$, which must also satisfy the requirement that
%$\delta\leq\frac{|\mathcal{I}(x^n)|}{2}$, so we get the following
%bound which is valid only for $d > \left\lfloor
%\frac{2}{\log(1\slash\alpha)}\right\rfloor$:
%\begin{equation}\label{eq_mod_bound}
%\Pr(D > d\,\big{|}\, x^n) \leq 2\alpha^d\left (1 + 2d \log(1\slash
%\alpha)\right)
%\end{equation}
%Now, let $d_0 = \left\lfloor
%\frac{2}{\log(1\slash\alpha)}\right\rfloor$, and define $d_1\geq
%d_0$ to be the largest such integer for which every integer $d_0 <
%d\leq d_1$ (if there are any) satisfies
%\begin{equation*}
%2\alpha^d\left (1 + 2d \log(1\slash \alpha)\right) > 1
%\end{equation*}
%We now replace the bound in (\ref{eq_mod_bound}) for $d\leq d_1$
%with unity, and the expected delay is bounded as follows:
%\begin{eqnarray}
%\nonumber \Expt \,(D\big{|}\,x^n) &\leq& 1+d_1 +\sum_{d=d_1+1
%}^\infty \Pr(D
%> d\,\big{|}\, x^n) \leq 1+ d_1 + 2\sum_{d=d_1+1}^\infty \alpha^d\left (1 + 2d
%\log(1\slash \alpha)\right) \\ \nonumber &\leq&   1+ d_1 +
%\frac{2\alpha^{d_1+1}}{1-\alpha} +
%\frac{4\alpha^{d_1+1}\big{(}\alpha+(d_1+1)(1-\alpha)\big{)}\log(1\slash
%\alpha)}{(1-\alpha)^2} \defn \mathcal{D}_2(\alpha)
%\end{eqnarray}

%An explicit bound $\mathcal{D}_3(\alpha)$ (but looser for large $\alpha$)
%can be obtained by substituting $d_1 = d_0$.

%so we get
%\begin{equation}
%\Expt \,(D\big{|}\,x^n) \leq 1+ \left\lfloor\frac{2}{\log(1\slash
%\alpha)}\right\rfloor +
%\frac{2\alpha^{(\left\lfloor\frac{2}{\log(1\slash
%\alpha)}\right\rfloor+1)}}{1-\alpha} +
%\frac{4\alpha^{(\left\lfloor\frac{2}{\log(1\slash
%\alpha)}\right\rfloor+1)}\left(\alpha+(\left\lfloor\frac{2}{\log(1\slash
%\alpha)}\right\rfloor+1)(1-\alpha)\right)\log(1\slash
%\alpha)}{(1-\alpha)^2} \defn \mathcal{D}_3(\alpha)
%\end{equation}
%\vspace{-1.2cm}
%\begin{figure}[htbp]
%  \begin{center}
%    \leavevmode
%    \epsfig{file=fig5.eps, scale = 0.5}
%    \caption{The ratio of the different bounds to the modified Gallager bound}
%    \label{fig5}
%  \end{center}
%\end{figure}
An explicit bound $\mathcal{D}_3(\alpha)$ (though looser for large
$\alpha$) can be obtained by substituting $d_1 = d_0$. The ratio
of our original bound $\mathcal{D}_1(\alpha)$, the modified bound
$\mathcal{D}_2(\alpha)$ and its looser version
$\mathcal{D}_3(\alpha)$ to the modified Gallager bound
$\mathcal{D}_{mg}(\alpha)$ are depicted in Figure
\ref{fig:ratios}. As can be seen, $\mathcal{D}_2(\alpha)$ is
tighter than $\mathcal{D}_{mg}(\alpha)$ for values of $\alpha$
smaller than $\sim 0.71$, and for larger values is looser but only
up to a multiplicative factor of $\sim 1.04$. Notice again that
all of the bounds coincide for $\alpha\rightarrow 0$, as in this
case they all tend to 1 which is the best possible general upper
bound.

\begin{figure}[htbp]
  \begin{center}
    \leavevmode
    \epsfig{file=fig5.eps, scale = 0.5}
    \caption{The ratio of the different bounds to the modified Gallager bound}
    \label{fig:ratios}
  \end{center}
    \vspace{-0.2cm}
\end{figure}

\section{Sources with Memory}\label{sec:memory}
The discussion of section \ref{sec:memoryless} is easily
generalized to sources with memory. The only point in the proof
that needs to be reestablished is the definition of $\alpha$,
which was the probability of the most likely source letter in the
memoryless case.
\begin{theorem}\label{thrm:memory}
\textit{Consider an arithmetic coding system for a source with a
probability distribution $p(x^n)$ over a finite alphabet
$\mathcal{X}$. Let
\begin{equation*}
\gamma(d) \defn \sup_n
\max_{x^{n+d}\in\mathcal{X}^{n+d}}p(x^{n+d}\,\big{|}\,x^n)
\end{equation*}
If $\,\gamma(d) = o\left(d^{\,-(1+\varepsilon)}\right)$ for some
$\varepsilon>0$, then the expected delay of the system is
bounded.}
\end{theorem}
\begin{proof}
The derivations for the memoryless case can be repeated, with
$\alpha^d$ replaced by $\gamma(d)$. The bound
(\ref{eq:memoryless5}) becomes
\begin{equation*} \Expt \,(D\,\big{|}\,x^n) \leq 1+
4\sum_{d=1}^\infty \gamma(d)\left (1 +
\log{\frac{1}{\gamma(d)}}\right)
\end{equation*}
If the sum above converges, then we have the bounded expected
delay property. The condition given in Theorem \ref{thrm:memory}
is sufficient to that end.
\end{proof}

For a memoryless source, $\gamma(d) = \alpha^d$ and the condition
is satisfied. It is also fulfilled for any source with memory
whose conditional letter probabilities are bounded away from 1,
and thus such sources admit a bounded expected delay. This fact
was already observed in \cite{arithmetic_coding_savari} with the
additional requirement for the conditional probabilities to be
bounded away from 0 as well (a byproduct of the dependency on the
least favorable letter). The condition in Theorem
\ref{thrm:memory} is however more general. As an example, consider
a stationary ergodic first order Markov source. Such a source
satisfies
\begin{equation}\label{eq:memory_p1}
p(x^{n+|\mathcal{X}|}\,\big{|}\,x^n) < 1\,,\quad
\forall\,x^{n+|\mathcal{X}|}\in \mathcal{X}^{n+|\mathcal{X}|}
\end{equation}
since otherwise the source would have a deterministic cycle which
contradicts the ergodic assumption. Define:
\begin{equation*}
\xi \defn \max_{x^{n+|\mathcal{X}|}\in
\mathcal{X}^{n+|\mathcal{X}|}}
p(x^{n+|\mathcal{X}|}\,\big{|}\,x^n)
\end{equation*}
We have from (\ref{eq:memory_p1}) that $\xi < 1$, and since the
source is stationary, $\xi$ is also independent of $n$.
$\gamma(d)$ is monotonically non-increasing and therefore
$\gamma(d) \leq
\xi^{\left\lfloor\frac{d}{|\mathcal{X}|}\right\rfloor}$ and is
exponentially decreasing with $d$, thus satisfying the condition
in Theorem \ref{thrm:memory}. This result can be generalized to
any Markov order.
\begin{corollary}
\textit{The expected delay of arithmetic coding for a finite
alphabet, stationary ergodic Markov source of any order is
bounded.}
\end{corollary}


\section{Summary}\label{sec:summary}
New upper bounds on the expected delay of an arithmetic coding
system for a memoryless source were derived, as a function of the
probability $\alpha$ of the most likely source letter. In
addition, a known bound due to Gallager that depends also on the
probability of the least likely source letter was uniformly
improved by disposing of the latter dependence. Our best bound was
compared to the modified Gallager bound, and shown to be tighter
for $\alpha < 0.71$ and looser by a multiplicative factor no
larger than $\sim 1.04$ otherwise. The bounding technique was
generalized to sources with memory, providing a sufficient
condition for a bounded delay. Using that condition, it was shown
that the bounded delay property holds for a stationary ergodic
Markov source of any order.

Future research calls for a more precise characterization of the
expected delay in terms of the entire probability distribution,
which might be obtained by further refining the bounding technique
presented in this paper. In addition, a generalization to coding
over cost channels and finite-state noiseless channels in the
spirit of \cite{arithmetic_coding_savari} can be considered as
well.

\bibliographystyle{IEEEbib}
\bibliography{ofer_refs}


%\begin{thebibliography}{3}
%\bibitem{Rissanen}
%J. Rissanen, ``Generalized Kraft Inequality and Arithmetic
%Coding,'' {\em IBM Journal of Research and Development},
%20:198-203.
%
%\bibitem{class}
%R. Zamir, Lecture Notes on Data and Signal Compression.
%
%\bibitem{Gallager}
%R.G. Gallager, Lecture Notes on Information Theory (Unpublished).
%
%
%\end{thebibliography}
%

\end{document}

new_shorts.tex

%\renewcommand{\baselinestretch}{1.48}
%\renewcommand{\baselinestretch}{1.23}
%\setlength{\oddsidemargin}{-6.4mm} \setlength{\topmargin}{-0.3in}
%\setlength{\textheight}{226mm} \setlength{\textwidth}{175mm}
%\setlength{\columnsep}{8mm}

\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
\newtheorem{theorem}{Theorem}
\newtheorem{definition}{Definition}
\newtheorem{algorithm}{Algorithm}
\newtheorem{proposition}{Proposition}
\newtheorem{conjecture}{Conjecture}
%\newtheorem*{theorem*}{Theorem}
%\theoremstyle{definition}
\newtheorem{example}{Example}
%\newtheorem*{example*}{Example}
\newcommand{\bre}{\begin{equation}}
\newcommand{\ere}{\end{equation}}
\newcommand{\be}\[
\newcommand{\ee}\]
\newcommand{\bra}{\begin{eqnarray}}
\newcommand{\era}{\end{eqnarray}}
\newcommand{\ba}{\begin{eqnarray*}}
\newcommand{\ea}{\end{eqnarray*}}
\newcommand{\bfg}{\begin{figure}[hbtp]}
\newcommand{\efg}{\end{figure}}
\newcommand{\bver}{\begin{verbatim}}
\newcommand{\ever}{\end{verbatim}}
\newcommand{\bit}{\begin{itemize}}
\newcommand{\eit}{\end{itemize}}
\newcommand{\ben}{\begin{enumerate}}
\newcommand{\een}{\end{enumerate}}
\newcommand{\ett}{\mbox{$\eta$} }
\newcommand{\coeff}[1]{\lfloor #1\rfloor}
\newcommand{\ceil}[1]{\lceil #1\rceil}
\newcommand{\floor}[1]{\lfloor #1 \rfloor}
\newcommand{\bfloor}[1]{\left\lfloor #1 \right\rfloor}
\newcommand{\dgr}[1]{\mbox{$#1^{\circ}$}}
%\newcommand{\th}[1]{\mbox{$\theta_{\rm #1}$}}
\newcommand{\cu}{\mbox{cosmic $\mu$ }}
\newcommand{\csa}[2]{\mbox{$\cos^2(#1 - #2)$}}
\newcommand{\csb}[2]{\mbox{$\cos2(#1 - #2)$}}

\newcommand{\Exp}{\mbox{E}}
\newcommand{\given}{\: | \:}
\newcommand{\Ker}{\mbox{Ker}\,}
\newcommand{\tildepss}{\tilde \epsilon_{s}}
\newcommand{\tildepssl}{\tilde \epsilon_{s_l}}
\newcommand{\epss}{\epsilon_s}
\newcommand{\epssl}{\epsilon_{s_l}}

\newcommand{\bT}{{\bf T}}
\newcommand{\bl}{{\bf l}}
\newcommand{\bk}{{\bf k}}
\newcommand{\bh}{{\bf h}}

\newcommand{\norm}[1]{\|#1\|}
\newcommand{\tN}{\tilde N}
\newcommand{\tA}{\tilde A}
\newcommand{\tX}{\tilde X}
\newcommand{\tc}{\tilde c}
\newcommand{\tv}{\tilde v}
\newcommand{\tH}{\tilde H}
\newcommand{\btH}{\tilde {\bf H}}
\newcommand{\btX}{\tilde {\bf X}}
\newcommand{\btv}{\tilde {\bf v}}
\newcommand{\btc}{\tilde {\bf c}}
\newcommand{\tab}{\ \ \ \ }
\newcommand{\bS}{\bar{S}}
\newcommand{\bc}{{\bf c}}
\newcommand{\type}{{\mathrm type}}
\newcommand{\GF}{{\mathrm GF}}
%\newcommand{\mod}{{\mathrm mod\:}}
\newcommand{\bs}{{\bf s}}
\newcommand{\bp}{{\bf p}}
\newcommand{\bX}{{\bf X}}
\newcommand{\bY}{{\bf Y}}
\newcommand{\bH}{{\bf H}}
\newcommand{\DFT}{{\mathrm DFT}}
\newcommand{\IDFT}{{\mathrm IDFT}}
\newcommand{\ldeg}{{\mathrm ldeg}}
\newcommand{\Real}{{\mathrm Re\:}}
\newcommand{\Imag}{{\mathrm Im\:}}
\newcommand{\E}{{\mathrm E}}
\newcommand{\weight}{{\mathrm wt}}
\newcommand{\xor}{\oplus}
\newcommand{\bu}{{\bf u}}
\newcommand{\bv}{{\bf v}}
\newcommand{\bt}{{\bf t}}
\newcommand{\bD}{{\bf D}}
\newcommand{\bw}{{\bf w}}
\newcommand{\bhw}{{\bf \hat w}}
\newcommand{\bn}{{\bf n}}
\newcommand{\bx}{{\bf x}}
\newcommand{\by}{{\bf y}}
\newcommand{\bz}{{\bf z}}
\newcommand{\bzr}{{\bf 0}}
\newcommand{\cR}{{\cal R}}
\newcommand{\cE}{{\cal E}}
\newcommand{\cS}{{\cal S}}
\newcommand{\cT}{{\cal T}}
\newcommand{\cX}{{\cal X}}
\newcommand{\cY}{{\cal Y}}
\newcommand{\oS}{\overline{S}}
\newcommand{\oP}{\overline{P}}
\newcommand{\tP}{\tilde{P}}
\newcommand{\cC}{{\mathcal{C}}}
\newcommand{\cN}{{\mathcal{N}}}
\newcommand{\cG}{\mathcal{G}}
\newcommand{\hcC}{\hat{\mathcal{C}}}
\newcommand{\cD}{{\mathcal{D}}}
\newcommand{\hcD}{\hat{\mathcal{D}}}
\newcommand{\hD}{\hat{D}}
\newcommand{\tcD}{\tilde{\mathcal{D}}}
\newcommand{\tcC}{\tilde{\cal C}}
\newcommand{\tC}{\tilde{C}}
\newcommand{\hA}{\hat{A}}
\newcommand{\hC}{\hat{C}}
\newcommand{\hc}{\hat{c}}
\newcommand{\hg}{\hat{g}}
\newcommand{\hw}{\hat{w}}
\newcommand{\tbc}{\tilde{\bf c}}
\newcommand{\hbc}{\hat{\bf c}}

\newcommand{\balpha}{\mbox{\boldmath $\alpha$}}
\newcommand{\bxi}{\mbox{\boldmath $\xi$}}
\newcommand{\btheta}{\mbox{\boldmath $\theta$}}
\newcommand{\blambda}{\mbox{\boldmath $\lambda$}}
\newcommand{\brho}{\mbox{\boldmath $\rho$}}
\newcommand{\bchi}{\mbox{\bf x}}
\newcommand{\bPhi}{{\bf \Phi}}
\newcommand{\bPsi}{{\bf \Psi}}
\newcommand{\bhPhi}{{\bf \hat \Phi}}
\newcommand{\bhPsi}{{\bf \hat \Psi}}
\newcommand{\bal}{\mbox{\boldmath $\alpha$}_0}

%\newcommand{\beginproof}{\textit{Proof.}  }
%\newcommand{\finproof}{\noindent $\Box$\\}
\def\defined{\: {\stackrel{\scriptscriptstyle \Delta}{=}} \: }
\def\psdir#1{#1}
\def\MSE{{\rm MSE}}
\def\argmax{\mathop{\rm argmax}}
\def\CB{\mathop{\rm BS}}
\def\defined{\: {\stackrel{\scriptscriptstyle \Delta}{=}} \: }
\def\leqa{\buildrel \rm {\scriptscriptstyle (1)} \over \leq}
\def\leqb{\buildrel \rm {\scriptscriptstyle (2)} \over \leq}
\def\leqc{\buildrel \rm {\scriptscriptstyle (3)} \over \leq}
\def\eqa{\buildrel \rm {\scriptscriptstyle (1)} \over =}
\def\eqb{\buildrel \rm {\scriptscriptstyle (2)} \over =}
\def\eqc{\buildrel \rm {\scriptscriptstyle (3)} \over =}

\newcommand{\refeq}[1]{(\ref{#1})}
\newcommand{\labeleq}[1]{\label{eq:#1}}
\newcommand{\refsec}[1]{(\ref{section:#1})}
\newcommand{\labelsec}[1]{\label{section:#1}}

\newcommand{\comment}[1]{}
\newcommand{\topc}[1]{$\stackrel{\circ}{\rm #1}$}
\newcommand{\tobecompleted}[1]{$<$ \textbf{To be completed: #1} $>$}
\newcommand{\ShowDavid}[1]{$<$~\textbf{Show David: #1}~$>$}
\newcommand{\ShowDavidAfterComments}[1]{$<$ \textbf{Show David after comments: #1} $>$}

\def\etal{$et \,\,al.\,\,$}

%\renewcommand{\thesection}{\Roman{section}}

% Definition for BIGBAR...
\newlength{\tmpbigbar}
\newcommand{\bigbar}[1]{
 \setlength{\tmpbigbar}{\unitlength}
 \settowidth{\unitlength}{\mbox{$#1$}}
  \stackrel{\barpic}{#1}
 \setlength{\unitlength}{\tmpbigbar}
}
\newcommand{\barpic}{\begin{picture}(1,0.01)(0,0)
\put(0.15,0){\line(12,0){0.7}}
\end{picture}
}
% end of definition BIGBAR

\newcommand{\vect}[1]
{\mbox{\boldmath $#1$}}

\newcommand{\vecth}[1]
{\hat{\mbox{\boldmath$#1$}}}

\newcommand{\tendsto}[2]
{\raisebox{-1.2ex}{$\stackrel{\textstyle \longrightarrow}{
\scriptscriptstyle #1\rightarrow #2}$}}

\newcommand{\overfrac}[3]
{\stackrel{\textstyle \mathrm{#1}}{\scriptstyle
#2}\raisebox{1.4ex}{$\textstyle #3$}}

\newcommand{\tr}{{\scriptscriptstyle T}}
\newcommand{\inv}{{\scriptscriptstyle -1}}

\newfont{\boldlarge}{msbm10 scaled 1100}
\newcommand{\RealF}{\mbox{\boldlarge R}}
\newcommand{\CompF}{\mbox{\boldlarge C}}
\newcommand{\Expt}{\mbox{\boldlarge E}}
\newcommand{\defn}{ \stackrel{\triangle}{=} }
\newcommand{\IntF}{\mbox{\boldlarge Z}}

\def\sketchproof{\noindent\hspace{2em}{\itshape Sketch of the proof: }}

\def\cN{{\cal N}}

AC_delay_isit.bbl
\begin{thebibliography}{1}

\bibitem{arithmetic_coding_jelink}
F.~Jelink,
\newblock {\em Probabilistic Information Theory},
\newblock McGraw-Hill, New York, 1968.

\bibitem{arithmetic_coding_rissanen}
J.~Rissanen,
\newblock ``Generalized kraft inequality and arithmetic coding,''
\newblock {\em IBM Journal of Research and Development}, vol. 20, pp. 198 --
  203, 1976.

\bibitem{arithmetic_coding_pasco}
R.~Pasco,
\newblock {\em Source Coding Algorithm for Fast Data Compression},
\newblock Ph.d dissertation, Dep. Elec. Eng., Stanford Univ., Stanford, CA,
  1976.

\bibitem{IT_cover}
T.~Cover and J.~Thomas,
\newblock {\em Elements of Information Theory},
\newblock John Wiley \& Sons, Inc., New York, 1991.

\bibitem{gallager_lecture_notes}
R.G. Gallager,
\newblock {\em Lecture Notes (unpublished)},
\newblock 1991.

\bibitem{arithmetic_coding_savari}
S.A. Savari and R.G. Gallager,
\newblock ``Arithmetic coding for finite-state noiseless channels,''
\newblock {\em IEEE Trans. Info. Theory}, vol. 40, pp. 100 -- 107, 1994.

\end{thebibliography}
