{'fraction_non_alphanumeric': 0.05733503646094394, 'fraction_numerical': 0.009523501544133103, 'mean_word_length': 3.7590027700831024, 'pattern_counts': {'":': 0, '<': 21, '<?xml version=': 0, '>': 42, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 18, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A Generalized Typicality for Abstract Alphabets

A new notion of typicality for arbitrary probability measures on standard Borel spaces is proposed, which encompasses the classical notions of weak and strong typicality as special cases. Useful lemmas about strong typical sets, including conditional typicality lemma, joint typicality lemma, and packing and covering lemmas, which are fundamental tools for deriving many inner bounds of various multi-terminal coding problems, are obtained in terms of the proposed notion. This enables us to directly generalize lots of results on finite alphabet problems to general problems involving abstract alphabets, without any complicated additional arguments. For instance, quantization procedure is no longer necessary to achieve such generalizations. Another fundamental lemma, Markov lemma, is also obtained but its scope of application is quite limited compared to others. Yet, an alternative theory of typical sets for Gaussian measures, free from this limitation, is also developed. Some remarks on a possibility to generalize the proposed notion for sources with memory are also given.


I. INTRODUCTION
The notion of typicality is one of the central concepts in information theory, especially for deriving inner bounds of various coding problems. There are many notions of typicality used these days. Among them, perhaps the most convenient one for network information theory is the notion of so called the strong typicality [1, p.326], or its variants such as the robust typicality [2]. The notion is based on the idea that a long samples from an i.i.d. source has a property that its empirical distribution is sufficiently close to the true distribution with high probability.
However, it is not so clear how to represent this "closeness" when the source takes infinitely many values, so This paper was in part presented at the IEEE International Symposium on Information Theory (ISIT), Honolulu, HI, USA, July 2014. usually strong typical sets (and their variants) were only defined on finite alphabets. On the other hand, there is another notion called the weak typicality [1, p.59] which can be defined for a wide class of sources, including i.i.d. sources on the Euclidean space of certain dimension with a well-defined density functions. However, it turns out that this notion of typicality is not so useful for various multi-terminal coding problems, since it lacks many properties of strong typicality that are widely used; for example, the conditional typicality lemma does not hold for weak typicality [3, p.32]. Accordingly, many previous researches on deriving inner bounds primarily concerned only finite alphabet problems. Hence, generalizing the strong typicality to a more general class of sources is a key to solve various multi-terminal coding problems for general alphabets.
There were several attempts in this direction. For example, in [4], a generalization of strong typicality was introduced, which can be applied when the alphabet is a Polish space (a separable completely metrizable topological space). The main idea was based on a famous duality between the space of continuous bounded functions and the space of countably-additive compact-regular Borel measures. Lots of useful properties of usual strong typicality still hold here, but there are some limitations; the natural class of functions under consideration in this typicality, is the set of continuous bounded functions, which is too restrictive. Even the average power constraint for Gaussian channels cannot be directly handled, so a kind of truncation arguments were needed; see [4,Section VI]. Also, in [5], a more general notion of strong typicality which can be applied when the alphabet is a standard Borel space [6] (which is essentially just a Polish space, but topology need not be explicitly given) was introduced. However, this notion of typicality lacks some crucial properties of the usual strong typicality, including the conditional typicality lemma. Another notion of typicality which is applicable when the alphabet is countable was introduced in [7].
In this paper, a new notion of typicality for an arbitrary probability measure on a standard Borel space is proposed. The class of those measurable spaces is fairly general; in particular, every separable Banach space endowed with the Borel σ-algebra belongs to the class. It turns out that both the classical notions of strong and weak typicality are special cases of the proposed notion of typicality. Lots of useful results about strong typicality for finite alphabets continue to hold in this generalization. Those results were the fundamental tools for proving achievability. For instances, asymptotic equipartition property, conditional typicality lemma, joint typicality lemma, packing and covering lemmas (as well as there "mutual versions") can be derived in this generalization. Hence, one do not need to do anything further (such as quantization arguments) to generalize a result for finite alphabet case into the general case, whenever the result is a consequence of those lemmas. Another fundamental tool called Markov lemma, is also obtained but its scope of application is quite limited compared to others. However, it is shown that we can develop an alternative theory of typical sets so that those restrictions disappear, when every involved probability measure is Gaussian.
The rest of this paper is organized as follows. We first introduce the new definition of typical sets in Section II, and introduce some basic properties in Section III. Joint typicality lemma, packing lemma, and covering lemma are obtained in Section IV. Section V is devoted to applications to coding problems. Section VI deals with Markov lemma. In Section VII, we show that limitations on Markov lemma can be very much relaxed when considering problems involving only Gaussian measures. Finally, we discuss how to extend the proposed notion to sources with memory in Section VIII.

II. DEFINITION OF TYPICAL SETS
Most of the useful results about the strong typicality in the case of finite alphabet are based on a simple lemma called typical average lemma [3, p.26]. The lemma says that the sample average of any nonnegative function on the alphabet should be close to the true average, whenever the samples are typical. The main idea of the new definition is to make a list of "test functions" for which the typical average lemma should hold. This idea is similar to the notions of typicality in [4] or [5]. However, those notions only utilize bounded measurable functions. The notion of typicality defined in this paper utilizes any integrable functions, and such a treatment is required because many useful functions in information theory are actually unbounded. Use of unbounded functions makes some proofs (for instance, the proof of Theorem III.2) much easier and intuitive. In [5], it is claimed that boundedness condition can be removed by considering suitable finite moment conditions and some straightforward truncation processes.
But such processes are often time-consuming and tedious. Basically, the approach of this paper does not rely on boundedness, and such truncation processes are required for only some basic results. One can perhaps completely forget about boundedness and truncation issues when applying the results to actual coding problems.
There are three parameters to determine conventional typical sets: a probability distribution µ, the number of samples n, and a positive real number ǫ > 0. The ǫ > 0 determines how the empirical distribution should be close to the true distribution µ; hence, one may call this ǫ as a typicality criterion. However, the new definition requires some extra information rather than just a positive real number ǫ to determine this "closeness". The first one of those extra information is the list of test functions which are integrable, and not necessarily nonnegative. Those functions are the candidates for the typical average lemma. The second is a set of points in the alphabet "to be excluded"; this is added due to some technical reasons, because it is crucial when proving some theorems. One can think of this "set of excluded points" as something similar to the set of points at which the probability mass function vanishes for the case of finite alphabet (see Example II.5). In [4], the "closeness" is given with respect to a metrizable topology, so no extra information other than ǫ was necessary. On the other hand, [5] uses a similar typicality criteria to that used here.
Before giving the precise definition of the new notion of typicality, first we define some notations which will be used throughout this paper. The set of positive integers (excluding 0) is denoted as Z + , and any function is assumed to be extended real-valued, if not specified. The base of a logarithm is always taken to be 2. The terminal object in the category of sets (that is, a singleton set whose actual value of the element is not important) will be denoted as { * }. This set will be served as the trivial alphabet admitting the only one probability measure. For any measuretheoretic terminologies and notations that is not defined in this paper, refer to [8], [9], or [10]. Every measure in this paper is assumed to be positive and countably-additive. We often omit to write the σ-algebra of a measurable space. For a measurable space (Z, C ), the set of every probability measure on Z is denoted as ∆(Z), and the set of every measure on Z is denoted as P(Z). The point-mass measure at a point x is denoted as d x . For a measure µ, the set of every µ-integrable function is denoted as L 1 (µ). This L 1 (µ) is a set of functions; it is not a set of December 15, 2014 DRAFT equivalence classes of µ-almost equivalent functions. This distinction was made because the empirical distribution is sensitive to pointwise behaviors. The indicator function of a set A is denoted as ½ A . Given a measure µ ∈ P(X) and a measurable mapping f : X → Y , the pushforward of µ by f means the measure f * µ : on Y . The set of integers m such that u ≤ m ≤ ⌈U ⌉ (u ≤ m ≤ ⌊U ⌋, respectively) for some integer u and a real number U ≥ u will be denoted as [u : U ] ([u : U ), respectively). We denote by a := b to say a is defined as b.
Throughout this section, let (X, A ) be a measurable space. This space X will be served as the alphabet.
The set of every µ-typicality criterion naturally becomes a lattice (a poset having the supremum and the infimum for any pair of elements); for µ-typicality criteria U 1 = (F 1 ; ǫ 1 ; N 1 ) and is the greatest lower bound.

Definition II.2 (Typical sets).
Let µ ∈ ∆(X) and n ∈ Z + . Let U = (F ; ǫ; N ) be a µ-typicality criterion. The µ-typical set of length n with respect to U is defined as By definition, a function in F automatically satisfies the typical average lemma.
2) The collection F can be empty; in that case, T (n) In [4], a sequence is declared to be typical, if its empirical distribution belongs to a weak-* neighborhood of the true distribution. A basic open neighborhood in the weak-* topology is characterized by integrations of a finite collection of bounded continuous functions, so the notion of typicality in [4] is essentially a special case of the notion of typicality just introduced.
Typical sets should be measurable sets; otherwise, a notion such as "the probability that a sequence is typical" does not make sense.

December 15, 2014 DRAFT
Proof: Let U = (F ; ǫ; N ). Consider the function given by Assume that X is a nonempty finite set and A is the power set of X. Then a probability measure µ ∈ ∆(X) can be completely characterized by a probability mass function p X on X. Define N := {x ∈ X : p X (x) = 0}. For given is exactly the strong typical set appearing in [1, p.326].
On the other hand, we get the robust typical set used in [3] Example II.6 (Weak typicality).
Assume that (X, A ) is the real line with the Borel σ-algebra. Let µ be a Borel probability measure having a density function f X , and assume that the differential entropy h(µ) := − log f X dµ exists and finite. Hence, Let (Y, B) be another measurable space. We show that typical sets in X can be related to typical sets in Y by a measurable mapping from X to Y . Definition II.7 (Pullback of typicality criteria).
Let ν ∈ ∆(Y ) and V = (G ; ǫ; K) be a ν-typicality criterion. Let φ : X → Y be a measurable mapping. Then the pullback of V under φ is defined as Proposition II.8.
Let µ ∈ ∆(X) and φ : X → Y be a measurable mapping. Let V be a φ * µ-typicality criterion. Then, φ * V is a µ-typicality criterion, and T ∈ K for all i = 1, · · · , n and if and only if x n ∈ T (n) December 15, 2014 DRAFT Hence, one can say that if a sequence in X is typical with respect to µ, then its image under φ in Y is also typical with respect to φ * µ. In particular, this fact is important when φ is a projection. Consider µ ∈ ∆(X × Y ) and the canonical projection φ = π X : X × Y → X. By applying the proposition to this case, one can say that if a sequence in X × Y is typical with respect to µ, then its X-components are also typical with respect to the marginal distribution of µ.

III. BASIC PROPERTIES
In this section, we will explore some important properties of the proposed notion of typicality. Let (X, A ) and (Y, B) be measurable spaces.
The following is a simple consequence of the weak law of large numbers: Theorem III.1 (Asymptotic equipartition property).
Let µ ∈ ∆(X) and U be a µ-typicality criterion. Then, Here µ n denotes the n-fold product measure of µ. Two main reasons why the above theorem holds is: first, any function in F is µ-integrable, and second, F is a finite set.
Proof: Let U = (F ; ǫ; N ), then for each f ∈ F , by the weak law of large numbers, Note that the weak law of large numbers still holds without the assumption of finite variance. Let δ > 0 be given, then for any f ∈ F , it follows that for sufficiently large n; say, n ≥ n f ∈ Z + . Since µ n (X n \ (X \ N ) n ) = 0, for n ≥ max f ∈F n f . Hence, it follows that lim n → ∞ µ n T (n) U (µ) = 1. Using the result above, we will prove an important statement about the size of a typical set. In the next theorem, we use the notation D(µ ν) for a probability measure µ and a σ-finite measure ν to denote the following quantity: provided that the integral exists, for the case when µ ≪ ν. Here, µ ≪ ν means that µ is absolutely continuous with respect to ν; that is, whenever ν(A) = 0 for some A ∈ A , then µ(A) = 0. For µ ≪ ν, dµ dν is the Radon-Nikodym derivative [9] of µ with respect to ν. If ν is a probability measure, then D(µ ν) becomes the usual Kullback-Leibler divergence [11], but here we allow ν to be an arbitrary σ-finite measure. Hence, D(µ ν) can be negative.
In particular, when ν is the counting measure, D(µ ν) is −H(µ), where H(µ) is the entropy of µ, and when ν is the Lebesgue measure on R d , D(µ ν) is −h(µ), where h(µ) is the differential entropy of µ.

1)
If D(µ ν) is finite, then for any ǫ > 0, there is a µ-typicality criterion U 0 such that for any µ-typicality for all n and for all sufficiently large n.

