Why Truncate Before Quantizing?
A dyadic grid gives a convenient way to replace function values by nearby multiples of powers of \(2\). For a bounded nonnegative function, a fixed grid and a downward rounding rule produce only finitely many values. For an unbounded function, however, rounding every value on the same grid generally produces infinitely many values. It may also fail to handle a function that takes the value \(+\infty\). Truncating first resolves both issues: at stage \(n\), cap the function at \(n\), then round down to the grid of mesh \(2^{-n}\).
Throughout the main construction, \((X,\mathcal{M},\mu)\) is an arbitrary measure space; no finiteness, sigma-finiteness, or completeness assumption is needed. The function \(f:X\to[0,\infty]\) is extended-real-valued and \(\mathcal{M}\)-measurable. A simple function here means a measurable function with finitely many finite real values. The approximations below are simple functions in this sense, even when \(f\) itself takes the value \(+\infty\).
The Construction and Its Pointwise Behaviour
The formula can be written using finitely many measurable level sets. For \(k=0,\ldots,n2^n-1\), let $$ E_{n,k}=\left\{x\in X:\frac{k}{2^n}\le a_n(x)<\frac{k+1}{2^n}\right\}, $$ and let \(E_{n,*}=\{x\in X:a_n(x)=n\}\). These sets are measurable because \(a_n\) is measurable and the intervals and singleton used in their definitions are Borel sets. They are pairwise disjoint and cover \(X\): every \(a_n(x)\in[0,n]\) either lies in exactly one of the half-open intervals displayed or equals \(n\). Thus $$ q_n=\sum_{k=0}^{n2^n-1}\frac{k}{2^n}\chi_{E_{n,k}}+n\chi_{E_{n,*}}. $$ This representation shows directly that \(q_n\) is a measurable simple function. Its possible values are among \(0,2^{-n},\ldots,n\), a finite set.
Proof. The finite measurable representation just established proves that every \(q_n\) is nonnegative, measurable, and finite-valued. To prove monotonicity, write \(Q_n(t)=2^{-n}\lfloor2^nt\rfloor\) for \(t\ge0\). The truncations satisfy \(a_n\le a_{n+1}\). Also \(Q_{n+1}\) is nondecreasing, and, for \(t\ge0\), $$ \left\lfloor2^{n+1}t\right\rfloor =\left\lfloor2(2^nt)\right\rfloor \ge 2\left\lfloor2^nt\right\rfloor. $$ Consequently \(Q_{n+1}(t)\ge Q_n(t)\). Combining these inequalities gives $$ q_{n+1}=Q_{n+1}(a_{n+1})\ge Q_{n+1}(a_n)\ge Q_n(a_n)=q_n $$ at every \(x\in X\).
Fix \(x\in X\). If \(f(x)=c<\infty\), then for every integer \(n>c\), \(a_n(x)=c\). The definition of the floor gives $$ 0\le c-2^{-n}\lfloor2^nc\rfloor<2^{-n}. $$ Since \(2^{-n}\to0\), this proves \(q_n(x)\to c=f(x)\). If \(f(x)=+\infty\), then \(a_n(x)=n\), and \(q_n(x)=2^{-n}\lfloor2^nn\rfloor=n\) for every \(n\). Thus \(q_n(x)\to+\infty=f(x)\). These cases establish pointwise convergence everywhere. \(\square\)
Worked Constructions
Worked Example: A Function with an Infinite Value
Take \(X=\{a,b,c\}\), \(\mathcal{M}\) equal to its power set, and \(\mu\) counting measure. Define the extended-real-valued measurable function by \(f(a)=1/3\), \(f(b)=5/4\), and \(f(c)=+\infty\). Compute the first three approximants.
At \(n=1\), the cap is \(1\) and the mesh is \(1/2\). Therefore $$ q_1(a)=\frac12\left\lfloor\frac23\right\rfloor=0,\qquad q_1(b)=\frac12\lfloor2\cdot1\rfloor=1,\qquad q_1(c)=1. $$ At \(n=2\), the cap is \(2\) and the mesh is \(1/4\): $$ q_2(a)=\frac14\left\lfloor\frac43\right\rfloor=\frac14,\qquad q_2(b)=\frac14\lfloor5\rfloor=\frac54,\qquad q_2(c)=2. $$ At \(n=3\), the cap is \(3\) and the mesh is \(1/8\): $$ q_3(a)=\frac18\left\lfloor\frac83\right\rfloor=\frac14,\qquad q_3(b)=\frac18\lfloor10\rfloor=\frac54,\qquad q_3(c)=3. $$ Thus the displayed triples are \((0,1,1)\), \((1/4,5/4,2)\), and \((1/4,5/4,3)\). Each coordinate is nondecreasing. At \(c\), the approximants increase without bound, as required for convergence to \(f(c)=+\infty\); at \(a\) and \(b\), the theorem gives convergence to \(1/3\) and \(5/4\), respectively.
Worked Example: Quantizing \(1/x\) on an Open Interval
Let \(X=(0,1)\) with the Lebesgue sigma-algebra and Lebesgue measure \(m\), and let \(f(x)=1/x\). This is a finite-valued, nonnegative measurable function on \(X\). Compute \(q_2\), whose cap is \(2\) and whose mesh is \(1/4\).
For \(k=0,1,2,3\), the level band for \(a_2=f\wedge2\) lies below \(1\), so it is empty because \(f(x)>1\) throughout \(X\). For \(k=4,5,6,7\), solving the band inequalities gives $$ \begin{aligned} E_{2,4}&=\left\{x\in(0,1):1\le \frac1x<\frac54\right\}=(4/5,1),\\ E_{2,5}&=\left\{x\in(0,1):\frac54\le \frac1x<\frac32\right\}=(2/3,4/5],\\ E_{2,6}&=\left\{x\in(0,1):\frac32\le \frac1x<\frac74\right\}=(4/7,2/3],\\ E_{2,7}&=\left\{x\in(0,1):\frac74\le \frac1x<2\right\}=(1/2,4/7]. \end{aligned} $$ The cap set is \(E_{2,*}=\{x\in(0,1):1/x\ge2\}=(0,1/2]\). The open endpoint at \(1\) in the first band is excluded because \(1\notin X\); the other endpoints follow from the weak lower and strict upper inequalities in each band. The sets partition \(X\), and $$ q_2=\frac54\chi_{(2/3,4/5]}+\frac32\chi_{(4/7,2/3]}+\frac74\chi_{(1/2,4/7]}+2\chi_{(0,1/2]}+\chi_{(4/5,1)}. $$ The last term has coefficient \(1\), corresponding to \(k=4\).
For an exact integral check, the lengths of the five intervals, in the order of values \(1,5/4,3/2,7/4,2\), are \(1/5,2/15,2/21,1/14,1/2\). Hence $$ \int_X q_2\,dm=\frac15+\frac54\frac{2}{15}+\frac32\frac{2}{21}+\frac74\frac{1}{14}+2\frac12 =\frac15+\frac16+\frac17+\frac18+1=\frac{1373}{840}. $$ As a check by level sets, \(q_2\) has increments of \(1/4\); the measures of \(\{q_2\ge j/4\}\) for \(j=1,\ldots,8\) are \(1,1,1,1,4/5,2/3,4/7,1/2\). Their sum is \(1373/210\), and multiplying by \(1/4\) again gives \(1373/840\).
Truncation-First and Direct Dyadic Formulas
The same construction can be written directly using the level sets of \(f\), without naming the intermediate truncation. For every \(n\ge1\), $$ q_n=\sum_{k=0}^{n2^n-1}\frac{k}{2^n} \chi_{\left\{k/2^n\le f<(k+1)/2^n\right\}} +n\chi_{\{f\ge n\}}. $$ Indeed, for \(f(x)<n\), exactly one of the displayed bands contains \(f(x)\), and its coefficient is the downward-rounded value. For \(f(x)\ge n\), including \(f(x)=+\infty\), the final term gives the value \(n\). Thus this direct level-set formula and truncation followed by quantization define exactly the same function.
There is an important distinction between this finite-range formula and the naive untruncated rounding \(2^{-n}\lfloor2^nf\rfloor\). On an unbounded function, the latter can take infinitely many values, so it need not be a simple function. At points where \(f=+\infty\), its floor is not a finite real number at all. The cutoff at \(n\) is what guarantees finitely many finite values at each stage.
Worked Example: An Unbounded Function on the Counting Space
Let \(X=\mathbb{N}=\{1,2,\ldots\}\) with counting measure and its power-set sigma-algebra, and let \(f(k)=k\). For fixed \(n\), the untruncated dyadic rounding takes the values \(2^{-n}\lfloor2^nk\rfloor=k\) for all \(k\in\mathbb{N}\). It therefore has infinitely many values and is not a simple function.
The truncated approximant has only the finite range \(0,2^{-n},\ldots,n\). At \(n=2\), \(q_2(1)=\frac14\lfloor4\rfloor=1\), while for every \(k\ge2\), \(f(k)\wedge2=2\), so \(q_2(k)=\frac14\lfloor8\rfloor=2\). Hence \(q_2=1\chi_{\{1\}}+2\chi_{\{2,3,\ldots\}}\), a finite-valued measurable simple function. For a fixed \(k\), whenever \(n>k\), the cap does not change \(f(k)\), and \(2^nk\) is an integer; hence \(q_n(k)=k\). This verifies pointwise convergence at every \(k\) directly.
Endpoint and Range Pitfalls
A level-set error can arise when a calculation silently replaces the domain by a closed interval. In the preceding example, for \(1\le k\le4\), the condition \(1/x\ge k/4\) holds for every \(x\in(0,1)\). The set is therefore \((0,1)\), not \((0,1]\). A uniform expression that preserves the domain is $$ \left\{x\in(0,1):\frac1x\ge\frac{k}{4}\right\} =(0,1)\cap(0,4/k]. $$ For \(1\le k\le4\), this intersection is \((0,1)\); for \(5\le k\le8\), it is \((0,4/k]\). Retaining the intersection prevents an excluded domain endpoint from entering the level set.
A second common mistake is to call every downward dyadic rounding a simple function. For example, on \(\mathbb{N}\) the untruncated rounding of \(f(k)=k\) has infinitely many values, as computed above. Simple functions must have finite range. The correction is to impose the finite cap first, or equivalently to include the final measurable set \(\{f\ge n\}\) with coefficient \(n\) in the direct formula.
Check Your Understanding
For each question, distinguish the finite cutoff from the dyadic rounding rule, and pay attention to the domain and the level-set endpoints.
- For \(f:X\to[0,\infty]\), write the finite measurable partition used to express \(q_n\) as a simple function.
- Why does \(q_n(x)\to+\infty\) when \(f(x)=+\infty\), even though every \(q_n(x)\) is finite?
- On \(X=(0,1)\), find the set \(\{x:1/x\ge3/2\}\), retaining the domain endpoint conventions.
- For \(f(k)=k\) on \(\mathbb{N}\), compute \(q_3(1)\), \(q_3(2)\), and \(q_3(4)\).
- Explain why untruncated dyadic rounding of an unbounded function need not be a simple function.