1 Introduction↩︎

1.1 Objectives and motivation↩︎

A variable-to-variable (V2V) length source code is the most general member of the family of lossless codes considered here. It parses the source into phrases of variable length and encodes each phrase with a binary codeword of variable length, combining the structural advantages of variable-to-fixed (V2F) length coding – which adapts the parsing to source statistics – with those of fixed-to-variable (F2V) length coding – which adapts codeword lengths to symbol probabilities.

The standard performance measure for a V2V length code is its asymptotic compression rate, \(\rho = \mathbb{E}\{\ell\}/\mathbb{E}\{L\}\), the ratio of expected codeword length to expected phrase length. Let \(\Lambda_n\) and \(\Sigma_n\) denote, respectively, the total codeword length (in bits) and the total source-symbol count after \(n\) encoded phrases. By the strong law of large numbers (\(\Lambda_n/n\to\mathbb{E}\{\ell\}\) and \(\Sigma_n/n\to\mathbb{E}\{L\}\) almost surely) and the continuous mapping theorem [1], the realized compression ratio \(R_n = \Lambda_n/\Sigma_n\) converges to \(\rho\) almost surely as \(n\to\infty\). This asymptotic rate, however, answers neither how quickly convergence occurs nor how large the fluctuations around \(\rho\) are at any finite number of encoded phrases \(n\). Both questions are practically important. In buffer analysis for variable-length codes, the fluctuation of the compression ratio over a finite window directly determines buffer overflow probabilities. In code design, comparing candidate codes requires evaluating their performance at finite \(n\), not merely their limit.

We address these questions by deriving exact formulas for all integer moments of \(R_n\), for a given V2V length code and a memoryless source. This is fundamentally an analysis of a given code’s finite-sample behavior, not a code-design method; the joint design of the parsing tree and codeword lengths for a target \(n\) remains open (see Section 2.5). Our main result is an exact formula for \(\mathbb{E}\{R_n^k\}\) for every positive integer \(k\) as a single one-dimensional integral, requiring only the single-phrase joint moment generating function (MGF) of \((L,\ell)\). The underlying tool is an integral representation of \(1/\Sigma_n\) as well as its \(k\)-th power as a Laplace transform, which enables turning a ratio of sums into a one-dimensional integral of simple single-phrase quantities. The novelty is in the systematic extension to every integer moment via the set-partition combinatorics of Theorem 4; the fact that the resulting formulas are exact at every finite \(n\) rather than asymptotic; and the further extension to Markov sources (Section 5), which replaces scalar moment generating functions by matrix-valued ones and requires a corresponding eigenvalue-perturbation argument with no scalar analogue. From these moments we derive closed-form asymptotic formulas for the bias constant \(\lim_{n\to\infty}n(\mathbb{E}\{R_n\}-\rho)\) and the variance constant \(\lim_{n\to\infty} n\mathrm{Var}\{R_n\}\), and we construct an Edgeworth approximation to the CDF of \(R_n\) that is substantially more accurate than the central limit theorem (CLT). Before turning to this analysis, Section 2 records some necessary background, including a compression-rate lower bound obtained by observing that a V2V length code is an instance of the finite-state encoders covered by the generalized Kraft inequality of [2]; this observation sets the stage for the moment analysis but is logically independent of it. Unlike the classical route to such a bound – concatenating many phrases and invoking a law-of-large-numbers argument to identify the limiting rate – the generalized-Kraft-inequality bound is a direct, purely algebraic consequence of a single spectral-radius inequality, with no block-length limit theorem involved.

1.2 Related work↩︎

The V2F and V2V length coding literature is relatively sparse. Existing work, surveyed in [3], focuses on the average redundancy of specific named codes (Huffman, Tunstall, Khodak, Boncelet) for known sources, using analytic combinatorics and Mellin-transform methods; Savari and Szpankowski [4] give an early analysis specifically of V2V length codes along these lines. The moments of \(R_n\) at finite \(n\), as distinct from the asymptotic rate \(\rho\), have not been addressed.

1.2.0.1 V2F length coding.

Tunstall’s algorithm [5] constructs an optimal uniquely parsable V2F dictionary by a simple greedy procedure. Savari and Gallager [6] established the asymptotic redundancy of Tunstall codes using renewal theory (modeling self-information as a regenerative process) and Markov reward machinery; their analysis brings in second moments of inter-renewal times, but only as a correction to the precision of an asymptotic mean formula, not as a variance target. Drmota, Reznik, and Szpankowski [7] established a CLT and a variance formula for the V2F phrase length \(L\), via renewal theory and Mellin transforms, as the dictionary size \(M\to\infty\). Both bodies of work address the phrase length \(L\) alone, under a fixed-length codeword assignment, as a function of a growing dictionary; our asymptotic variable is the number of phrases \(n\) processed by a fixed code, and our object is the ratio \(R_n = \Lambda_n/\Sigma_n\) rather than \(L\).

1.2.0.2 Plurally parsable dictionaries.

Savari [8], [9] showed that relaxing unique parsability can outperform the Tunstall dictionary of the same size for highly predictable sources, with exact results for specific binary-source families but no general algorithm.

1.2.0.3 Delay and redundancy.

Shayevitz, Meron, Feder, and Zamir [10] characterize the redundancy–delay trade-off for V2V and related code families. Their object is the expected per-symbol code length as a function of a worst-case delay constraint, not the moments of \(R_n\) as the number of phrases grows.

1.2.0.4 Codeword-length distributions.

Courtade and Verdú [11] study the CGF and Gaussian approximation of the codeword length of an optimal F2V length code on an \(n\)-symbol block, tracing back to Strassen’s foundational second-order asymptotic analysis [12] and complementing Kontoyiannis’s earlier second-order noiseless source coding theorems [13] (which also covers Markov sources) and the non-asymptotic refinements of Kontoyiannis and Verdú [14]. This is a single i.i.d.sum, not a ratio of two correlated sums with a random denominator; the ratio structure is specific to V2V and V2F coding and is the source of the combinatorial complexity addressed in the present paper.

1.2.0.5 Generalized Kraft inequality.

Merhav [2] establishes a generalized Kraft inequality for finite-state encoders, strictly improving the earlier result of Ziv and Lempel [15]. We use this to derive an explicit lower bound on the V2V compression ratio in terms of the parsing tree structure.

2 System model and background on V2V codes↩︎

2.1 Source model and notation↩︎

We consider a discrete memoryless source (DMS) \(X_1,X_2,\dots\), where each symbol \(X_i\) (\(i\) – positive integer) is a random variable taking values in a finite alphabet \(\mathcal{X}\) of cardinality \(\alpha\); specific realizations are denoted by \(x_1,x_2,\dots\). Each symbol is drawn according to the source distribution \(P=\{P(x),~x\in\mathcal{X}\}\). The single-letter entropy is \[\label{eq:entropy} H(X) = -\sum_{x\in\mathcal{X}} P(x)\log_2 P(x).\tag{1}\] A V2V length code is specified by two components:

1. A source dictionary \(\mathcal{D}\): a prefix-free set of variable-length source strings, represented by the leaves of a complete \(\alpha\)-ary tree. The size of the dictionary is \(|\mathcal{D}|=M\), and a generic member of \(\mathcal{D}\) is denoted by \(y\). A source string \(x_1,x_2,\dots\) is parsed by the dictionary parser into a succession of phrases \(y_1,y_2,\dots\); the corresponding random variables \(Y_1,Y_2,\dots\), induced by the source \(P\), form another DMS with alphabet \(\mathcal{D}\) (of size \(M\)) and phrase probabilities \(\{Q(y),\,y\in\mathcal{D}\}\), where each \(Q(y)\) is given by the product of the letter probabilities that make up the phrase \(y\). Let \(L(y)\), \(y\in\mathcal{D}\), denote the length of phrase \(y\), in source symbols. We denote by \(H(Y)\stackrel{\Delta} {=}-\sum_{y\in\mathcal{D}}Q(y)\log_2 Q(y)\) the phrase entropy.

2. A variable-length uniquely decodable (UD) code, mapping \(\mathcal{D}\) into a set of variable-length binary strings. Let \(\ell(y)\) denote the length, in bits, of the codeword assigned to \(y\in\mathcal{D}\).