4)
If µ ≪ ν and D(µ ν) = −∞, then for any M ≥ 0, there is a µ-typicality criterion U 0 such that for any µ-typicality criterion U ≤ U 0 , we have for all sufficiently large n.
For the special case when ν is the counting measure (the Lebesgue measure, respectively), one can conclude that the cardinality (the volume, respectively) of a typical set is approximately the exponential of the entropy (the differential entropy, respectively).

Proof:
1) Choose g = dµ dν and define U 0 := (log g; ǫ ′ ; ∅), where 0 < ǫ ′ < ǫ. Fix n ∈ Z + and a µ-typicality criterion U ≤ U 0 , then by the definition of typical sets, , so for that case we have December 15, 2014 DRAFT Consider the following identity: Hence, it follows that Since we have µ n T (n) U (µ) ≤ 1 for all n, it follows that for all n. Also, for sufficiently large n, we have µ n T (n) U (µ) ≥ 1 − δ for any given small δ ∈ (0, 1), by the asymptotic equipartition property. Therefore, for such n, By taking n sufficiently large, we can assume that ǫ ′ + 1 n log 1 1−δ < ǫ, thus for sufficiently large n.
Fix n ∈ Z + and a µ-typicality criterion U ≤ U 0 , then for any x n ∈ T (n) so at least one x i should belong to A, concluding that T (n) For each k ∈ Z + , define a measurable function f k on X as Also, f + k k∈Z + is an increasing sequence of nonnegative measurable functions converging pointwise to (log g) + µ-almost everywhere, since we know that to have µ(X) < ∞. So by monotone convergence theorem [8], f + k dµ → (log g) + dµ = +∞ as k → ∞. Since f − k = (log g) − is integrable for all k, it follows that f k dµ → +∞ as k → ∞. Take k ∈ Z + so that f k dµ ≥ M + 1. Define U 0 := (f k ; 1; ∅). Fix n ∈ Z + and a µ-typicality criterion U ≤ U 0 , then , so for that case we have Proceeding as the same as the first part of the case 1, we get the result.
0 otherwise for each x ∈ X. Note that f + k = (log g) + for each k ∈ Z + and (log g) Also, f − k k∈Z + is an increasing sequence of nonnegative measurable functions converging pointwise to (log g) − µ-almost everywhere, since we know that So by monotone convergence theorem, we get f k dµ → log g dµ = −∞ as k → ∞ by considering positive parts and negative parts separately. Take k ∈ Z + so that f k dµ ≤ −M − 2. Define U 0 := (f k ; 1; ∅).
Fix n ∈ Z + and a µ-typicality criterion U ≤ U 0 , then , so for that case we have Proceeding as the same as the second part of the case 1, we get the result.
Although the proofs are much delicate, conditional versions of above theorems are also true. Before stating them, let us look at some definitions. The following definition is from [12,Chapter 4], but notations used here are different from it:

