{'fraction_non_alphanumeric': 0.06350124342143311, 'fraction_numerical': 0.014227054537042393, 'mean_word_length': 3.6798376184032477, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Beyond Countable Alphabets: An Extension of the Information-Spectrum Approach

A general approach is established for deriving one-shot performance bounds for information-theoretic problems on general alphabets beyond countable alphabets. It is mainly based on the quantization idea and a novel form of"likelihood ratio". As an example, one-shot lower and upper bounds for random number generation from correlated sources on general alphabets are derived.


I. INTRODUCTION
The information-spectrum approach, since its introduction by Han and Verdú [1], has become one of the most important tools of information theory. Similar to Shannon's classical approach (see e.g., [2]), the information-spectrum approach is mainly confined to countable alphabets, though in some cases, its extension to continuous alphabets is direct. The difficulty comes from two aspects: 1) It is difficult to formulate information measures and performance bounds for arbitrary alphabets in a unified way. The Radon-Nikodym derivative seems a good candidate, or a good basis for defining information measures, but it exists only if the absolute-continuity condition is satisfied.
2) It is difficult to extend certain useful proof techniques from finite alphabets to general alphabets, and even to countably infinite alphabets. For example, it is not easy to construct an analog of the random-bin map when the domain is uncountable, and it is also difficult to generalize structured random coding techniques (such as random matrices) to the case of infinite alphabets. This paper will partly solve this problem by providing a general approach for one-shot performance bounds, an important part of the information-spectrum approach. Our main approach is based on quantization, which effectively overcomes the second difficulty. Given any problem on infinite alphabets, we take the following steps: 1) modifying the problem by quantization so that the modified version can be described on finite alphabets and hence has already a solution; 2) converting the solution of the modified problem into a solution of the original problem; and 3) repeating the first and second steps with a sequence of quantizations with increasing resolution to get the asymptotically optimal solution. This idea may look simple, but is difficult to be developed into a general approach. In the rest of this paper, we will give the basic results of this approach and then illustrate this approach by an example. We will also introduce a novel form of "likelihood ratio", a generalization of the Radon-Nikodym derivative that perfectly solves the first difficulty.
We close this section with some notations used throughout this paper. The field of real numbers is denoted by R, and the set of integers from 1 to n is denoted by [n]. When performing probabilistic analysis, all objects of study are related to a basic probability space (Ω, A, P ) with A a σ-algebra in Ω and P a probability measure on (Ω, A). A random element in a measurable space (X , X) is a measurable mapping from Ω into X . For probability measures µ and ν on (X , X), the statistical distance between µ and ν is Measure-theoretic methods will be used in this paper. Readers not familiar with measure theory are referred to [3]- [5]. All measures considered in this paper are finite. For a topological space S, its Borel σ-algebra generated by the topology in S is denoted by B(S). The integral of a real-valued, measurable function f on some measure space (X , X, λ) is denoted by λf = λ(f ). When λ is a probability measure, we write E λ f = E λ (f ) in place of λf and write E f if λ = P . If λ|f | < +∞, then λf induces a finite signed measure (f · λ)(A) := λ(f 1 A ) on (X , X). Given a sub σ-algebra F of X, we denote by λ F f the density function d(f · λ)| F /dλ| F , which is called the conditional expectation of f with respect to F if λ is a probability measure. In this case, we wirte E F λ f in place of λ F f . For A ∈ X, λ F (A) := λ F 1 A defines a kernel from (X , F) to (X , X). For a kernel µ from (X , X) to (Y, Y), we denote by µ B the real-valued map x → µ(x, B) for some fixed B ∈ Y, and by µ x the measure on (Y, Y) for some fixed x ∈ X . Thus λ(µ B ), as a function of B, becomes a measure on (Y, Y), and is usually written as λ(µ). The extended kernel µ of µ is a kernel from (X , X) to (X × Y, X × Y) given by (x, C) → µ(x, C x ) with C x = {y : (x, y) ∈ C}. The product λ×µ := λ(µ) is a measure on (X ×Y, X×Y), and we simply write λµ when there is no possible ambiguity. Note that λµ coincides with the product-measure notion when µ reduces to a measure on (Y, Y).