We index the successive phrases produced by the parser by \(i=1,2,\dots\); the \(i\)-th phrase is \(Y_i\), of length \(L(Y_i)\) source symbols, encoded by a codeword of length \(\ell(Y_i)\) bits. For a DMS, the pairs \((L(Y_i),\ell(Y_i))_{i\ge1}\) are independent and identically distributed; we write \(Y\) for a generic random phrase with distribution \(Q\), so that \(L(Y)\) and \(\ell(Y)\) denote its length and its codeword length, respectively. When it causes no ambiguity, we abbreviate \(L(Y)\) and \(\ell(Y)\) by \(L\) and \(\ell\); the explicit argument \(Y\) is retained whenever a formula defines a new named quantity as an expectation. The following single-phrase quantity appears throughout: \[\mu_j(t)\stackrel{\Delta} {=}\mathbb{E}\{[\ell(Y)]^j e^{-tL(Y)}\},~j=0,1,2,\dots,~t\ge0. \label{eq:muj}\tag{2}\] Note that \(\mu_0(t)=\mathbb{E}\{e^{-tL(Y)}\}\) is the MGF of \(-L(Y)\). We define the mean phrase length and mean codeword length by \[\label{eq:barLell} \bar{L}\stackrel{\Delta} {=}\mathbb{E}\{L(Y)\}=\sum_{y\in\mathcal{D}} Q(y)L(y), \qquad \bar{\ell}\stackrel{\Delta} {=}\mathbb{E}\{\ell(Y)\}=\sum_{y\in\mathcal{D}} Q(y)\ell(y).\tag{3}\] The asymptotic compression rate of the code is defined as \[\rho \stackrel{\Delta} {=}\frac{\bar\ell}{\bar L} = -\frac{\mu_1(0)}{\mu_0'(0)},\] where \(\mu_0'(\cdot)\) denotes the derivative of \(\mu_0(\cdot)\). For any two random variables \(U,V\) appearing below, we write \(\mathrm{Var}\{U\}\stackrel{\Delta} {=}\mathbb{E}\{U^2\}-(\mathbb{E}\{U\})^2\) and \(\mathrm{Cov}\{U,V\}\stackrel{\Delta} {=}\mathbb{E}\{UV\}-\mathbb{E}\{U\}\mathbb{E}\{V\}\) for their variance and covariance, respectively.

After encoding \(n\) phrases, the total code length is \(\Lambda_n \stackrel{\Delta} {=}\sum_{i=1}^n \ell(Y_i)\) (in bits) and the total number of source symbols consumed is \(\Sigma_n \stackrel{\Delta} {=}\sum_{i=1}^n L(Y_i)\). The realized compression ratio over \(n\) phrases is \[\label{eq:Rndef} R_n \stackrel{\Delta} {=}\frac{\Lambda_n}{\Sigma_n} = \frac{\sum_{i=1}^n \ell(Y_i)}{\sum_{i=1}^n L(Y_i)}~~\frac{bits}{symbol}.\tag{4}\] By the strong law of large numbers, \(\Lambda_n/n\to\bar\ell\) and \(\Sigma_n/n\to\bar L\) almost surely (a.s.), and so, by the continuous mapping theorem, \(R_n\to\rho\) a.s.as \(n\to\infty\).

2.2 Structure and parsing↩︎

The dictionary \(\mathcal{D}\) of a V2V length code is represented by a full \(\alpha\)-ary rooted tree, i.e., every internal node has \(\alpha\) children, one per each possible source symbol; the \(M\) leaves correspond to the \(M\) phrases \(y\in\mathcal{D}\). The parsing rule is as follows: start at the root, follow the edge labeled by each successive source symbol until reaching a leaf. The leaf reached identifies the current phrase \(y\); the encoder emits the binary codeword assigned to that leaf and resets to the root for the next phrase.

Let \(J\) denote the number of internal nodes of the parsing tree, including the root. Unique parsability forces \(M=J(\alpha-1)+1\), so \[\label{eq:Jdef} J = \frac{M-1}{\alpha-1}.\tag{5}\] The phrase length satisfies \(L(y)\ge1\) for every \(y\in\mathcal{D}\), and the codeword length \(\ell(y)\) takes values in \(\{1,2,\dots,\ell_{\max}\}\) for some maximum codeword length \(\ell_{\max}\).

2.3 V2V as a finite-state encoder↩︎

A finite-state (FS) encoder over the source alphabet \(\mathcal{X}\) and output alphabet \(\mathcal{B}\) is specified by a finite state set \(\mathcal{Z}\) (of size \(|\mathcal{Z}|\)), a next-state function \(g:\mathcal{Z}\times\mathcal{X} \to\mathcal{Z}\), and an output function \(f:\mathcal{Z}\times\mathcal{X} \to\mathcal{B}^*\), where \(\mathcal{B}^*\) denotes a set of finite strings over \(\mathcal{B}\), possibly including the empty string \(\emptyset\) of length zero. For a string \(s\in\mathcal{B}^*\), we write \(\ell[s]\) for its length in bits, with the convention \(\ell[\emptyset]=0\); this is consistent with \(\ell(y)\) of Section 2 when \(s=c(y)\) is the codeword of leaf \(y\). When a source sequence \(x_1,x_2,\dots\) is fed into the encoder, the state evolves according to the recursion \(z_{i+1} = g(z_i,x_i)\), \(i=1,2,\dots\) (with \(z_1\) being a fixed initial state), and the encoder outputs the sequence of strings from \(\mathcal{B}\), \(f(z_1,x_1), f(z_2,x_2),\dots\)

The V2V length encoder described in the preceding subsection can be cast as an FS encoder with a state set \(\mathcal{Z}\) given by the set of \(J\) internal nodes of the parsing tree (thus \(|\mathcal{Z}|=J\)), source alphabet \(\mathcal{X}\) (of cardinality \(\alpha\)), and output alphabet \(\mathcal{B}=\{0,1\}\) (binary codewords). The encoder is in state \(z\in\mathcal{Z}\) when it has partially matched a phrase and is currently at internal node \(z\). For source symbol \(x\) processed while in state \(z\), the next-state and output functions are: \[\label{eq:nextstate} g(z,x) = \begin{cases} z' & \text{if the child of z along edge x is an internal node z',}\\ root & \text{if the child of z along edge x is a leaf,} \end{cases}\tag{6}\] \[\label{eq:output} f(z,x) = \begin{cases} \emptyset & \text{ if }g(z,x)\ne root,\\ c(y) & \text{if the child of z along x is leaf y.} \end{cases}\tag{7}\] The encoder emits output only when a phrase is completed (i.e., when the child is a leaf), at which point it resets to the root.

The IL property holds for uniquely parsable dictionaries, since each codeword maps to a unique leaf, which together with the initial parsing state determines the phrase consumed. For plurally parsable dictionaries [8] – where a source string may have more than one valid parse – the IL property may fail, and the framework below requires modification.

For \(m\ge1\), \(g(z,x^m)\) will denote the final state of the encoder when the initial state is \(z\) and it processes the \(m\) successive inputs \(x^m=(x_1,\dots,x_m)\in\mathcal{X}^m\); \(f(z,x^m)\) denotes the corresponding output string emitted in response to \(x^m\).

2.4 The generalized Kraft inequality and a lower bound on the compression ratio↩︎

The classical Kraft–McMillan inequality, \(\sum_{y} 2^{-\ell(y)}\le1\), characterizes a limitation on lossless codes over a fixed alphabet but does not directly apply to FS encoders. For the IL FS encoder above, the appropriate generalization uses the following matrix.

Let \(\mathrm{spr}(\mathbf{K})\) denote the spectral radius of \(\mathbf{K}\). The generalized Kraft inequality reads:

Note that the right-hand side is independent of \(m\). This is the key improvement over the earlier generalized Kraft inequality of Ziv and Lempel [15], whose analogous bound grows linearly in \(m\); this linear growth prevents one from extracting any useful rate lower bound from the Ziv–Lempel result.

Substituting \(J=(M-1)/(\alpha-1)\) into Theorem 2 and taking the supremum over \(m\ge1\) gives the following lower bound on the compression ratio of any V2V length code, valid for any source (not necessarily memoryless); this is eq. (34) of [2], whose proof combines the per-entry bound of Theorem 2 with the standard Kraft-sum-with-slack redundancy bound and is not reproduced here:

The right-hand side of ?? cannot be smaller than the entropy rate \(H_\infty\stackrel{\Delta} {=}\lim_{m\to\infty}H(X_m\mid X^{m-1})\) (a supremum dominates the limit), and decreases in \(M\). For a DMS, \(H(X_m\mid X^{m-1})=H(X)\), so the supremum is taken over \(H(X)-C(M,\alpha,\ell_{\max})/m\), which yields \(H(X)\). This is a substantially more direct route to the converse than the classical technique of concatenating many phrases and invoking a law-of-large-numbers argument.

2.5 Design↩︎

Unlike F2V length coding (where Huffman’s algorithm gives a provably optimal greedy construction) and V2F length coding (where Tunstall’s algorithm does the same for memoryless sources), no analogous optimal joint design algorithm is known for V2V length coding, where both the parsing tree and the codeword lengths are simultaneously free. The standard practice is a two-stage heuristic: build a Tunstall-optimal V2F tree, then apply Huffman coding to the leaf probabilities induced by that tree. This heuristic is not known to be jointly optimal and in general it is not [16]. The minimum achievable redundancy for V2V length codes of a given size \(M\) is an open problem. One known negative result: for a binary memoryless source with \(0<P(1)<1/2\), no V2V code achieves exactly zero redundancy [3].

The best known achievability result is due to Khodak [3], [16]: for any memoryless source there exists a V2V code whose average redundancy decays as \(O(\bar L^{-5/3})\), where \(\bar L\) is the average phrase length. This strictly improves on the \(O(1/\bar L)\) redundancy of the Tunstall–Huffman heuristic, achieved by using a parsing tree that deliberately maintains non-uniform leaf probabilities so that variable codeword lengths can contribute meaningfully. An explicit construction achieving this bound is given in [16].

2.6 Notation summary↩︎