Definition III.3 (Measure kernels).
A measure kernel from X to Y is a mapping κ : We write κ(B|x) to denote κ(x)(B) for each x ∈ X and B ∈ B. The integration of a function g : Y → R with respect to the measure κ(x) is denoted as g(y) dκ(y|x) where y is a dummy variable. If for all x ∈ X, we call κ a probability kernel. The set of every probability kernel from X to Y is denoted as K(X; Y ). If there exists a countable partition (A k × B k ) k∈N + of X × Y by measurable rectangles such that κ(B k |x) < ∞ for all x ∈ A k for each k ∈ Z + , then κ is said to be σ-finite.
The conditional distribution of a random variable with respect to another random variable is an example of probability kernels. One can also view a probability kernel κ as a channel with the input alphabet X and the output alphabet Y .
The following notion is useful for discussions from now on.

Definition III.5 (Conditional typical sets).
Let ν ∈ ∆(X × Y ) and V be a ν-typicality criterion. For n ∈ Z + and x n ∈ X n , we define the conditional µ-typical set of length n with respect to V given x n as Note that a conditional typical set T (n) V (ν|x n ) is always measurable, since it is a section of the joint typical set T (n) V (ν), which is (A ⊗n ⊗ B ⊗n )-measurable. Now, we will prove conditional typicality lemma of [3, p.27] in our setting.
In the below, κ n : X n → ∆(Y n ) denotes the probability kernel defined as κ n ( Theorem III.7 (Bounded conditional typicality lemma).
Let µ ∈ ∆(X) and κ ∈ K(X; Y ). Then, for any µκ-bounded typicality criterion V, there exists a µ-bounded typicality criterion U and a positive number c > 0 such that The above theorem says that whenever the criterion of being jointly typical consists of essentially bounded functions, the probability that a random sequence y n , which is generated conditionally i.i.d. given a typical sequence x n , is jointly typical with x n , converges to 1 exponentially fast.
Proof: Let V = (G ; ǫ; K). We may assume that G consists of a single measurable function g : X × Y → R; one can easily modify the proof a little bit to deal with the general case. We can also assume that g is bounded on so there exists a µ-null set N so that κ(K x |x) = 0 for all x ∈ X \ N . Define a function f : X → R as and let U := (f ; ǫ ′ ; N ) for some ǫ ′ ∈ (0, ǫ), then U is a µ-bounded typicality criterion. Fix n ∈ Z + and x n ∈ T (n) From Hoeffding's inequality [13,Theorem 2], it follows that where M > 0 is chosen so that |g| ≤ M . Since x n ∈ T (n) U (µ), one can easily verify that Therefore, The above inequality holds for any x n ∈ T (n) U (µ), proving the theorem. A similar result for general typicality criteria is also true:

Theorem III.8 (Conditional typicality lemma).
Let µ ∈ ∆(X) and κ ∈ K(X; Y ). Then, for any µκ-typicality criterion V and δ ∈ (0, 1), there exists a µ-typicality December 15, 2014 DRAFT Proof: As in the proof of the previous theorem, we may assume that V = (g; ǫ; K) for some g ∈ L 1 (µκ), ǫ > 0, and a µκ-null set K. We use a truncation argument; for each k ∈ Z + , define then from Lebesgue dominated convergence theorem [8], we know that g k → g in L 1 (µκ) and h k → 0 in Let V k := g k ; ǫ 3 ; K , then from Theorem III.7, we know that for any given x n ∈ T (n) U (µ). On the other hand, define thus we can deduce by Chevychev's inequality [8].
if test functions satisfy some finite moment conditions. In Chapter 6, an argument of this kind is stated in detail.
2) We have seen in Chapter 2 that, if (x n , y n ) are jointly typical for some y n , then x n should be typical.
Conditional typicality lemma can be seen as a kind of converse to this. Now, a conditional version of the divergence lemma also can be proved by using this conditional typicality lemma instead of the asymptotic equipartition property. Up to here, we did not impose any assumptions on measurable spaces; therefore, all theorems we have stated are true for arbitrary alphabets (that is, arbitrary measurable spaces).
However, the proof given here of the following theorem relies on a lemma (see Lemma A.1) which uses the assumption that (Y, B) is countably-generated; that is, there exists a countable subset G of B so that B is the smallest σ-algebra containing G . Hence, from now on we assume that (Y, B) is countably-generated. Except the lemma, the whole procedure of the proof is similar to that of Theorem III.2.

1)
If D(µκ µλ) is finite, then for any ǫ > 0, there is a µκ-typicality criterion V 0 such that for any µκ-typicality for all n, and there exists a µ-typicality criterion U (depending on V) so that for all sufficiently large n.
2) If µκ ≪ µλ, then there is a µκ-typicality criterion V 0 such that for any µκ-typicality criterion for all n.

4)
If D(µκ µλ) = −∞, then for any M ≥ 0, there is a µκ-typicality criterion V 0 such that for any µκ-typicality for all sufficiently large n.
For the special case when λ is identically the counting measure (the Lebesgue measure, respectively), one can conclude that a typical cardinality (volume, respectively) of a conditional typical set is approximately the exponential of the conditional entropy (conditional differential entropy, respectively). Many other statements about the size of typical sets are also simple corollaries of this lemma. Proof: Thus, we get for all x n ∈ X n , for all n. Note that if x n / ∈ (X \N ) n , then the inequality trivially holds, because T For the second part of the theorem, note that from the conditional typicality lemma, we get a µ-typicality for any sufficiently large n. Since we know for every x n ∈ X n , it follows that for sufficiently large n, for all x n ∈ T (n) U (µ). Take n large enough to satisfy ǫ ′ + 1 n log 1 1−δ < ǫ, then we get for all x n ∈ T (n) Also, f + k k∈Z + is an increasing sequence of nonnegative measurable functions converging pointwise to (log g) + µκ-almost everywhere. So by monotone convergence theorem, we get f k dµκ → log g dµκ = +∞ as k → ∞ by considering positive parts and negative parts separately. Take k ∈ Z + so that for (x n , y n ) ∈ T (n) V (µκ), so for that case we have Proceeding as the same as the first part of the case 1, we get the result. 4) Choose g = dµκ dµλ , and take N as the case 1. For each k ∈ Z + , define a measurable function f k on X × Y as is an increasing sequence of nonnegative measurable functions converging pointwise to (log g) − µκ-almost everywhere. So by monotone convergence theorem, we get f k dµκ → log g dµκ = −∞ as k → ∞ by considering positive parts and negative parts separately.
for (x n , y n ) ∈ T (n) V (µκ), so for that case we have Proceeding as the same as the second part of the case 1, we get the result.