II. THE QUANTIZATION APPROACH
In this section, we will establish the basic results of the quantization approach. Because of the space limitation, most simple proofs are omitted. The readers are referred to [6] for omitted proofs.
We first give an overview of the main tricks of our approach. Trick 2.1 (Quantization): Given a measurable space (X , X), a finite quantization of X can be characterized by a finite sub σ-algebra F of X, which induces a natural projection π F from X to atoms(F) given by x → z such that x ∈ z, where atoms(F) is the set of all elements in F that cannot be decomposed into smaller pieces that are also in F. In fact, atoms(F) forms a finite partition of X .
be a family of real-valued integrable functions on the measure space (X 1 × X 2 , X 1 × X 2 , µ). Let ǫ > 0. By Theorem 2.4, for each i ∈ [ℓ], there is a finite sub σ-algebra C i,j of X j for each j ∈ [2] such that In the same vein and by Corollary 2.5, we can show that, for any ν ≪ µ, there is a finite sub σ-algebra F of . Then we can find a sequence (F n ) ∞ n=1 of finite sub σ-algebras so that each sequence g for any p-norm of R ℓ with p ≥ 1, where ν → is the shorthand of convergence in ν-measure. Similar tricks with Theorems 2.6 and 2.15 also work for statistical distances and likelihood ratios (Trick 2.3).