The paper accumulates a fair amount of notation as it goes; the following table collects the symbols used across more than one section, for reference while reading the more technical parts (Sections 3 and 5 especially). Purely local symbols, introduced and used within a single proof, are omitted.

3 Moments of the compression ratio for memoryless sources↩︎

This section develops the main technical machinery of this paper in two stages. In Sections 3.1–3.2, an exact formula for every integer moment \(\mathbb{E}\{R_n^k\}\) is obtained. First, the case \(k=1\) is worked out in full, and then it is generalized for an arbitrary positive integer \(k\). Second, from these exact formulas: a refined Edgeworth approximation to the CDF of \(R_n\) (Section 3.4) that improves on the classical CLT by using the skewness the third moment provides; closed-form \(O(1/n)\) asymptotics for the bias and variance via Laplace’s method (Section 3.5); and a large-deviations analysis of \(R_n\)’s tails. A numerical validation against Monte Carlo simulation (Section 3.3) checks the exact formulas along the way. In this section the phrase pairs \((L(Y_i),\ell(Y_i))_{i\ge1}\) are i.i.d.with the same distribution as \((L(Y),\ell(Y))\) for a generic phrase \(Y\), as is appropriate for a DMS.

3.1 The mean compression ratio↩︎

We begin with the first moment – the expected compression ratio \(\mathbb{E}\{R_n\}\) – as the quantity of primary practical interest and the one that motivates the general approach.

3.2 Extension to general moments↩︎

The proof of Theorem 3 used two ingredients: the Laplace transform representation of \(1/s\), and independence across phrase pairs. For general \(k\ge1\), the same two ingredients apply, but expanding \(\Lambda_n^k\) now produces cross-terms between different phrases, and tracing of these requires some combinatorial bookkeeping. That bookkeeping is organized by set partitions of \(\{1,\dots,k\}\), defined precisely in the proof below, with a worked example for \(k=2\) and \(k=3\) included along the way.

For \(k=2\) and \(k=3\), the integrals are explicitly: \[\label{eq:secondmoment} \mathbb{E}\{R_n^2\} = \int_0^\infty t\bigl(n\mu_2(t)[\mu_0(t)]^{n-1}+n(n-1)[\mu_1(t)]^2[\mu_0(t)]^{n-2}\bigr)\mathrm{d}t,\tag{17}\] \[\begin{align} \label{eq:thirdmoment} \mathbb{E}\{R_n^3\} = \frac{1}{2}\int_0^\infty t^2\bigl(&n\mu_3(t)[\mu_0(t)]^{n-1} +3n(n-1)\mu_2(t)\mu_1(t)[\mu_0(t)]^{n-2}\\ &+n(n-1)(n-2)[\mu_1(t)]^3[\mu_0(t)]^{n-3}\bigr)\mathrm{d}t. \end{align}\tag{18}\] From these three moments one obtains the mean, variance, and skewness of \(R_n\) via \(\mathrm{Var}\{R_n\}=\mathbb{E}\{R_n^2\}-(\mathbb{E}\{R_n\})^2\) and \(\gamma_1=(\mathbb{E}\{R_n^3\}-3\mathbb{E}\{R_n\}\mathbb{E}\{R_n^2\}+2(\mathbb{E}\{R_n\})^3)/(\mathrm{Var}\{R_n\})^{3/2}\).

3.3 Validation↩︎

We now validate ?? on a simple V2V length code: a binary memoryless source with \(P(0)=1-P(1)=p=0.8\), parsed by the Tunstall tree with dictionary \(\{00,01,1\}\), and coded with the Huffman assignment \((\ell(00),\ell(01),\ell(1))=(1,2,2)\). The same source, tree, and codeword assignment are used again for the bias-decomposition example in Section 4. This is a complete prefix code: \(2^{-1}+2^{-2}+2^{-2}=1\), so Kraft’s inequality holds with equality, and every codeword length is a positive integer. The phrase probabilities are \(Q(00)=p^2=0.64\), \(Q(01)=p(1-p)=0.16\), \(Q(1)=1-p=0.2\), giving \(\bar L=1.8\), \(\bar\ell=1.36\), and \(\rho=\bar\ell/\bar L=0.7556\).

For this model, \(\mu_j(t)=\mathbb{E}\{[\ell(Y)]^je^{-tL(Y)}\}\) is the explicit three-term sum \[\mu_j(t) = 0.64\cdot1^j e^{-2t} + 0.16\cdot2^j e^{-2t} + 0.2\cdot2^j e^{-t},\] so, e.g., \(\mu_0(t)=0.8e^{-2t}+0.2e^{-t}\) and \(\mu_1(t)=0.96e^{-2t}+0.4e^{-t}\). The three integrals ?? , 17 , 18 are evaluated by standard numerical quadrature (Gaussian quadrature after the substitution \(t=u/n\) to handle the concentration near \(t=0\) for larger \(n\)).

At \(n=50\) phrases, the exact formulas give: \[\label{eq:exact50} \mathbb{E}\{R_{50}\}=0.7571,\quad\mathrm{Var}\{R_{50}\}=0.003230,\quad \gamma_1=0.2878.\tag{19}\] For validation, we performed a Monte Carlo simulation of \(1{,}000{,}000\) independent realizations of \(50\) phrase pairs \((L(Y_i),\ell(Y_i))\), drawn according to the three phrase probabilities above, computing the realized ratio \(R_{50}=\Lambda_{50}/\Sigma_{50}\) for each. The empirical estimates are: \[\label{eq:mc50} \widehat{\mathbb{E}\{R_{50}\}}=0.7571,\quad \widehat{\mathrm{Var}\{R_{50}\}}=0.003226,\quad \widehat{\gamma_1}=0.2875.\tag{20}\] Agreement is to three or four significant figures throughout – the skewness \(\gamma_1\) in particular is the first quantity that 18 provides beyond what a first-order approximation would give – and the exact formulas require no simulation effort at all.

3.4 The Edgeworth approximation↩︎

The three exact moment formulas ?? –18 can be used to construct a sharper approximation to the CDF of \(R_n\) than the ordinary CLT (Gaussian) approximation. By the bivariate CLT, the pair \((\Lambda_n-n\bar\ell,\Sigma_n-n\bar L)/\sqrt{n}\) converges in distribution to a bivariate normal as \(n\to\infty\). By the delta method [1], any function that is continuously differentiable at the limiting mean again yields a normal limit, with asymptotic variance determined by the gradient of the function and the full limiting covariance matrix. Applied to the map \((\lambda,m)\mapsto\lambda/m\), which is continuously differentiable at \((\bar\ell,\bar L)\) since \(\bar L>0\), this implies that \(Z_n\stackrel{\Delta} {=}(R_n-\mathbb{E}\{R_n\})/\sqrt{\mathrm{Var}\{R_n\}}\) converges in distribution to a standard normal \(\mathcal{N}(0,1)\). The CLT approximation to the CDF \(F(x)\stackrel{\Delta} {=}\Pr\{R_n\le x\}\) is therefore \(\Phi_{\rm nor}(z)\), where \(z=(x-\mathbb{E}\{R_n\})/\sqrt{\mathrm{Var}\{R_n\}}\) and \(\Phi_{\rm nor}\) is the standard normal CDF. But this approximation ignores the skewness of the distribution, which is \(O(1/\sqrt{n})\) and non-negligible at moderate \(n\).