IV. PACKING AND COVERING LEMMAS
In this section, we will prove some fundamental tools to be used for various achievability proofs. Let (X, A X ), (Y, A Y ), and (Z, A Z ) be standard Borel spaces, and let µ XY Z ∈ ∆(X × Y × Z). Define µ X to denote the pushforward of µ XY Z onto X under the projection (which is, the marginal distribution on X), and similarly define µ XY and µ XZ . Since we are dealing with standard Borel spaces, there exist a probability kernel κ Y |X ∈ K(X; Y ) such that µ XY = µ X κ Y |X , and similarly κ Z|X , κ Y |XZ , and κ Z|XY [14,Chapter 5]. If x, y, z are random variables taking values in X, Y , and Z, respectively, with the joint distribution µ XY Z , then one can think of the Kullback- as the conditional mutual information I(y; z|x) (in the expression µ XY κ Z|X , κ Z|X is treated as a kernel from . For a general definition of conditional mutual information for arbitrary alphabets, see [15]. Then the following theorem is just a specialized result of the conditional divergence lemma: Theorem IV.1 (Joint typicality lemma).
1) If I(y; z|x) < ∞, then for any ǫ > 0, there is a µ XY Z -typicality criterion W 0 such that for any µ XY Z -typicality for all n, and there exists a µ XY -typicality criterion V (depending on W) such that for all sufficiently large n.

Remark IV.2.
By symmetry, the same theorem holds when the role of Y and Z are interchanged.
This theorem is a generalization of the theorem with the same name found in [3, p.29]. Since packing lemma, covering lemma, and "mutual versions" of these lemmas in [3] are all basically derived from joint typicality lemma, it follows that almost the same proof procedure is also valid in the generalized setting. Proofs of these generalizations that are directly following those in [3] are given from now on. We will often use abstract conditional expectations in the proofs; details about abstract conditional expectations can be found in [10]. We will denote a conditional expectation of a real-valued random variable w with respect to the σ-algebra generated by another random variable x as E[w|x]; here, x inside the bracket does not mean the value of x but the mapping x itself. Let us define the following terminology: Let κ ∈ K(X; Y ) and y be a random variable taking values in Y . Then we say y follows a conditional distribution κ given x for another random variable x taking values in X, if (x, y) * Pr = (x * Pr) ⋊ κ. In that case, we write Now we state and prove the main theorems of this section: Theorem IV.4 (Packing lemma).
Let R ≥ 0 be a nonnegative real number such that R < I(y; z|x). Then, there exists a µ XY Z -typicality criterion W 0 and a positive number c > 0 such that, for any µ XY Z -typicality criterion W ≤ W 0 , we have the following for all n ∈ Z + : Let I n be a finite set with |I n | ≤ 2 nR . Let (x n , y n ) be a random variable taking values in X n × Y n , and for each m ∈ I n , let z n (m) be a random variable taking values in Z n . Assume that each z n (m) follows a conditional distribution κ n Z|X given (x n , y n ). Then, Proof: Assume first that I(y; z|x) < ∞. Choose ǫ > 0 with R < I(y; z|x) − ǫ, and take W 0 obtained from the joint typicality lemma. Fix n ∈ Z + and an µ XY Z -typicality criterion W ≤ W 0 . Take x n , y n , I n , z n (m)'s as above, then for given m ∈ I n , by the joint typicality lemma, The case I(y; z|x) = ∞ also can be proved similarly.
Clearly, we can get the same conclusion (with a minor modification of "for all n" to "for all sufficiently large n") when |I n | ≤ f (n)2 nR for a fixed function f such that lim n → ∞ f (n)2 −δn = 0 for all δ > 0.

Theorem IV.5 (Covering lemma).
Let R ≥ 0 be a nonnegative real number such that R > I(y; z|x). Then, there exists a µ XY Z -typicality criterion W 0 and a positive number c > 0 such that, for any µ XY Z -typicality criterion W ≤ W 0 , there exists a µ XY -typicality criterion V so that we have the following for all sufficiently large n ∈ Z + : Let I n be a finite set with |I n | ≥ 2 nR . Let (x n , y n ) be a random variable taking values in X n × Y n , and for each m ∈ I n , let z n (m) be a random variable taking values in Z n . Assume that for m, m ′ ∈ I n with m = m ′ , (z n (m), z n (m ′ )) follows a conditional distribution κ n Z|X × κ n Z|X given (x n , y n ). Then we have Proof: From the assumption, it should be the case that I(y; z|x) < ∞ and R > 0. Choose ǫ > 0 with R > I(y; z|x) + ǫ, and by using the joint typicality lemma, take a µ XY Z -typicality criterion W 0 such that for any µ XY Z -typicality criterion W ≤ W 0 , there exists a µ XY -typicality criterion V so that for all (x n , y n ) ∈ T (n) V (µ XY ), whenever n ≥ n 0 for some n 0 ∈ Z + .
December 15, 2014 DRAFT Fix W ≤ W 0 and find such a V and n 0 . Let n ≥ n 0 , and take x n , y n , I n , z n (m)'s as above. For each m ∈ I n , define e(m) to be the indicator random variable of the event Note that p 1 , p 2 are measurable functions. Then, almost surely, for m, m ′ ∈ I n with m = m ′ . By Chevyshev's inequality, ≤ |I n |p 1 (x n , y n ) + |I n | 2 p 2 (x n , y n ) almost surely, thus Pr(N = 0|x n , y n ) ≤ 1 |I n |p 1 (x n , y n ) ≤ 2 −nR p 1 (x n , y n ) almost surely. Note that Pr (N = 0|x n , y n ) d Pr Let R 1 , R 2 ≥ 0 be nonnegative real numbers such that R 1 + R 2 < I(y; z|x). Then, there exists a µ XY Z -typicality criterion W 0 and a positive number c > 0 such that, for any µ XY Z -typicality criterion W ≤ W 0 , we have the following for all n ∈ Z + : Let I n , J n be a finite sets with |I n | ≤ 2 nR1 and |J n | ≤ 2 nR2 . Let x n be a random variable taking values in X n , and for each m 1 ∈ I n and m 2 ∈ J n , let y n (m 1 ) and z n (m 2 ) be random variables taking values in Y n and Z n , respectively. Assume that for each m 1 ∈ I n and m 2 ∈ J n , (y n (m 1 ), z n (m 2 )) follows a conditional distribution κ n Y |X × κ n Z|X given x n . Then, Proof: Assume first that I(y; z|x) < ∞. Choose ǫ > 0 with R 1 + R 2 < I(y; z|x) − ǫ and take W 0 obtained from the joint typicality lemma. Fix n ∈ Z + and a µ XY Z -typicality criterion W ≤ W 0 . Take x n , I n , y n (m 1 )'s, J n , z n (m 2 )'s as above, then for given m 1 ∈ I n and m 2 ∈ J n , by the joint typicality lemma, Pr (x n , y n (m 1 ), z n (m 2 ))) ∈ T (n) Pr (x n , y n (m 1 ), z n (m 2 )) ∈ T Pr (x n , y n (m 1 ), z n (m 2 )) ∈ T The case I(y; z|x) = ∞ also can be proved similarly.
Let R 1 , R 2 ≥ 0 be nonnegative real numbers such that R 1 + R 2 > I(y; z|x). Then, there exists a µ XY Z -typicality criterion W 0 and a positive number c > 0 such that, for any µ XY Z -typicality criterion W ≤ W 0 , there exists a µ X -typicality criterion U so that we have the following for all sufficiently large n ∈ Z + : Let I n , J n be finite sets with |I n | ≥ 2 nR1 and |J n | ≥ 2 nR2 . Let x n be a random variable taking values in X n , and for each m 1 ∈ I n and m 2 ∈ J n , let y n (m 1 ) and z n (m 2 ) be random variables taking values in Y n and Z n , respectively. Assume followings: 1) For each m 1 ∈ I n and m 2 ∈ J n , (y n (m 1 ), z n (m 2 )) follows a conditional distribution κ n Y |X × κ n Z|X given x n .