Trick 2.3 (Handling likelihood ratios by Theorems 2.15):
Likelihood ratios may be the objects most often occurring in a one-shot performance bound. Let µ and ν be two measures on (X × Y, X × Y). The likelihood ratio of µ to ν is Having introduced the main tricks, we proceed to introduce the details of the quantization approach. Theorem 2.4: Let f be a real-valued integrable function on the measure space (X × Y, X × Y, µ). Then for any ǫ > 0, there is a finite sub σ-algebra C of X and a finite sub σ-algebra f is integrable and can be finitely approximated} It is clear that A is a π-system containing X × Y, and we have: In other words, f + g ∈ H. In a similar way, we can show that cf ∈ H for c ∈ R.
(c) If f n ∈ H converges everywhere to an integrable function g (including all bounded functions for finite µ) with |f n | ≤ |g|, then by the dominated convergence theorem, µ|f N − g| < ǫ/4 for some large integer N . Furthermore, By the monotone class theorem for functions ([4, Theorem 6.1.3]) with properties (a)-(c), we conclude that H contains all bounded functions measurable with respect to σ(A) = X × Y. Again by (c) with f n (p) = g(p)1{g(p) ≤ n} for arbitrary integrable g, it is easy to see that H contains all integrable functions.
Corollary 2.5: Let f be a real-valued integrable function on the measure space (X × Y, X × Y, µ). Let ν be a measure such that ν ≪ µ. Then for any ǫ > 0, there is a finite sub σ-algebra C of X and a finite sub σ-algebra D of Y such that Theorem 2.6: Let µ be a probability kernel from (X , X, λ) to (Y, P(Y)) with Y at most countable. Then for any ǫ > 0, there is a finite sub σ-algebra C of X such that A performance bound obtained by the information-spectrum approach is often expressed in terms of some kind of random likelihood ratios, it is thus necessary to understand the notions of likelihood ratios well. Usually, a likelihood ratio is expressed as a Radon-Nikodym derivative of two probability measures. Sometimes, however, we will encounter a more complicated form of likelihood ratios, a Radon-Nikodym derivative of two probability kernels. In the discrete case, it can be written as P Y |X (y | x)/PŶ |X (y | x), and we have A generalization of this identity is given as follows. Theorem 2.7: Let µ and ν be two kernels from (X , X, λ) to (Y, Y) such that µ x ≪ ν x for λ-almost every x in X . Then λµ ≪ λν and for λ-almost every x, This theorem tells us that in general cases we need to use the form d(λµ)/d(λν) in place of dµ x /dν x because the former is always measurable with respect to X × Y. A useful consequence of Theorem 2.7 is: Corollary 2.8: Let µ and ν be two probability kernels from the probability space (X , The Radon-Nikodym derivative dµ/dν cannot handle all cases of likelihood ratios, because it does not exist if µ is not absolutely continuous with respect to ν. In this case, we need a more general form of likelihood ratios based on the approach of [7]. Recall that the (real) projective line is defined as the set of lines through the origin in the affine plane R 2 , and points R(x, y) of the projective line are written as (x : y) (homogeneous coordinates), reflecting the fact that R(x, y) = R(z, w) iff x/y = z/w (for y, w = 0). In analogy, we define P, the nonnegative part of the projective line, as follows: forms a ray through the origin in R 2 ≥0 iff (r, s) is admissible. The half projective line P is defined as the set of rays through the origin in R 2 ≥0 , and points R >0 (r, s) of P are written as [r : s], or simply as r/s when s = 0 and there is no possible ambiguity. The natural projection π P : R 2 ≥0 \ {(0, 0)} → P given by (x, y) → [x : y] thus induces a quotient topology in P, so that π P becomes a quotient map and is measurable with respect to the corresponding Borel σ-algebras.
Since the map ρ : R 2 ≥0 \{(0, 0)} → [0, 1] given by (x, y) → x/(x+y) is a quotient map, it follows from [8,Corollary 22.3] that ρ induces a homeomorphism κ : P → [0, 1] given by which further induces a metric and an order on P. Definition 2.10: The metric d P on P is defined by The order ≤ of P is defined by It is clear that P with metric d P is a complete separable metric space.
For any real-valued functions f and g on X , if (f (x), g(x)) is admissible for all x ∈ X , then the function [f : g](x) := [f (x) : g(x)] is well defined and is also called admissible (on X ). Conversely, any P-valued function on X can be written as with f 1 , f 2 , g 1 , and g 2 all real-valued measurable functions on X , then there is a real-valued measurable function t on X such that t(x) = 0, f 1 (x) = t(x)f 2 (x), and g 1 (x) = t(x)g 2 (x) for all x ∈ X .
Let µ be a measure on (X , X). If [f : g] is admissible on X except a µ-negligible set of points, then we say [f : g] is admissible µ-almost everywhere. Similarly, if [f 1 : g 1 ] = [f 2 : g 2 ] is true for all x ∈ X except a µ-negligible set of points, we say [f 1 : Proposition 2.13: Let f and g be two real-valued integrable functions on the measure space (X , X, µ). If [f : g] is admissible µ-almost everywhere, then the conditional expectation µ F [f : g] := [µ F f : µ F g] with respect to some sub σ-algebra F is also admissible µ-almost everywhere.
We are now ready to define the general form of likelihood ratios.
Likelihood ratios enjoy the following property, which is an easy consequence of Corollary 2.5.

III. AN EXAMPLE: SEPARATE RANDOM NUMBER
GENERATION FROM CORRELATED SOURCES In this section, we will explain the quantization approach by an example: separate random number generation from correlated sources. For its importance in information theory, the readers are referred to [9]. The finite-alphabet case of this problem has been extensively studied in [10] and the references therein. We will now extend this result to the case of general alphabets.
We first briefly introduce the problem of separate random number generation. For simplicity, we only consider the case of two correlated sources with side information at the tester.
Let X = (X 0 , X 1 , X 2 ) be a triple of correlated random elements in X 0 × X 1 × X 2 . Let ϕ = (ϕ 1 , ϕ 2 ) be a pair of (randomness) extractors X i → Y i with Y i finite (i = 1, 2). We are interested in the minimum value of the statistical distance over all pairs ϕ of extractors, where U Y1 and U Y2 denote the uniform distributions over Y 1 and Y 2 , respectively. The next theorem gives one-shot bounds of d(X | ϕ) in the case of finite alphabets.
2) Conversely, every pair ϕ of extractors satisfies for all 0 < r < 1. Proof: When the alphabets are all finite, it is clear that ] P X -almost everywhere, and thus the theorem is trivially true because of Theorem 3.1.
2) Converse part: Similar to the proof of direct part, we first prove the converse part with general (X 0 , X 0 ) and other alphabets finite. Again by Trick 2.2 with Theorems 2.6 and 2.15, we have (3) and (4), so that where the last inequality follows from the Portmanteau theorem, and A r denotes the closure of A r . Then we turn to the general case. By Trick 2.2 with Theorem 2.15, we can find a sequence ((C n,1 , C n,2 )) ∞ n=1 of pairs of finite sub σ-algebras satisfying (5) and σ(ϕ i ) ⊆ C n,i for all n and i. Then for every n and i, we have ϕ i = ψ n,i • π Cn,i for some ψ n,i , and therefore where the last inequality follows from the Portmanteau theorem. Finally, where s k = (r + 1/k) ∧ 1, namely, the minimum of r + 1/k and 1. Remark 3.3: Note that even if the alphabets X i are all continuous, there are many nontrivial situations in which T i X (X) does not degenerate to the point [1 : 0]. For simplicity, let us assume that X 2 is constant. If X 1 is a (p, 1 − p)-mixture of a real number and a uniform random variable in [0, 1], both independent of X 0 , then T 3 X (X) is a random variable taking values in {1/p, [1 : 0]} with probabilities p and 1 − p, respectively. Note that the extractors in our problem are fixedlength extractors. This example tells us that the performance of a fixed-length extractor is dominated by the worst case. If X 1 takes values in {X 0 − 0.5, X 0 + 0.5} with equal probabilities and X 0 is uniformly distributed over [0, 1], then T 3 X (X) = 2 almost surely. This example shows that a random variable even with continuous distribution does not necessarily have infinite randomness because of the side information at the tester. The one-shot bounds provided by Theorem 3.2 are tight enough for the first-and second-order asymptotic analysis. If we define (which is well defined because (x, y) = (0, 0)), then we can easily obtain a generalization of the achievable rate region in the finite case, with for example the spectral inf-entropy rate H(X 1 | X 0 ) of general source X 1 given general source X 0 defined by :

