Single-letter and block distortion

Let $(\mathcal{X},\mathcal{A})$ and $(\widehat{\mathcal{X}},\widehat{\mathcal{A}})$ be measurable spaces, and let $d:\mathcal{X}\times \widehat{\mathcal{X}}\to [0,+\mathrm{\infty }]$ be a measurable single-letter distortion. For a positive integer $n$ and ordered blocks $x^n=(x_1,\dots ,x_n)\in {\mathcal{X}}^n$ and ${\widehat{x}}^n=({\widehat{x}}_1,\dots ,{\widehat{x}}_n)\in {\widehat{\mathcal{X}}}^n$, define the normalized additive block distortion by

$d_n(x^n,{\widehat{x}}^n):=\frac{1}{n}{\sum }_{t=1}^{n}d(x_t,{\widehat{x}}_t)\mathrm{.}$

If the same ordered blocks are labeled $x_a^{a+n-1}:=(x_a,\dots ,x_{a+n-1})$ and ${\widehat{x}}_a^{a+n-1}:=({\widehat{x}}_a,\dots ,{\widehat{x}}_{a+n-1})$, for any integer $a$, the equivalent formula is

$d_n(x_a^{a+n-1},{\widehat{x}}_a^{a+n-1})=\frac{1}{n}{\sum }_{i=a}^{a+n-1}d(x_i,{\widehat{x}}_i)\mathrm{.}$

The substitution $i=a+t-1$ gives the defining sum, so changing the coordinate labels changes neither the block distortion nor its normalization. In particular, blocks $X_0^{n-1}$ use the indices $0,\dots ,n-1$, while blocks $X^n=(X_1,\dots ,X_n)$ use $1,\dots ,n$.

When the alphabets are finite and nonempty and $d$ is finite-valued, define $d_{\max }:={\max }_{x,\widehat{x}}d(x,\widehat{x})$. Expected distortion is $\mathbb{E}{d}_n(X^n,{\widehat{X}}^n)$; the excess-distortion probability at threshold $D$ is $\mathbb{P}(d_n(X^n,{\widehat{X}}^n)>D)$. These are distinct criteria: one is an expectation and the other is a tail probability.