V. APPLICATIONS TO CODING PROBLEMS
In this section, some applications of the new typicality to coding problems are given. Derivations of many outer bounds do not rely on the alphabet size, excluding the cardinality-bound-part of auxiliary variables. In [15], a general definition of conditional mutual information for arbitrary alphabets is given, and some basic properties such as the chain rule are derived. Hence, outer bounds often can be extended to the general alphabet case with only some minor obstacles. On the other hand, derivations of inner bounds are often based on strong typicality, so the new notion of typicality makes possible for those inner bounds to be extended to the general alphabet case also.
These generalizations are quite straightforward; just replace usual strong typical sets appearing in the proofs with new typical sets.
However, still there are some technical subtleties remaining. First, quantities easily become infinite or even undefined, when alphabets are not finite. For example, the differential entropy may not be defined for a general real-valued random variable. Even when quantities are well-defined but becomes infinity, problems can happen when differences of such quantities are involved. Thus, sometimes a transfer procedure of a proof for the finite alphabet case to the general case is not completely transparent. Second, even when we can prove the same result for a coding theorem as in the finite alphabet case, numerical evaluation of the obtained region is rarely possible, because in general it is an infinite-dimensional optimization problem. Only for some special cases (such as additive Gaussian noise channel) this evaluation is computationally possible.
Despite of those subtleties, it is theoretically satisfactory that one does not need to pay much additional efforts on proving coding theorems for general alphabets. The point-to-point channel coding theorem and the point-to-point lossy source coding theorem are given as examples to explicitly show that there is essentially no additional thing required to prove coding theorems with infinite alphabets. Proofs given here basically follow those given in [3].
We will first describe precise mathematical formulations of those problems before proving them. One can see that there is almost no complicated assumptions about regularity to make the proofs mathematically rigorous.

A. Point-to-point channel coding theorem
Let (X, A ), (Y, B) be standard Borel spaces.

Definition V.1 (Memoryless channels).
A memoryless channel with a cost function is a quadruple (X, Y, κ, t), where κ ∈ K(X; Y ) and t : X → [0, ∞] is a measurable function. Here, X is called the input alphabet, Y is called the output alphabet, κ is called the channel transition kernel, and t is called the cost function. where I(µ, κ) is defined as D (µκ µ × κ * µ); see Remark III.4.

1) Define
then it is clear that C i (B) = 0 if B < B min . Also, for that case (R, B) is never achievable for any R. Hence, 2) On the other hand, when B ≥ B min , (0, B) is always achievable; choose x 0 ∈ X such that B min ≤ t(x 0 ) < B + ǫ, and consider the encoder f : m → x 0 .

Example V.3.
In some literatures such as [3], achievability of a rate is defined in terms of codes satisfying cost constraint B, not B + ǫ as in ours. This difference is just a minor issue, since two different operational capacity-cost functions arising from different definitions of achievability indeed coincide on (B min , ∞]. However, at B = B min , the capacity-cost function defined in terms of codes satisfying average cost constraint B (which will be denoted as C ′ o ) may not be lower-semicontinuous in general. For example, let X = Y = R and κ(x) = d x , t(x) = x 2 for each x ∈ X. This is the noiseless channel with real alphabet and quadratic cost function. Then one can easily verify that C We call a function f : , respectively) for all x, y ∈ I and λ ∈ [0, 1].
1) Since C i is increasing, the limit on the right-hand side always exists. by Fano's inequality, so

2) Note that
Since C i is increasing and concave on [B min , ∞], be given, so that R < C i (B + ǫ) whenever ǫ > 0 is sufficiently small. Take any such ǫ > 0.
Note that for both of the cases, t (n) (x n ) ≤ B + ǫ whenever x n ∈ T for each m ∈ [1 : 2 nR ], so we may assume that the message is chosen to be 1; that is, where y n is the received sequence when the message is chosen to be 1. . Since x n (m) and y n are independent when m = 1, by the assumption on V, we know that Pr(E 2 ) ≤ 2 −cn . On the other hand, also can be made sufficiently small when n is large, by the asymptotic equipartition property. Therefore, we can take n sufficiently large to make P av e ≤ ǫ. Hence, there exists ω such that the (n, ⌈2 nR ⌉)-channel code (f ω , g ω ) (which is shown to satisfy average cost constraint B + ǫ) having the property log⌈2 nR ⌉ n ≥ R and P e (f ω , g ω ) ≤ ǫ.
Since ǫ > 0 can be taken to be arbitrarily small, (R, B) is achievable. Therefore, C o (B) ≥ C + i (B).

B. Point-to-point lossy source coding theorem
Let (X, A ), (Y, B) be standard Borel spaces.

Definition V.7 (Memoryless sources).
A memoryless source with a distortion function is a quadruple (X, Y, µ, t), where µ ∈ ∆(X) and t : X×Y is a measurable function. Here, X is called the source alphabet, Y is called the reconstruction alphabet, µ is called the source probability measure, and t is called the distortion function. We always assume that D max := The infimum of ∅ is defined to be ∞. On the other hand, the information rate-distortion function is defined as Remark V.8.

1) Define
then it is clear that R i (D) = ∞ if D < D min . Also, for that case (R, D) is never achievable for any R: for any encoder f and decoder g, where g = (g 1 , · · · , g n ) by Tonelli's theorem [12,Chapter 4]. Define κ i (x i ) as Hence, for D < D min , we have R o (D) = R i (D) = ∞. . We may assume that R i (D 1 ) and R i (D 2 ) are both finite, since the result is trivial when one of them is infinite. Let ǫ > 0 be given and choose κ 1 , and D = λD 1 + (1 − λ)D 2 , then t dµκ = λ t dµκ 1 + (1 − λ) t dµκ 2 ≤ D, and due to convexity of the function Since ǫ > 0 is arbitrary, it follows that Therefore, we get convexity.

Remark V.12.
Since R i is decreasing, the limit on the right-hand side always exists. Proof of converse (R o ≥ R + i ): Assume that (R, D) is achievable for some R ∈ [0, ∞). Then for given ǫ ∈ (0, 1), there exists an (n, M )-source code (f, g) such that Construct a random variable x n following the distribution µ n and define m := f (x n ), y n := g(m). We proceed just as the case of discrete memoryless source: Since R i is decreasing and convex on [D min , ∞], Then since ǫ ∈ (0, 1) is arbitrary, . Let R > R + i (D) be given, so that R > R i (D + ǫ 4 ) whenever ǫ > 0 is sufficiently small. Take any such ǫ > 0.
(Analysis of expected distortion) Let x n be the random variable representing the input to the encoder which is independent to y n (m)'s, and let f , g be the encoder and the decoder corresponding to y n (m)'s. Let y n be the reconstructed codeword g(f (x n )). Define the following error events: Since x n and y n (m)'s are independent, by the assumption on U and V, we know that Pr(E 2 ) ≤ 2 −cn provided that n is sufficiently large. Together with the asymptotic equipartition property applied to µ, it follows that provided that n is sufficiently large. Therefore, Hence, there exists ω such that the (n, ⌊2 nR ⌋)-code (f ω , g ω ) satisfies Since ǫ > 0 can be taken to be arbitrarily small,