IV. THE PROOFS OF RESULTS IN SECTION II
Proof of Corollary 2.5: Since ν ≪ µ, it follows from [3, Lemma 4.2.1] that there is a positive δ such that each measurable set A satisfying µ(A) < δ also satisfies ν(A) < ǫ. Using Theorem 2.4 with ǫ ′ = δǫ/2, we obtain by Markov's inequality that there is a finite sub σ-algebra C of X and a finite sub σ-algebra D of Y such that Proof of Theorem 2.6: Since E λ (µ) is a probability measure on Y, there is a finite subset B of Y such that For every y ∈ B, it follows from Theorem 2.4 that there is a finite sub σ-algebra C y of X such that for every σ-algebra F satisfying C y ⊆ F ⊆ X. Let C = σ( y∈B C y ), and then for every σ-algebra F satisfying C ⊆ F ⊆ X, Proof of Theorem 2.7: By Propositions 5.1 and 5.2, we immediately have λµ ≪ λν. For any C ∈ X × Y, where the last equality follows from Proposition 5.3. Taking C = A × B for any A ∈ X and B ∈ Y, we thus have for λ-almost every x in X , and for every such x, for all (x, y) except a λν-negligible set of points (Proposition 5.4). Proof of Corollary 2.8: where (6) follow from Theorem 2.7 and Proposition 5.3. Proof of Proposition 2.11: It is obvious by observing that [f : g] = π P (f (x), g(x)) with f , g, and π P all measurable.
Proof of Proposition 2.12: By definition, for every x ∈ X , there is a number t(x) = 0 such that f 1 (x) = t(x)f 2 (x) and g 1 (x) = t(x)g 2 (x). Then it suffices to show that t is measurable. Let A = {x : f 2 (x) = 0}. It is clear that which is measurable.
Proof of Theorem 2.15: First note that which is admissible (µ + ν)-almost everywhere by Proposition 2.13. From Corollary 2.5, it follows that there is a finite sub σ-algebra C of X and a finite sub σ-algebra D of Y such that for every σ-algebra F satisfying C×D ⊆ F ⊆ X×Y. Therefore ≥ ǫ < ǫ.

V. FACTS USED BY SECTION IV
Proposition 5.1: Let µ and ν be two kernels from the measure space (X , X, λ) to (Y, Y) such that µ x ≪ ν x for λ-almost every x in X . Then λ(µ) ≪ λ(ν).
Proof: Let ι x be the map of Y into X × Y given by y → (x, y), which is clearly measurable. Then where the second equality follows from [3, Lemma 2.6.8].

VI. CONCLUSION
In this paper, we develop a general approach for deriving one-shot bounds for information-theoretic problems on general alphabets. This approach provides a mechanical way for solving problems on general alphabets based on their solutions in the finite-alphabet case, and hence it helps us better understand information theory in a unified way beyond countable alphabets. This is still an ongoing research. Applying this approach to other problems of information theory will be our future work.