The one-term Edgeworth expansion corrects for the skewness. It approximates \(F\) by \[F_{\tiny Edgeworth}(x)\stackrel{\Delta} {=}\Phi_{\rm nor}(z)-\varphi(z)\,\frac{\gamma_1}{6}(z^2-1), \label{eq:edgeworth}\tag{21}\] where \(z=(x-\mathbb{E}\{R_n\})/\sqrt{\mathrm{Var}\{R_n\}}\), \(\varphi=\Phi'_{\rm nor}\) is the standard normal density, and \(\gamma_1\) is the skewness of \(R_n\). The approximation 21 is a standard result in the theory of Edgeworth expansions for sums of i.i.d.random variables [18]; its validity for the ratio \(R_n=\Lambda_n/\Sigma_n\) follows from the delta method applied to the bivariate CLT for \((\Lambda_n,\Sigma_n)\), under standard moment conditions on the phrase pair \((L(Y),\ell(Y))\). The key point is that all three parameters entering 21 – \(\mathbb{E}\{R_n\}\), \(\mathrm{Var}\{R_n\}\), and \(\gamma_1\) – are available from ?? –18 for every finite \(n\).

Continuing the same numerical example as in Subsection 3.3, Table 1 shows the absolute approximation error \(|F(x)-F_{\tiny Edgeworth}(x)|\) for \(n=50\), at several standardized values \(z\), comparing the CLT approximation against 21 with the exact \(\gamma_1=0.2878\):

The Edgeworth correction reduces the approximation error at every tabulated point, by a factor ranging from about \(3\) to nearly \(200\) depending on \(z\); averaged over the range shown, the mean absolute error drops by a factor of about \(3.4\) and the maximum error by a factor of about \(2.7\). This is a more modest improvement than a smooth, continuously-supported distribution would show (compare Remark 1 below), since \(L(Y)\) and \(\ell(Y)\) each take only two values here, but it is a genuine improvement for an actual code.

Figure 1 shows this comparison as a continuous function of \(z\) rather than at the five tabulated points, against a \(20{,}000{,}000\)-trial Monte Carlo baseline. The CLT error traces out a broad envelope peaking near \(z=0\), while the Edgeworth error stays consistently lower across the entire range shown. Both curves show some oscillation rather than a perfectly smooth profile; this is a genuine finite-alphabet effect discussed in Remark 1 below.

3.5 Asymptotic Approximation via the Laplace method of integration↩︎

For large \(n\), the integrands in ?? are sharply concentrated near \(t=0\) and can be evaluated asymptotically by the Laplace method of integration. The change of integration variabe \(t=u/n\) transforms the integrals into a form where the concentration is explicit and a systematic expansion in \(1/n\) can be carried out. There are two versions of Laplace’s method for an integral \(\int_a^b g(t)e^{-nf(t)}\mathrm{d}t\), depending on where \(f\) attains its minimum over the domain of integration. If the minimum occurs at an interior point \(t_0\in(a,b)\) with \(f'(t_0)=0\), the local behavior of \(f\) near \(t_0\) is quadratic, and so, \(e^{-nf(t)}\) is locally approximated by a Gaussian, \(e^{-nf(t_0)}\cdot\exp\left\{-\frac{nf''(t_0)}{2}(t-t_0)^2\right\}\), giving the familiar \(\sqrt{\frac{2\pi}{nf''(t_0)}}\) prefactor. If instead the minimum occurs at a boundary point of the domain (\(a\) or \(b\)) with \(f'(t_0)\ne0\), the local behavior of \(f\) is linear rather than quadratic, and \(e^{-nf(t)}\) is locally approximated at the vicinity of \(t_0\) by a plain exponential, \(e^{-nf(t_0)}e^{-nf'(t_0)(t-t_0)}\), rather than a Gaussian; its moments against a power series in \((t-t_0)\) are then elementary Gamma-function integrals rather than Gaussian moments (see, e.g., [19] or [20]). This second, boundary case is the one relevant here: as shown below, \(f(t)\stackrel{\Delta} {=}-\ln\mu_0(t)\) attains its minimum over \(t\in[0,\infty)\) at the boundary point \(t_0=0\) with \(f'(0)=\bar L\ne0\), so \([\mu_0(t)]^{n}=e^{-nf(t)}\) is approximated near \(t=0\) by the exponential \(e^{-n\bar Lt}\). The derivation below carries this out to one further order in \(1/n\) than the leading term alone provides, since the bias coefficient \(C\) requires the \(O(1/n)\) correction.

Let \(f(t)=-\ln\mu_0(t)\) denote the negative cumulant generating function (CGF) of \(-L(Y)\). Since \(L(Y)\ge1\) a.s., \(f(0)=0\) and \(f'(0)=\mathbb{E}\{L(Y)\}=\bar L>0\). Furthermore, \(f\) is strictly concave as \(f''(t)<0\) for all \(t\ge0\). In particular, \(f(t)>0\) for all \(t>0\), so \([\mu_0(t)]^{n-1}=e^{-(n-1)f(t)}\to0\) exponentially fast in \(n\) for every fixed \(t>0\). The integrand of ?? , which is proportional to \(\mu_1(t)[\mu_0(t)]^{n-1}\), therefore concentrates near \(t_0=0\) as \(n\to\infty\). Substituting \(t=u/n\) gives \([\mu_0(u/n)]^{n-1}=e^{-(n-1)f(u/n)}\approx e^{-\bar L u}\) (to leading order for large \(n\)), and after the substitution the integral becomes \(\int_0^\infty\mu_1(u/n)e^{-(n-1)f(u/n)}\mathrm{d}u\), which is \(O(1)\).

3.5.0.1 The bias term.

Write \(\bar L=\mathbb{E}\{L(Y)\}\), \(\kappa_2=\mathrm{Var}\{L(Y)\}\), \(\bar\ell=\mathbb{E}\{\ell(Y)\}\), \(c_{\ell L}=\mathbb{E}\{\ell(Y)L(Y)\}\). The \(O(1/n)\) expansion of \(\mathbb{E}\{R_n\}\) follows from a general fact about this boundary case of the Laplace method, stated here and proved in Appendix A (see also [19] and [20] for the general theory).

The case \(k=m=1\), \(h=g\) reduces to \[n\cdot\int_0^\infty g(t)e^{-(n-1)f(t)}\mathrm{d}t = \frac{g_0}{a}+\frac{a^2g_0+ag_1+bg_0}{na^3}+O\left(\frac{1}{n^{2}}\right),\] the form used just below.

Applying Lemma 1 with \(f(t)=-\ln\mu_0(t)\) and \(g=\mu_1\): from the previous paragraph, \(a=\bar L\) and \(b=\kappa_2\); and since \(\mu_1(0)=\mathbb{E}\{\ell(Y)\}=\bar\ell\) and \[\mu_1'(t)=\frac{\mathrm{d}}{\mathrm{d}t}\mathbb{E}\{\ell(Y)e^{-tL(Y)}\}=-\mathbb{E}\{L(Y)\ell(Y)e^{-tL(Y)}\},\] so \(\mu_1'(0)=-c_{\ell L}\), we have \(g_0=\bar\ell\) and \(g_1=-c_{\ell L}\). Substituting into ?? , \[\mathbb{E}\{R_n\} = n\cdot\int_0^\infty\mu_1(t)[\mu_0(t)]^{n-1}\mathrm{d}t = \frac{\bar\ell}{\bar L}+\frac{1}{n}\cdot\frac{\bar L^2\bar\ell-\bar Lc_{\ell L}+ \kappa_2\bar\ell}{\bar L^3}+O\left(\frac{1}{n^2}\right) = \rho+\frac{C}{n}+O\left(\frac{1}{n^2}\right)\] with \[C = \frac{\bar\ell(\bar L^2+\kappa_2)-c_{\ell L}\bar L}{\bar L^3}.\] We state this as Proposition 1 below.

A comment is in order concerning an alternative route for calculating the bias – the delta-method. Since \(\bar U_n:=\Sigma_n/n\) and \(\bar V_n:=\Lambda_n/n\) are exact sample means of i.i.d.data, \(\mathbb{E}\{\bar U_n\}=\bar L\) and \(\mathbb{E}\{\bar V_n\}=\bar\ell\) exactly, for every \(n\). Writing \(g(u,v):=v/u\) and Taylor-expanding \(R_n=g(\bar U_n,\bar V_n)\) to second order around \((\bar L,\bar\ell)\), the first-derivative terms vanish upon taking expectations, since the sample means are exactly unbiased – so the entire bias comes from the second derivatives: \[C = \frac{1}{2}\Bigl(g_{uu}\mathrm{Var}\{L\}+2g_{uv}\mathrm{Cov}\{L,\ell\}\Bigr) = \frac{\rho\,\mathrm{Var}\{L\}-\mathrm{Cov}\{L,\ell\}}{\bar L^2},\] using \(g_{uu}=2\rho/\bar L^2\), \(g_{uv}=-1/\bar L^2\), \(g_{vv}=0\) at \((\bar L,\bar\ell)\) – algebraically identical to ?? , with \(\mathrm{Var}\{L\}=\kappa_2\) and \(\mathrm{Cov}\{L,\ell\}=c_{\ell L}-\bar L\bar\ell\).

This is a useful independent cross-check, but not a substitute for the derivation above. The delta method, by construction, gives only the leading \(O(1/n)\) correction: it starts from an asymptotic expansion of \(R_n\) itself and stops at second order once that correction is in hand, since the first-derivative terms vanish identically and nothing forces the expansion any further. The Laplace-method route above instead starts from the exact formula ?? , valid at every finite \(n\), and reaches the bias by expanding that formula asymptotically – so the same machinery, carried one order further, would give the \(O(1/n^2)\) term too, and (via Theorem 4 and Lemma 1 applied repeatedly, as just below) gives every higher moment – variance, skewness, and beyond – from a single combinatorial formula, rather than requiring a fresh, increasingly delicate multivariate Taylor expansion for each one in turn. It also extends uniformly to the Markov case of Section 5: there, the delta method’s natural generalization requires tracking how a phrase’s own fluctuation correlates with the state it leaves the chain in – a genuine complication with no analogue here – whereas an eigenvalue-perturbation argument handles this automatically, by perturbing the joint spectral object directly rather than decomposing the bias into pieces by hand.

3.5.0.2 The variance term.

Lemma 1, applied twice more, yields the asymptotic variance directly. Write \(\mathbb{E}\{R_n^2\}=I_1+I_2\) where \[\label{eq:I1I2} I_1=\int_0^\infty tn\mu_2(t)[\mu_0(t)]^{n-1}\mathrm{d}t,\quad I_2=\int_0^\infty tn(n-1)[\mu_1(t)]^2[\mu_0(t)]^{n-2}\mathrm{d}t,\tag{22}\] each matching the Lemma’s left-hand side with \(k=2\) (since the extra factor is \(t=t^{k-1}\)). For \(I_1\), \(m=1\) and \(h=\mu_2\), so \(h_0=\mu_2(0)=s_{\ell2}\) where \(s_{\ell2}:=\mathbb{E}\{[\ell(Y)]^2\}\); since \(I_1\) itself turns out to contribute only at order \(1/n\) to \(\mathbb{E}\{R_n^2\}\), only the Lemma’s leading term is needed: \[I_1 = \frac{s_{\ell2}}{n\bar L^2}+O\left(\frac{1}{n^2}\right).\] For \(I_2\), \(m=2\) and \(h=[\mu_1]^2\), so \(h_0=[\mu_1(0)]^2=\bar\ell^2\) and, by the product rule, \(h_1=2\mu_1(0)\mu_1'(0)=-2\bar\ell\,c_{\ell L}\); since \(I_2\) contributes at leading order \(O(1)\), both terms of the Lemma are needed: \[I_2 = \frac{\bar\ell^2}{\bar L^2} +\frac{1}{n}\cdot\frac{\bar\ell\bigl(3\bar L^2\bar\ell-4\bar L\,c_{\ell L}+3\kappa_2\bar\ell\bigr)}{\bar L^4} +O\left(\frac{1}{n^2}\right).\]

On the validation example of Section 3.3, the analytic formulas of Propositions 1 and 2 evaluate to a bias coefficient of \(0.076818\) and an asymptotic scaled variance of \(0.159000\). The exact formula ?? evaluated at large \(n\) gives \(n(\mathbb{E}\{R_n\}-\rho)\to0.076818\) and \(n\mathrm{Var}\{R_n\}\to0.159000\), matching to six significant figures and confirming both propositions numerically.

3.6 Large deviations of the compression ratio↩︎

The Edgeworth expansion of Section 3.4 characterizes the behavior of \(R_n\) in the \(O(1/\sqrt{n})\) fluctuation region around \(\rho\). For deviations of fixed size \(\Delta>0\) (independent of \(n\)), the probability \(\Pr\{R_n > \rho+\Delta\}\) decays exponentially in \(n\), and its exact exponential rate follows directly from Cramér’s theorem.

The key observation is that the event \(\{R_n > \rho+\Delta\}\) is equivalent to a standard large-deviations event for a sum of i.i.d. random variables. Since \[\label{eq:ld95equiv} R_n > \rho+\Delta \;\iff\; \frac{\Lambda_n}{\Sigma_n} > \rho+\Delta \;\iff\; \sum_{i=1}^n \bigl[\ell(Y_i) - (\rho+\Delta)L(Y_i)\bigr] > 0,\tag{23}\] the event is determined by whether the partial sum of the i.i.d.random variables \(Z_i^{(\Delta)} := \ell(Y_i) - (\rho+\Delta)L(Y_i)\) exceeds zero. Since \(\mathbb{E}\{Z_i^{(\Delta)}\} = \mathbb{E}\{\ell(Y)\} - (\rho+\Delta)\mathbb{E}\{L(Y)\} = -\Delta\mathbb{E}\{L(Y)\} < 0\) for \(\Delta>0\), this is a large-deviations event with the sum crossing zero against its drift. An identical reduction handles the lower tail: \(\{R_n < \rho-\Delta\} \iff \sum_i [\ell(Y_i)-(\rho-\Delta)L(Y_i)] < 0\), with \(\mathbb{E}\{\ell(Y)-(\rho-\Delta)L(Y)\} = \Delta\mathbb{E}\{L(Y)\} > 0\).

By Cramér’s theorem, for every \(\Delta>0\) (all logarithms in this subsection are natural logarithms): \[\begin{align} \frac{1}{n}\log\Pr\{R_n > \rho+\Delta\} &\;\to\; -I_+(\Delta), \tag{24}\\ \frac{1}{n}\log\Pr\{R_n < \rho-\Delta\} &\;\to\; -I_-(\Delta), \tag{25} \end{align}\] where the rate functions are \[\label{eq:ld95rate95upper} I_+(\Delta) \;=\; \sup_{\theta > 0} \Bigl\{-\log\mathbb{E}\bigl\{e^{\theta[\ell-(\rho+\Delta)L]}\bigr\}\Bigr\},\tag{26}\] \[\label{eq:ld95rate95lower} I_-(\Delta) \;=\; \sup_{\theta < 0} \Bigl\{-\log\mathbb{E}\bigl\{e^{\theta[\ell-(\rho-\Delta)L]}\bigr\}\Bigr\}.\tag{27}\] For a real parameter \(\theta\) and constant \(c\), let \(P_\theta^{(c)}\) denote the exponentially tilted law of \((L,\ell)\) obtained by weighting each realization proportionally to \(e^{\theta(\ell-cL)}\), and write \(\mathbb{E}_\theta^{(c)}\{\cdot\}\) for the corresponding expectation; below, \(c\) is \(\rho+\Delta\) for the upper tail and \(\rho-\Delta\) for the lower tail, and we abbreviate \(P_\theta^{(c)}\) and \(\mathbb{E}_\theta^{(c)}\) by \(P_\theta\) and \(\mathbb{E}_\theta\) since \(c\) is clear from context. The supremum over \(\theta>0\) in \(I_+\) is unconstrained (the CGF is finite for all \(\theta>0\) provided \(\ell\) has all exponential moments, which holds for a finite alphabet); for a finite dictionary \(L\) is bounded, so the CGF of \(\ell-(\rho-\Delta)L\) is finite for all \(\theta\in\mathbb{R}\), and the supremum over \(\theta<0\) in \(I_-\) is unconstrained; for codes with unbounded phrase lengths, the supremum may be constrained to an interval \((\theta_{\min},0)\). The supremum in each case is achieved at a unique \(\theta^*\). For the upper tail, \(\theta^*>0\) is the unique positive root of \[\label{eq:ld95tilt95upper} \frac{\mathbb{E}\{[\ell-(\rho+\Delta)L]\,e^{\theta^*[\ell-(\rho+\Delta)L]}\}}{\mathbb{E}\{e^{\theta^*[\ell-(\rho+\Delta)L]}\}} = 0,\tag{28}\] and for the lower tail, \(\theta^*<0\) is the unique negative root of \[\label{eq:ld95tilt95lower} \frac{\mathbb{E}\{[\ell-(\rho-\Delta)L]\,e^{\theta^*[\ell-(\rho-\Delta)L]}\}}{\mathbb{E}\{e^{\theta^*[\ell-(\rho-\Delta)L]}\}} = 0.\tag{29}\] In both cases the condition expresses that the compression ratio under the tilted distribution \(P_{\theta^*}\) equals the target level: \(\mathbb{E}_{\theta^*}\{\ell\}/\mathbb{E}_{\theta^*}\{L\}=\rho+\Delta\) (upper tail) or \(\rho-\Delta\) (lower tail). Thus \(P_{\theta^*}\) is the unique exponential tilt of the original phrase-pair law under which the large-deviations event is typical.

The rate functions \(I_+,I_-\) are not built from a separate toolkit: \(\mathbb{E}\{e^{\theta[\ell-(\rho+\Delta)L]}\}=\mathbb{E}\{e^{\theta\ell-tL}\}\) along the ray \(t=\theta(\rho+\Delta)\) (and similarly for \(I_-\) along \(t=\theta(\rho-\Delta)\)), and this joint exponential moment is exactly the object that reduces to \(\mu_0(t)\) at \(\theta=0\) and to \(\mu_1(t)\) upon differentiating in \(\theta\) at \(\theta=0\) (Section 2). The exact moments of Sections 3–3.5 and the large-deviations rate functions here are two different slices of this same underlying two-parameter family, evaluated in different regimes: \(t\) alone for the moments, and along the rays above for the tails.

4 Comparison with V2F and F2V length codes↩︎

The three code families differ in which of the phrase length \(L\) and codeword length \(\ell\) they allow to vary: F2V fixes \(L\), V2F fixes \(\ell\), and V2V lets both vary. The fact that V2V can match or beat the other two on the asymptotic rate \(\rho\) is not surprising – it strictly contains them as special cases. The more informative question is what this extra freedom does to the finite-\(n\) behavior captured by \(C\), and what, if anything, it reveals about why some V2V constructions substantially outperform both alternatives while others do not.

4.0.0.1 Setup.

Fix a binary memoryless source with \(p=P(0)=0.8\) (\(H=0.722\) bits/symbol) and the Tunstall tree \(\{00,01,1\}\) (\(\bar L=1.8\), \(\mathrm{Var}\{L\}=0.16\)).

4.0.0.2 The structural decomposition.

The bias formula of Proposition 1 rewrites as \[\label{eq:bias95structure} C = \frac{\rho\,\mathrm{Var}\{L\} - \mathrm{Cov}\{L,\ell\}}{\bar L^2},\tag{30}\] which separates cleanly by code family:

• F2V: \(L\) is deterministic, so \(\mathrm{Var}\{L\}=\mathrm{Cov}\{L,\ell\}=0\) and \(C=0\) identically – not a design achievement, but a triviality of having no phrase-length randomness to create bias from. It buys nothing for \(\rho\).

• V2F: \(\ell\) is constant, so \(\mathrm{Cov}\{L,\ell\}=0\) always, giving \(C=\rho\mathrm{Var}\{L\}/\bar L^2>0\) with no freedom to reduce it: the fixed codeword length that limits \(\rho\) to \(O(1/\bar L)\) redundancy is the same constraint that locks in this bias.

• V2V: both vary, so \(\mathrm{Cov}\{L,\ell\}\) is a genuine design variable. Correlating \(L\) and \(\ell\) positively – longer phrases getting longer codewords – reduces \(C\) below what V2F could achieve with the same tree and the same \(\mathrm{Var}\{L\}\).

This freedom cuts both ways, though: the Huffman codeword assignment that minimizes \(\rho\) need not create positive covariance. For the tree above, Huffman assigns the shortest codeword to the most probable phrase (\(00\), \(P=0.64\)), which happens to be one of the longest phrases (\(L=2\)), giving \(\mathrm{Cov}\{L,\ell\}=-0.128<0\) and \(C_{\rm V2V}=0.077\) – larger than \(C_{\rm V2F}=0.055\) despite \(\rho_{\rm V2V}=0.756<\rho_{\rm V2F}=1.111\). The same tree admits a different codeword assignment (giving the shortest codeword to the shortest phrase instead) that achieves \(\mathrm{Cov}\{L,\ell\}=+0.160\) and \(C=0\) exactly, at the cost of a worse \(\rho=1\). V2F and F2V have no such choice to make; V2V’s freedom is precisely the ability to trade between these two objectives, in either direction.

4.0.0.3 Why this matters: the Khodak code.

The tension above raises the question of whether \(\rho\) and \(C\) can be improved together rather than traded off, and the Khodak code [3], [16] shows that they can. By the conservation of entropy [21], \(H(Y)=\bar L\,H\) for any parsing tree, where \(H(Y)\) is the phrase entropy; the Khodak construction assigns near-Shannon codewords, \(\ell(y)\approx-\log_2Q(y)\), to a tree deliberately built to preserve non-uniform leaf probabilities. By the asymptotic equipartition property, a typical phrase of length \(L(y)\) satisfies \(Q(y)\approx2^{-L(y)H}\), so \(\ell(y)\approx L(y)H\) holds for the typical phrases that carry essentially all the probability mass as \(L(y)\) grows – not for every individual leaf (a phrase consisting entirely of the single most probable symbol, for instance, gets a codeword far shorter than \(L(y)H\)), but for enough of the distribution to drive the averages below. This achieves redundancy \(r:=\rho-H=O(\bar L^{-5/3})\) – strictly better than the \(O(1/\bar L)\) available to V2F or to Tunstall–Huffman. The same typical-phrase approximation gives \(\mathrm{Cov}\{L,\ell\}\approx H\,\mathrm{Var}\{L\}\), so substituting into 30 , \[\label{eq:khodak95C} C \;\approx\; \frac{\rho\mathrm{Var}\{L\}-H\mathrm{Var}\{L\}}{\bar L^2} \;=\; \frac{(\rho-H)\mathrm{Var}\{L\}}{\bar L^2} \;=\; \frac{r\,\mathrm{Var}\{L\}}{\bar L^2} \;=\; O(r) \;=\; O(\bar L^{-5/3}).\tag{31}\] The bias coefficient shrinks at the same rate as the redundancy – not a second, independent achievement, but a direct consequence of the same design principle. Compare V2F: \(\ell\) cannot track \(L\) at all, so \(\mathrm{Cov}\{L,\ell\}=0\) is permanent regardless of how the tree is built, and neither the \(O(1/\bar L)\) floor on \(r\) nor the resulting \(C=\rho\mathrm{Var}\{L\}/\bar L^2\) can be improved by this mechanism.

For a binary Bernoulli\((2/3)\) source, the explicit Bugeaud–Drmota–Szpankowski construction [16] (convergent denominator \(q=5\)) gives \(\bar L=116.4\), \(\rho=0.9211\) against \(H=0.9183\) (\(r=0.0028\)), and \(\mathrm{Var}\{L\}=4824\); 31 predicts \(C\approx0.00097\), close to the exact value \(C=0.000962\) from Proposition 1 (\(\mathrm{Cov}\{L,\ell\}=4430\) against the predicted \(H\mathrm{Var}\{L\}=4430\)). Table [tab:khodak] confirms the resulting \(O(1/n)\) convergence numerically, using the exact moment formula ?? at every \(n\):

The approximation is accurate to five decimal places by \(n=50\), well before the asymptotic regime is actually reached.

5 Extension to Markov sources↩︎

This section repeats the memoryless program of Section 3 with the i.i.d.assumption dropped: a boundary state is identified that renders successive phrases Markov rather than independent (§5.1); the scalar quantities \(\mu_j(t)\) become matrices indexed by that state (§5.2); the mean formula of Theorem 3 becomes a matrix product (§5.4, validated against direct simulation); and the Laplace-method bias analysis of Section 3.5 becomes a matrix-eigenvalue perturbation, with the correction term now characterized by a Poisson equation rather than a plain derivative (§5.5, with a pointer to the underlying argument in Appendix B. The memoryless case reappears throughout as an exact special case, not a separate limit.

We now extend the source model to the Markov case. Specifically, in this section, \(X_1,X_2,\dots\) is assumed an irreducible, time-homogeneous, first-order Markov chain on the alphabet \(\mathcal{X}\) of cardinality \(\alpha\), with transition probabilities \(\Pr\{X_{k+1}=x'\mid X_k=x\}\), and initial state \(X_0\). The parsing tree, dictionary, and codeword assignment are exactly as before.

5.1 Source model: the boundary state \(S_i\)↩︎

Let \(\Sigma_i = L(Y_1)+\cdots+L(Y_i)\) denote the total number of source symbols consumed through the \(i\)-th phrase (with \(\Sigma_0\stackrel{\Delta} {=}0\), consistent with the \(\Sigma_n\) of Section 2), so phrase \(Y_i\) consists of the symbols \(X_{\Sigma_{i-1}+1},\dots,X_{\Sigma_i}\). We define the state of the source at the \(i\)-th phrase boundary as the last symbol consumed before that boundary, that is, \[\label{eq:state95def} S_i\stackrel{\Delta} {=}X_{\Sigma_i}, \qquad i=0,1,2,\dots\tag{32}\] and so \(S_0=X_0\). Thus the state set is \(\mathcal{X}\) itself, of size \(\alpha\); \(S_{i-1}\) is the symbol in force when phrase \(Y_i\) begins, and \(S_i\) is the symbol reached when phrase \(Y_i\) ends and the parser resets to the root of the parsing tree.

The initial state \(S_0\) is taken to have the stationary distribution \(\pi\) of the phrase-boundary chain \(\{S_i\}_{i\ge0}\) just defined (shown to be a genuine Markov chain in Lemma 2 below) – a distribution generally different from the ordinary stationary distribution of \(\{X_k\}_{k\ge0}\) itself, since phrase boundaries sample states at variable, state-dependent intervals rather than at every symbol (Section 5.4 gives a numerical instance of this gap).

Since phrase \(Y_i\) is parsed by running the parsing tree against the symbols \(X_{\Sigma_{i-1}+1},X_{\Sigma_{i-1}+2},\dots\) until a leaf is reached, the triple \((L(Y_i),\ell(Y_i),S_i)\) is a measurable function of \(S_{i-1}=X_{\Sigma_{i-1}}\) together with the (as yet unconsumed) continuation of the chain from time \(\Sigma_{i-1}\) onward. This lets the Markov property of \(\{X_k\}_{k\ge0}\) pass through the parsing recursion to the phrase level:

This is what makes \(\{S_i\}_{i\ge0}\) – not \(\{X_k\}_{k\ge0}\) itself – the Markov chain that matters for the moment analysis: the matrix quantities below are indexed by \(\mathcal{X}\) and evolve one step per phrase rather than per symbol. The construction extends verbatim to a \(k\)-th order Markov chain or a hidden finite-state source, taking \(S_i\) to be the last \(k\) symbols or the hidden state; we do not pursue this here.

5.2 Matrix-valued moment generating functions↩︎

For states \(s,s'\in\mathcal{X}\), define the matrix-valued moment generating function \[[\boldsymbol{\mu}_j(t)]_{ss'} := \mathbb{E}\{[\ell(Y_i)]^je^{-tL(Y_i)}\mathbf{1}[S_i=s']\mid S_{i-1}=s\}, \qquad j=0,1,2,\dots,~~t\ge 0, \label{eq:muj95matrix95def}\tag{33}\] for any phrase index \(i\ge1\) (by Lemma 2, this conditional law does not depend on \(i\)). These are \(\alpha\times\alpha\) nonnegative matrices parameterized by \(t\): \(\boldsymbol{\mu}_j(t)\) is the matrix analogue of the scalar quantity \(\mu_j(t)\) of Section 2, and the case \(j=0\) corresponds to the state transition matrix at phrase boundaries, \([\boldsymbol{\mu}_0(t)]_{ss'} = \mathbb{E}\{e^{-tL(Y_i)}\mathbf{1}[S_i=s']\mid S_{i-1}=s\}\). At \(t=0\), \([\boldsymbol{\mu}_0(0)]_{ss'}=\Pr\{S_i=s'\mid S_{i-1}=s\}\), so \(\boldsymbol{\mu}_0(0)\) is row-stochastic.

We assume throughout that \(\boldsymbol{\mu}_0(0)\) – the phrase-boundary chain’s own transition matrix, as distinct from the transition matrix of \(\{X_k\}_{k\ge0}\) itself – is irreducible and aperiodic (equivalently, primitive); this is a separate condition from the irreducibility of \(\{X_k\}_{k\ge0}\) assumed in Section 5 (a tree can route every path ending in a given state through a first symbol unreachable in one step from another state, so the two irreducibilities do not simply hand each other over), and it holds for every example in this paper. Aperiodicity is needed, not just irreducibility: an irreducible but periodic chain can have several eigenvalues tied for maximum modulus (e.g.the period-\(2\) chain \(\left(\begin{smallmatrix}0&1\\1&0\end{smallmatrix}\right)\) has eigenvalues \(1\) and \(-1\), both of modulus \(1\)), which would break the spectral-gap argument used in Section 5.5 and Appendix B to isolate the dominant eigenvalue’s contribution; primitivity is exactly what rules this out (by the Perron–Frobenius theorem for primitive matrices, the Perron eigenvalue is then strictly greater in modulus than every other eigenvalue).

A simple sufficient condition, easily checked without appeal to Perron–Frobenius theory directly: if \(\{X_k\}_{k\ge0}\) has a fully positive one-step transition matrix (i.e. \(\Pr\{X_{k+1}=x'\mid X_k=x\}>0\) for every \(x,x'\in\mathcal{X}\)), then \(\boldsymbol{\mu}_0(0)\) has strictly positive entries throughout, and is therefore automatically both irreducible and aperiodic. Indeed, full positivity means any specific finite symbol sequence has positive probability of occurring next, from any current state; since the parsing tree is finite, every leaf corresponds to some such sequence, so every leaf – and hence every ending state – is reachable with positive probability from every starting state in a single phrase. This condition is considerably stronger than needed (it fails, for instance, whenever some transition is structurally forbidden), but it covers most sources encountered in practice and requires no computation beyond inspecting the source’s own transition matrix.

Under this assumption, let \(\pi\) denote the unique stationary distribution of \(\boldsymbol{\mu}_0(0)\) – a row vector, consistent with its left-multiplying matrices throughout (as in \(\pi\boldsymbol{\mu}_0(0)\) just below) – satisfying \(\pi\boldsymbol{\mu}_0(0)=\pi\) and \(\sum_{s}\pi_s=1\). For a state-dependent single-phrase quantity \(G(Y_i)\) (such as the phrase length \(L(Y_i)\), the codeword length \(\ell(Y_i)\), or their product), we write \(\mathbb{E}_\pi\{G(Y_i)\} \stackrel{\Delta} {=}\sum_{s\in\mathcal{X}}\pi_s\mathbb{E}\{G(Y_i)\mid S_{i-1}=s\}\) for its expectation under the stationary regime; for \(G=L\), this plays the role of \(\bar L\) of Section 2 in the Markov case, and is the a.s.limit \(\Sigma_n/n\to\mathbb{E}_\pi\{L(Y_i)\}\) by the ergodic theorem for irreducible finite-state Markov chains.

5.3 The first moment formula for the Markov case↩︎

5.4 Worked example and validation↩︎

We use the binary Markov source of Savari and Gallager [6]: the state is the last bit emitted, and the self-transition probability (probability of emitting the same bit as the last one) is \(q\). This source has two states \(\{0,1\}\), with transition probabilities \(\Pr[S_i=s\mid S_{i-1}=s]=q\) and \(\Pr[S_i=1-s\mid S_{i-1}=s]=1-q\).

We use the parsing dictionary \(\{00,01,1\}\) (the same as in Section 4) and assign fixed-length codewords \(\ell\equiv2\) (a V2F code). The three possible phrases and their contributions to \(\boldsymbol{\mu}_0(t)\) are:

• Phrase \(1\) (one symbol equal to \(1\)): emitted from state \(0\) with probability \(1-q\) (cross-transition) and from state \(1\) with probability \(q\) (self-transition), driving the source to state \(1\), with \(L=1\).

• Phrase \(00\) (two \(0\)s): reached via symbol \(0\) then another \(0\); probability from state \(0\) is \(q\cdot q=q^2\) and from state \(1\) is \((1-q)\cdot q=q(1-q)\), driving the source to state \(0\), with \(L=2\).

• Phrase \(01\): from state \(0\) via \(0\) (prob.\(q\)) then \(1\) (prob.\(1-q\)), probability \(q(1-q)\); from state \(1\) via \(0\) (prob. \(1-q\)) then \(1\) (prob.\(1-q\)), probability \((1-q)^2\). Drives source to state \(1\), \(L=2\).

Collecting these contributions into the matrix \(\boldsymbol{\mu}_0(t)\) (rows indexed by starting state, columns by ending state): \[\label{eq:mu095matrix} \boldsymbol{\mu}_0(t) = \begin{pmatrix} q^2 e^{-2t} & (1-q)e^{-t}+q(1-q)e^{-2t}\\ q(1-q)e^{-2t} & qe^{-t}+(1-q)^2e^{-2t} \end{pmatrix}.\tag{38}\] Since \(\ell\equiv2\), \(\boldsymbol{\mu}_1(t)=2\boldsymbol{\mu}_0(t)\) and ?? simplifies to \(\mathbb{E}\{R_n\}=2n\int_0^\infty\pi\boldsymbol{\mu}_0(t)^n\mathbf{1}\,\mathrm{d}t\).

5.5 Asymptotic bias for Markov sources↩︎

The large-\(n\) asymptotic analysis of ?? proceeds as in Section 3.5: the substitution \(t=u/n\) stabilizes the numerical evaluation, and the resulting bias coefficient \(n(\mathbb{E}\{R_n\}-\rho)\) converges to a finite limit as \(n\to\infty\). This is governed by the dominant eigenvalue \(\Lambda(t)\) of \(\boldsymbol{\mu}_0(t)\) and the reason is that, for large \(n\), \([\boldsymbol{\mu}_0(t)]^n\) itself is governed by \([\Lambda(t)]^n\) (times a bounded projector term, standard for a matrix with a strictly dominant eigenvalue) – the matrix analogue of the scalar \([\mu_0(t)]^n\) of the memoryless case, which trivially equals itself raised to the \(n\)-th power. So extracting the \(O(1/n)\) term from ?? requires a Taylor series expansion of \(\Lambda(t)\) around \(t=0\) to the same order that Section 3.5 needed for the scalar quantity \(f(t)=-\ln\mu_0(t)\). For Example 1, the results are displayed in Table [tab:markov95bias95convergence].

A closed-form expression for the bias coefficient requires going one order further than the eigenvalue derivative \(\Lambda'(0)=-\mathbb{E}_\pi\{L\}\) already computed (Example 1) – exactly as the memoryless case of Section 3.5 needed not just \(f'(0)\) but also \(f''(0)\). For a matrix eigenvalue problem, unlike the scalar case, getting the second-order term \(\Lambda''(0)\) requires first finding the first-order correction to \(\Lambda(t)\)’s corresponding eigenvector – a standard fact of matrix perturbation theory (the same mechanism as second-order energy shifts needing first-order wavefunction corrections in perturbation theory more generally) – and this correction is what the Poisson equation below solves for.

Specifically, consider the expansion \(\boldsymbol{\mu}_0(t) = P + t\boldsymbol{\mu}_0'(0) + O(t^2)\) (with \(P\stackrel{\Delta} {=}\boldsymbol{\mu}_0(0)\)), \(\Lambda(t)\)’s corresponding right eigenvector as \(v(t) = \mathbf{1} + t\,\boldsymbol{e}+ O(t^2)\) (since \(P\mathbf{1}=\mathbf{1}\), this right eigenvector at \(t=0\) is \(\mathbf{1}\), and \(\boldsymbol{e}\) is its unknown first-order correction), and the eigenvalue itself as \(\Lambda(t) = 1 - \bar L t + O(t^2)\), where \(\bar L:=\mathbb{E}_\pi\{L\}\). Substituting into the eigenvalue equation \(\boldsymbol{\mu}_0(t)v(t)=\Lambda(t)v(t)\) and matching the coefficients of \(t\) on both sides gives \[\label{eq:order95t} (P-I)\boldsymbol{e}= -\bar L\mathbf{1} - \boldsymbol{\mu}_0'(0)\mathbf{1}.\tag{39}\] Recall from Example 1 that \([\boldsymbol{\mu}_0(t)\mathbf{1}]_s=\mathbb{E}\{e^{-tL(Y_i)}\mid S_{i-1}=s\}\), so \(\boldsymbol{\mu}_0'(0)\mathbf{1}=-g\) with \(g_s\stackrel{\Delta} {=}\mathbb{E}\{L(Y_i)\mid S_{i-1}=s\}\) the expected phrase length given starting state \(s\). Substituting into 39 , \[(P-I)\boldsymbol{e}= g-\bar L\mathbf{1}, \qquad\text{i.e.}\qquad (I-P)\boldsymbol{e}= \bar L\mathbf{1}-g.\] Since \((I-P)\mathbf{1}=0\), this equation only determines \(\boldsymbol{e}\) up to an additive multiple of \(\mathbf{1}\); writing \(w\stackrel{\Delta} {=}-\boldsymbol{e}\) and fixing this freedom by the normalization \(\pi w=0\) turns it into exactly the Poisson equation \[\label{eq:Poisson} (I-P)w = g - \mathbb{E}_\pi\{L\}\cdot\mathbf{1}, \qquad \pi w = 0,\tag{40}\] (this name and normalization are standard in Markov reward theory [22], where \((I-P)w=h\) with \(\pi h=0\) is the equation for the relative reward \(w\) associated with a per-state reward whose \(\pi\)-average has already been subtracted off). Here \(w\) – the relative-value vector – is precisely the relative-reward vector of Savari and Gallager [6], computed there for the reward “self-information of a phrase” under dictionary-size asymptotics; here the reward is “phrase length \(L\)” and the asymptotics are in phrase count.

This Poisson-equation correction is in fact the whole of what is needed: a second, completely analogous Poisson equation for the reward \(\ell\), combined with a joint eigenvalue perturbation in both the reward variable and \(t\), yields the bias coefficient \(C\) in closed form for a general Markov V2V code – not merely the V2F sub-case tabulated above (writing \(\Lambda_{\theta t}\) for the resulting mixed second derivative, and \(\Lambda''(0)\) for the second derivative of the already-familiar \(\Lambda(t)\) of Example 1):

This is an extended version of the paper, including the complete derivation of Proposition 3 in Appendix B below, in place of the proof sketch given in the version submitted for publication.

Figure 2 plots both closed forms ?? and ?? over the full range \(q\in(0,1)\), rather than at the single value \(q=0.99\) tabulated above. Both bias coefficients diverge as \(q\to1\) – a highly persistent source mixes slowly, and the Poisson-equation solutions \(w,w_\ell\) that drive \(\Lambda''(0)\) and \(\Lambda_{\theta t}\) grow correspondingly large – and, notably, the two curves cross at exactly \(q=1/3\) (as follows directly from equating ?? and ?? ): for weakly persistent sources the V2F code has the larger finite-\(n\) bias, while for strongly persistent sources (including the \(q=0.99\) case tabulated in both examples) the genuine V2V code’s bias is larger, mirroring the memoryless-case tension already noted in Section 4 between optimising a code for \(\rho\) and optimising it for \(C\).

6 Conclusion↩︎

The exact formula ?? gives, for any fixed V2V code applied to a DMS, exact formulas for all integer moments of the realized compression ratio \(R_n\) at every finite \(n\): mean, variance, and skewness are computable by one-dimensional numerical quadrature, from which an Edgeworth approximation to the CDF is obtained. The Laplace method applied to ?? recovers the classical ratio-estimator bias and variance asymptotics algebraically, by a different route than the delta method (Section 3.5), and provides a design guideline (maximize \(\mathrm{Cov}\{L,\ell\}\) for fastest convergence) backed by a precise, finite-\(n\) formula.

The extension ?? to Markov sources replaces scalar quantities by matrix-valued ones and is validated both against direct simulation and against the correct ergodic limit; the \(O(1/n)\) bias coefficient for this Markov case is likewise obtained in closed form (Proposition 3, Appendix B, via a joint eigenvalue perturbation that reduces exactly to Proposition 1 in the memoryless limit.

Independently of the moment analysis, the observation that a V2V code is an instance of a finite-state encoder lets us directly apply the generalized Kraft inequality of [2]: via Corollary 1, this gives an explicit, \(m\)-independent lower bound on the compression ratio in terms of the dictionary parameters \(M\), \(\alpha\), and \(\ell_{\max}\), with an \(O(1/m)\) correction term that improves on the Ziv–Lempel bound whose analogous constant grows linearly in \(m\). The structural analysis of Section 4 decomposes the bias coefficient \(C\) into a \(\mathrm{Var}\{L\}\) term and a \(\mathrm{Cov}\{L,\ell\}\) term, each of which vanishes identically for one of F2V and V2F; applied to the Khodak code, the same decomposition shows that its improved \(O(\bar L^{-5/3})\) redundancy and its correspondingly smaller bias coefficient are two faces of the same design principle rather than independent achievements.

Appendix A: Proof of the boundary Laplace lemma↩︎

This appendix proves Lemma 1, the boundary case of Laplace’s method used in Section 3.5, in its general form (arbitrary \(k,m\ge1\)).

Appendix B: Closed-form Markov bias coefficient↩︎

This appendix derives the closed-form expression for \(n(\mathbb{E}\{R_n\}-\rho)\) used in Section 5, for a general Markov V2V code whose phrase-boundary chain is irreducible and aperiodic (both \(L\) and \(\ell\) state-dependent random variables, not merely the V2F sub-case of Example 1). The argument rests on a single general fact about how the Perron eigenvalue of a matrix responds to two parameters at once (Lemma 3 below); once that lemma is established, the derivation is a short substitution, not a lengthy one, and nothing is omitted.

Setup↩︎

Define the joint matrix-valued moment generating function \[\label{eq:joint95transform} [\Psi(\theta,t)]_{ss'} := \mathbb{E}\{e^{\theta\ell(Y_i)-tL(Y_i)}\mathbf{1}[S_i=s']\mid S_{i-1}=s\}, \qquad s,s'\in\mathcal{X},\tag{41}\] so that \(\Psi(0,t)=\boldsymbol{\mu}_0(t)\) and \(\partial_\theta\Psi(\theta,t)|_{\theta=0}=\boldsymbol{\mu}_1(t)\). Let \(\Lambda(\theta,t)\) denote \(\Psi(\theta,t)\)’s dominant (Perron) eigenvalue near the origin, so \(\Lambda(0,t)=\Lambda(t)\) recovers the scalar eigenvalue of Section 5.5.

A general two-parameter perturbation lemma↩︎

The remaining derivation is an instance of a single, general fact about how the Perron eigenvalue of a matrix responds to two parameters simultaneously – stated and proved once here, in the abstract, rather than worked out from scratch in the specific notation of this problem.

6.0.0.1 Application.

Take \(A=\Psi\). Differentiating 41 gives \(A_t\mathbf{1}=-g\), \(A_\theta\mathbf{1}=g_\ell\) (where \(g_\ell(s):=\mathbb{E}\{\ell(Y_i)\mid S_{i-1}=s\}\)), \(A_{tt}=\boldsymbol{\mu}_0''(0)\), \(A_\theta=\boldsymbol{\mu}_1(0)\), \(A_t=\boldsymbol{\mu}_0'(0)\), and \(A_{\theta t}\mathbf{1}=-g_{L\ell}\) where \(g_{L\ell}(s):=\mathbb{E}\{L(Y_i)\ell(Y_i)\mid S_{i-1}=s\}\) (differentiating the exponent \(\theta\ell(Y_i)-tL(Y_i)\) once in each variable brings down a factor \(-L(Y_i)\ell(Y_i)\)). By ?? , \(\Lambda_t(0,0)=-\pi g=-\bar L\) and \(\Lambda_\theta(0,0)=\pi g_\ell=\bar\ell\), recovering the already-known values. The two Poisson equations ?? , for \(x=t\) and \(x=\theta\) respectively, are \[\label{eq:poisson95L} (I-P)w = g-\bar L\mathbf{1}, \qquad \pi w=0 \qquad(w:=-v_t),\tag{42}\] \[\label{eq:poisson95ell} (I-P)w_\ell = g_\ell-\bar\ell\,\mathbf{1}, \qquad \pi w_\ell=0 \qquad(w_\ell:=v_\theta),\tag{43}\] matching the Poisson equation of Section 5.5, with the sign flip for \(w\) tracing to \(A_t\mathbf{1}=-g\) carrying an extra minus sign that \(A_\theta\mathbf{1}=g_\ell\) does not. Substituting into ?? with \((x,y)=(t,t)\) and \((x,y)=(\theta,t)\): \[\label{eq:Lambda95pp95general} \Lambda''(0) = \pi\,\boldsymbol{\mu}_0''(0)\,\mathbf{1} - 2\,\pi\,\boldsymbol{\mu}_0'(0)\,w, \qquad \Lambda_{\theta t} = -\bar c - \pi\,\boldsymbol{\mu}_1(0)\,w + \pi\,\boldsymbol{\mu}_0'(0)\,w_\ell,\tag{44}\] where \(\bar c:=\mathbb{E}_\pi\{L\ell\}=\pi g_{L\ell}\) – exactly the formulas quoted in Proposition 3, obtained here by pure substitution into Lemma 3 rather than a fresh derivation. The resulting formula was additionally verified numerically to 10+ significant figures against direct high-precision computation of the exact formula ?? at large \(n\), on two different Markov V2V codes built on the source of Example 1 (one with \(\ell\) depending only on the destination state, one without that special structure), and collapses exactly to Proposition 1 in the memoryless limit.

References↩︎

---

1. For example, if \(k=3\) and the tuple \((i_1,i_2,i_3)=(5,7,5)\), slots \(a=1\) and \(b=3\) share the phrase index \(5\) while slot \(c=2\) has the different index \(7\), so the induced partition is \(\tau=\{\{1,3\},\{2\}\}\), with \(|\tau|=2\) subsets of sizes \(2\) and \(1\). The other tuples inducing this same \(\tau\) are exactly those of the form \((j,j',j)\) for any two distinct phrase indices \(j\ne j'\) in \(\{1,\dots,n\}\).↩︎