VI. MARKOV LEMMA
Along with conditional typicality lemma, joint typicality lemma, and packing and covering lemmas, there is another fundamental lemma used for derivations of inner bounds, called Markov lemma. It says that whenever we have a Markov chain y − x − z, joint typicality of (x n , y n ) together with joint typicality of (x n , z n ) implies joint typicality of (x n , y n , z n ) with high probability. The important difference from conditional typicality lemma is that z n does not need to be conditionally i.i.d. given (x n , y n ). Markov lemma does not seem to be obtained in our setting with its full generality yet; however, it becomes a simple corollary of the bounded conditional typicality lemma when involved test functions are bounded. This includes the finite alphabet case as a special case since any integrable function on a finite measurable space should be bounded almost everywhere.
Let Let µ ∈ ∆(X), κ ∈ K(X; Y ), and λ ∈ K(X; Z). For each n ∈ Z + and a µλ-typicality criterion S, let λ (n) S ∈ K(X n ; Z n ). Assume that, for any ǫ > 0, there exist a µλ-typicality criterion S 0 so that for any µλ-typicality criterion S ≤ S 0 , one can find a µ-typicality criterion U, satisfying λ (n) for all x n ∈ T (n) U (µ) and a measurable subset E of T (n) S (µλ|x n ), whenever n is sufficiently large. Then for any µ(κ × λ)-bounded typicality criterion W, there exists a µλ-typicality criterion S 0 and a positive number c > 0 such that, for any µλ-typicality criterion S ≤ S 0 , there exists a µκ-typicality criterion V so that for all sufficiently large n.
To avoid potential confusion, the dependency relation in the condition is written here formally: ∀ǫ; ∃S 0 ; ∀S ≤ S 0 ; ∃U; ∃n 0 ; ∀n ≥ n 0 ; ∀x n ∈ T (n) where some restrictions on the domains of variables are understood implicitly.
Proof: Let W be a µ(κ × λ)-bounded typicality criterion. Then we can find a µκ-typicality criterion V 1 and a positive number c 1 > 0 such that for all n ∈ Z + larger than some n 1 ∈ Z + by applying the bounded conditional typicality lemma. Next, pick any ǫ ∈ (0, c 1 ) and apply the assumption on λ (n) S 's to get a µλ-typicality criterion S 0 . Let c := c 1 − ǫ. Now, choose any µλ-typicality criterion S ≤ S 0 . Then there exists a µ-typicality criterion U so that for all x n ∈ T (n) U (µ) and a measurable subset E of T (n) S (µλ|x n ), whenever n is sufficiently large, say, larger than some n 0 ∈ Z + . Choose a µκ-typicality criterion V ≤ V 1 such that (x n , y n ) ∈ T Note that, in the proof above, rather than Markovity (which is, the fact that λ and λ (n) S are only functions of x n , not y n ), exponential decay of the probability of error was the crucial concern, which is a result of boundedness of test functions. Unfortunately, we do not have this property for general integrable test functions, so validity of the theorem for that case is still not clear. As noted in Chapter 1, boundedness is quite a strong condition. The theorem cannot be applied directly to even the simplest case with Gaussian measures and quadratic functions, because quadratic functions are not bounded. Therefore, it is highly desired to extend the theorem to more general situations.
The definition above seems quite artificial, but it appears naturally when one tries to make an exponential decay of error probability in conditional typicality lemma. Also, note that when pointwise values of κ are Gaussian where variances are uniformly bounded, a function of at most quadratic order will become a log-exponential test function.
One can easily see by using Jensen's inequality that an exponentially integrable function is always log-exponential with respect to any decomposition of the measure into a marginal and a corresponding conditional distribution (a function f is exponentially integrable, if 2 δ|f | is integrable for some δ > 0). A sum of a log-exponential function and a bounded measurable function is again log-exponential. Now we extend the bounded conditional typicality lemma in terms of log-exponential typical sets:

Theorem VI.3 (Log-exponential conditional typicality lemma).
Let µ ∈ ∆(X) and κ ∈ K(X; Y ). Then for any µκ-typicality criterion V log-exponential with respect to (µ, κ), there exists a µ-typicality criterion U and a positive number c > 0 such that for all sufficiently large n ∈ Z + .
Proof: We may assume that V = (g; ǫ; K) as usual. Find a positive real number δ > 0 such that For each k ∈ Z + , define the truncation g k : X × Y → R as , and also define a measurable function h k : X → R as then the Lebesgue dominated convergence theorem guarantees that we can choose k ∈ Z + such that Let V k := g k ; ǫ 3 ; K , then there exists a bounded µ-typicality criterion U k and a positive real number c 1 > 0 such that for sufficiently large n ∈ Z + by applying the bounded conditional typicality lemma. Define U := U k ∧ h k ; ǫδ 12 ; ∅ . Now, fix n ∈ Z + large enough so that the above inequality holds, and let x n ∈ T (n) U (µ). Consider the set then clearly Z is contained in so by Chevychev's inequality, .
so it follows that κ n (Z|x n ) ≤ 2 − ǫδ 6 n . Note that if y n ∈ T (n) Therefore, we get for all x n ∈ T (n) U (µ) provided that n is sufficiently large. By using the log-exponential conditional typicality lemma instead of the bounded conditional typicality lemma in the proof of Theorem VI.1, we get the following: Corollary VI.4 (Log-exponential Markov lemma).
Theorem VI.1 is still true when W is log-exponential with respect to (µκ, λ).
From Jensen's inequality, one can easily see that a test function is log-exponential with respect to (µκ, λ) if it is log-exponential with respect to (µ, κ × λ).

VII. THE GAUSSIAN CASE
Most of results about typical sets given in this paper were just described in terms of existence of typical sets satisfying some properties. It was not necessary to be careful about the actual contents in the typicality criteria.
Unfortunately, to apply the log-exponential Markov lemma, we should keep track the list of test functions inside the given typicality criteria, because we have to know whether or not those functions are log-exponential. The aim of this section is to establish a claim saying that we still do not need to care about those things when everything is Gaussian. As discussed in the previous section, a function of at most quadratic order is log-exponential with respect to Gaussian measures. What we will show here is that indeed functions of at most quadratic order are sufficient to build the whole theory when every measure is Gaussian.
The main motivation of this is the fact that the test function which appears in the proof of the joint typicality lemma was the logarithm of a Radon-Nikodym derivative; when measures are Gaussian, this function may become a quadratic function. To be precise, let us formalize our discussions. We will consider (possibly singular) Gaussian measures on Euclidean spaces. Let us denote the Gaussian measure on R d of mean m and (possibly singular) covariance matrix Σ as N d (m, Σ). We review some simple facts about Gaussian measures: 1) Let µ ∈ ∆(R d1 ) and κ ∈ K(R d1 ; R d2 ). Then µκ is a Gaussian measure on R d1+d2 , if and only if, µ is a Gaussian measure on R d1 and κ : x → N d2 (Ax + b, Λ) for some d 2 × d 1 matrix A and a vector b ∈ R d2 , and a d 2 × d 2 positive-semidefinite matrix Λ [16].
2) Any Gaussian measure on R d1 is an affine transformation of the standard Gaussian measure N d2 (0, I) (here, I is the d 2 × d 2 identity matrix) where d 2 is the rank of the covariance matrix. To see why, let µ = N d1 (m, Σ) and let d 2 be the rank of Σ. Since Σ is symmetric, it is orthogonally diagonalizable [17, p.247]; hence, we can write Σ = P T DP for some orthogonal matrix P and a diagonal matrix D. We may assume that D = 3) If µ, ν are Gaussian measures on R d1 and µ ≪ ν, then µ and ν should have the same support. To see why, first find an affine map T : R d2 → R d1 sending the standard Gaussian meaure to ν, then from this it is clear that the support of ν is the affine subspace T [R d2 ] of R d1 . Then since ν ≪ T * m where m is the Lebesgue measure on R d2 , it follows that µ ≪ T * m, so the support of µ is contained in is an affine isomorphism, we can think of the pushforward (T −1 ) * µ. This is a Gaussian measure on R d2 which is absolutely continuous with respect to the Lebesgue measure; hence, it should be non-singular. Thus, in fact, ν ≪ µ as well. We can also compute the Radon-Nikodym derivative dµ dν : let µ ′ := (T −1 ) * µ and ν ′ :

4) The product of Gaussian measures is Gaussian
We first formally define functions of quadratic order as functions which grow not faster than sum of a constant with the norm-square function.

Definition VII.1 (Quadratic typical sets).
Let µ ∈ ∆(R d ). A µ-integrable function f : R d → R is said to be µ-quadratic, if there exists a µ-null set N and a constant M ≥ 0 such that |f (x)| ≤ M (1 + x 2 ) whenever x ∈ R d \ N . A µ-typicality criterion U is said to be a µ-quadratic typicality criterion, if each test function in U is µ-quadratic. A µ-typical set with respect to a µ-quadratic typicality criterion is called a µ-quadratic typical set.
The pullback of a quadratic typicality criteria under an affine map is again quadratic.
Hence for a T * µ-quadratic typicality criterion V, the pullback T * V is a µ-quadratic typicality criterion.
Proof: Take a T * µ-null set K and a constant M 1 ≥ 0 such that |g(y)| ≤ M 1 (1 + y 2 ). Clearly, We prove that any quadratic test function is indeed log-exponential with respect to a Gaussian measure. In fact, it is even exponentially integrable.

Lemma VII.3.
Let µ be a Gaussian measure on R d and f : R d → R a µ-quadratic function. Then, f is exponentially integrable with respect to µ.
Proof: Let T : R d ′ → R d be an affine map sending the standard Gaussian measure λ := N d ′ (0, I) to µ.
Since f is µ-quadratic, f • T is λ-quadratic, so there exists a λ-null set N and a constant M ≥ 0 such that . From now on, we prove that all the results derived in Section III, Section IV, and Section VI can be written in terms of quadratic typical sets when all the involved measures are jointly Gaussian.
Proof: Since bounded functions are clearly µ-quadratic, we only need to check that the function appearing in the proof of Theorem VI.3 is µ-quadratic when we have chosen δ > 0 sufficiently small. First, find For each x ∈ R d1 , define K x := y ∈ R d2 : (x, y) ∈ K , then there exists a µ-null set N so Since µ and κ are jointly Gaussian, we can write κ(x) = N d2 (Ax + b, Λ) for each x ∈ R d1 . Therefore, there is a linear map B : R d → R d2 such that the affine map T x : z → Bz + Ax + b maps the standard Gaussian measure λ := N d (0, I) to κ(x), where d is the rank of Λ. Note that d, A, B, b does not depend on x. Hence, we can write Since λ is the standard Gaussian measure, one can show by direct computation that whenever δ > 0 is sufficiently small, we have A precise upper bound on δ only depends on B and M , so it follows that for some constant C ≥ 0, whenever x ∈ R d \ N . Therefore, h k is µ-quadratic.
In the statement of the conditional divergence lemma, let X = R d1 , Y = R d2 , and both µκ and µλ be Gaussian.
Then D(µκ µλ) always exists and nonnegative, and D(µκ µλ) = ∞ if and only if µκ ≪ µλ. Also, V 0 in the statement can be found as a µκ-quadratic typicality criterion for all cases. Furthermore, for the case when D(µκ µλ) is finite, U, which depends on V, can be also found to be µ-quadratic whenever V is a µκ-quadratic typicality criterion.
Proof: It is trivial that D(µκ µλ) always exists and nonnegative, since both µκ and µλ are probability measures.

1) (For D(µκ µλ) < ∞)
The only test function involved in V 0 in the proof of the conditional divergence lemma is log dµκ dµλ . We show that this is a µκ-quadratic function. As remarked before, there is an affine map T : R d → R d1+d2 sending a Gaussian measure N d (m, Σ) to µκ and sending the standard Gaussian measure N d (0, I) to µλ, and , then K is a µκ-null set, and write T −1 : so log dµκ dµλ is clearly µκ-quadratic. Therefore, V 0 can be chosen to be µκ-quadratic. To show the claim about U, note that in the proof of the conditional divergence lemma, U can be taken to be µ-quadratic by applying the Gaussian conditional typicality lemma instead of the usual conditional typicality lemma, whenever V is given to be µκ-quadratic.
2) (For µκ ≪ µλ) The test function chosen in the proof of the conditional divergence lemma is a bounded function, so the conclusion is trivial.
Since joint typicality lemma is just a specialization of conditional divergence lemma, it can be also stated in terms of quadratic typical sets. Packing and covering lemmas (as well as their "mutual versions") are consequences of conditional typicality lemma and joint typicality lemma, so they also can be stated in terms of quadratic typical sets. Now Markov lemma is the only remaining: Theorem VII.6 (Gaussian Markov lemma).
Let µ ∈ ∆(R d1 ), κ ∈ K(R d1 ; R d2 ), and λ ∈ K(R d1 ; R d3 ) so that both µκ and µλ are Gaussian. For each n ∈ Z + and a µλ-quadratic typicality criterion S, let λ (n) S ∈ K(R d1n ; R d3n ) (which is not necessarily Gaussian). Assume that, for any ǫ > 0, there exists a µλ-quadratic typicality criterion S 0 so that for any µλ-quadratic typicality criterion S ≤ S 0 , one can find a µ-quadratic typicality criterion U, satisfying for all x n ∈ T   It is now clear that there should be no problem to directly apply the same derivation of an inner bound of a given discrete memoryless coding problem relying on those fundamental lemmas to the corresponding Gaussian memoryless coding problem. However, this does not mean that we have the same formula for an achievable region.
For example, consider the quadratic Gaussian distributed source coding problem [18]: we have a jointly Gaussian random sources x 1 , x 2 , which are encoded separately at rates R 1 , R 2 , respectively, and then decoded jointly. The distortion criteria is given as whilex n 1 andx n 2 are reconstructions of x n 1 and x n 2 at the decoder, respectively. Here, the theory of quadratic typical sets does not immediately give the following Berger-Tung inner bound [19] [20]: for some auxiliary random variables u 1 , u 2 satisfying the Markov chain u 1 −x 1 −x 2 −u 2 and measurable functionŝ What we can say immediately using the theory of quadratic typical sets is that, the above inner bound holds when the joint distribution of (x 1 , x 2 , u 1 , u 2 ,x 1 (u 1 , u 2 ),x 2 (u 1 , u 2 )) is Gaussian. That is, all variables including not only the variables stated in the problem but also auxiliary variables, should have a jointly Gaussian distribution. For the case of quadratic Gaussian distributed source coding problem, the optimal choice of auxiliary variables are indeed Gaussian [21], but one cannot be sure that this will always be the case for other problems. Yet, when Markov lemma was not necessary, we can apply the theory of general typical sets rather than quadratic typical sets so such restriction need not to be concerned.

VIII. SOME REMARKS ON SOURCES WITH MEMORY
We have discussed a generalization of strong typicality which can be applied to a wide range of sources without memory. Perhaps, it is possible to extend the concept of typical sets to sources with memory. Such an extension will enable generalization of many results about memoryless problems into problems containing sources or channels with memory. It is not certain whether such generalizations are useful in practice or not, because the obtained results will be multi-letter characterizations; however, finding the "ultimate" definition of typical sets which can be applied to a very large range of sources is theoretically appealing. The idea of the extension will be the same: consider a finite collection of test functions. However, it is not obvious to say what are test functions. The Shannon- McMillan-Breiman theorem [22] and its extension to random sequences of continuous variables [23] suggests that it is natural to define weak typical sets of a stationary ergodic stochastic process x := (x k ) k∈Z with well-defined joint densities as where p n is the joint pdf of (x i ) is the differential entropy rate. Taking this as a motivating example, we can conclude that, rather than to consider a single test function, we should consider a sequence of test functions for sources with memory.
For a memoryless source, we have defined typical sets with respect to only the marginal probability distribution.
For a source with memory (that is, a random sequence), we should deal with the whole probability distribution on the space of sequences of symbols. This space can be viewed as a single probability space endowed with a measurable self-map called the shift map, representing the flow of time. One may argue that this dynamical system is "the essence" of the random sequence, so it seems natural that we should think of the definition of typical sets that can be given for general dynamical systems.
Let us restrict ourselves to consider only invertible ergodic measure-preserving dynamical systems [24] (for example, bidirectional stationary ergodic random sequences). In the motivating example, we can write 1 n log p n (x 0 , · · · , x n−1 ) = 1 n n−1 i=0 log p i (x i |x 0 , · · · , x i−1 ) where p i (x i |x 0 , · · · , x i−1 ) is the conditional pdf of x i given (x 0 , · · · , x i−1 ). If we define f i (x k ) k∈Z := log p i (x 0 |x −1 , x −2 , · · · , x −i+1 ) for each i, then 1 n log p n (x 0 , · · · , x n−1 ) = 1 n is the shift map. Note also that Therefore, the weak typical set is the projection onto R n of the following set: Thus, a typical set for an invertible ergodic measure-preserving dynamical system (X, A , µ, T ) may look like T (n) U (µ, T ) := x ∈ X \ N : where N is a µ-null set, F is a finite collection of "test sequences" (f i ) ∞ i=0 of measurable functions on X, and U = (F ; ǫ; N ). A test sequence may not be an arbitrary sequence of measurable functions, and there should be some conditions to be satisfied. The following generalization of the Birkhoff's ergodic theorem given in [22] suggests a possible class of test sequences: Theorem VIII.1 (Breiman, 1957).
Let (X, A , µ, T ) be an ergodic measure-preserving dynamical system. Let (f i ) ∞ i=0 be a sequence of measurable functions on X such that sup i |f i | dµ < ∞ that is convergent µ-almost everywhere to some function f . Then, This theorem gives a sort of asymptotic equipartition property. According to [23], some results discussed in this paper (for example, the divergence lemma) are expected to be generalized to the case of stationary ergodic sources (in fact, as depicted in [23], Theorem VIII.1 can be stated for possibly non-ergodic stationary sources in terms of conditional expectations, so it is possible to think of an even more general case of such sources). However, the situation is more complicated than the memoryless case, because the Hoeffding's inequality does not hold in general for dependent random variables. There are some generalizations of the Hoeffding's inequality, such as the Azuma's inequality [25], but it is still not clear that what restrictions on the class of test sequences lead us to the most natural definition of typical sets for sources with memory.

IX. CONCLUSION
A new notion of typical sets for a general class of memoryless sources was defined, which properly generalizes the conventional notion of strong typical sets. It turns out that the weak typicality is also a special case of the proposed notion. The definition is based on an observation that typical average lemma is the one validating most of useful properties of strong typical sets. Some similar approaches already exist, including [4] and [5], but the new notion will be more appropriate for network information theory in the sense that, many technical lemmas, including conditional typicality lemma, joint typicality lemma, and packing and covering lemmas, can be easily generalized in a completely rigorous manner. Together with Markov lemma introduced in [19] and [20], these lemmas have been the main tools for deriving inner bounds of many multi-terminal coding problems. It was explicitly shown that some classical coding theorems can be generalized in a straightforward way only with very little technical assumptions. On the other hand, Markov lemma also has been generalized in restrictive ways, but this limitation causes no problem especially when the joint probability distribution is Gaussian and every involved test function is at most of quadratic order. However, still more improvements are desired to get a better theory. Also, there may be a notion of typicality generalizing the introduced notion further to include sources with memory, but this task is not seem to be simple.

ACKNOWLEDGMENT
This work was supported by MSIP as GFP/(CISS-2012M3A6A6054195). The author would like to thank Prof.
Sae-Young Chung for his guidance and useful discussions with him. The author also would like to thank Seung uk Jang for his careful verification of statements and proofs. Suggestion of the terminology "test functions" of an anonymous reviewer is appreciated as well.

APPENDIX
Here, several folklore lemmas are collected.

Lemma A.1.
Let (X, A ) be a measurable space and (Y, B) be a countably-generated measurable space. Let µ ∈ ∆(X) and κ : X → ∆(Y ) be a probability kernel. Let λ : X → P(Y ) be a σ-finite positive measure kernel with µκ ≪ µλ.
Fix a Radon-Nikodym derivative g = dµκ dµλ , then there exists a µ-null set N so that κ(x) ≪ λ(x) and g(x, ·) is a Radon-Nikodym derivative of κ(x) with respect to λ(x) for all x ∈ X \ N .
Proof: Let B 0 be the algebra generated by a countable generator of B. Then B 0 is countable. Fix B ∈ B 0 , then for any A ∈ A we have then we have proved that B 0 ⊆ C . We claim that C = B. Since B 0 is an algebra, it suffices to show that C is a monotone class, by the monotone class theorem [10, p.18]. Let (B k ) k∈Z + be an increasing sequence in C and B := k∈Z + B k , then it follows by monotone convergence theorem and countable-additivity of κ(x) that for all B ∈ B. Therefore, it follows that κ(x) ≪ λ(x) and g(x, ·) is a Radon-Nikodym derivative of κ(x) with respect to λ(x). Since B 0 is countable, N is a µ-null set. Hence, we get the conclusion.

Lemma A.2.
Let (X, A ) and (Y, B) be measurable spaces. Then, the function I : ∆(X) × K(X; Y ) → [0, ∞] defined as is concave in the first variable and convex in the second variable.
Since ǫ > 0 is arbitrary, concavity of I in the first variable is proved. To prove convexity in the second variable, = λI(µ, κ 1 ) + (1 − λ)I(µ, κ 2 ), thus convexity of I in the second variable is also proved.