{'fraction_non_alphanumeric': 0.041714069017823284, 'fraction_numerical': 0.015295158639868538, 'mean_word_length': 4.361741782446629, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Empirical and Strong Coordination via Soft Covering with Polar Codes

We design polar codes for empirical coordination and strong coordination in two-node networks. Our constructions hinge on the fact that polar codes enable explicit low complexity schemes for soft covering. We leverage this property to propose explicit and low-complexity coding schemes that achieve the capacity regions of both empirical coordination and strong coordination for sequences of actions taking value in an alphabet of prime cardinality. Our results improve previously known polar coding schemes, which (i) were restricted to uniform distributions and to actions obtained via binary symmetric channels for strong coordination, (ii) required a non-negligible amount of common randomness for empirical coordination, and (iii) assumed that the simulation of discrete memoryless channels could be perfectly implemented. As a by-product of our results, we obtain a polar coding scheme that achieves channel resolvability for an arbitrary discrete memoryless channel whose input alphabet has prime cardinality.


I. INTRODUCTION
The characterization of the information-theoretic limits of coordination in networks has recently been investigated, for instance, in [2]- [5]. The coordinated actions of nodes in the network are modeled by joint probability distributions, and the level of coordination is measured in terms of how well these joint distributions approximate a target joint distribution with respect to the variational distance. Two types of coordination have been introduced: empirical coordination, which requires the one dimensional empirical distribution of a sequence of n actions to approach a target distribution, and strong coordination, which requires the n dimensional distribution of a sequence of n actions to approach a target distribution. The concept of coordination sheds light into the fundamental limits of several problems, such as distributed control or task assignment in a network. Several extensions and applications have built upon the results of [3], including channel simulation [4], [5], multiterminal settings for empirical coordination [6] or strong coordination [7]- [9], empirical coordination for joint source-channel coding [10], and coordination for power control [11].
The design of practical and efficient coordination schemes approaching the fundamental limits predicted by information theory has, however, attracted little attention to date. One of the hurdles faced for code design is that the metric to optimize is not a probability of error but a variational distance between distributions. Notable exceptions are [12], [13], which have proposed coding schemes based on polar codes [14], [15] for a small subset of all two-node network coordination problems.
In this paper, we demonstrate the ability of polar codes to solve the issue of coding for channel resolvability. Building upon this, we significantly extend on the results in [12], [13] to provide an explicit and low-complexity alternative to the information-theoretic proof in [3] for two-node networks. More specifically, the contributions of this paper are as follows: • We propose an explicit polar coding scheme to achieve the channel resolvability of an arbitrary memoryless channel whose input alphabet has prime cardinality; low-complexity coding schemes have previously been proposed with polar codes in [13], invertible extractors in [16], and injective group homomorphisms in [17] but are all restricted to symmetric channels. Although [18] has proposed low-complexity coding schemes for arbitrary memoryless channels, the construction therein is non-explicit in the sense that only existence results through averaging are proved. • We propose an explicit polar coding scheme that achieves the entire empirical coordination capacity region for actions from an alphabet of prime cardinality, when common randomness, whose rate vanishes to zero as the blocklength grows, is available at the nodes. This construction extends [12], which only deals with uniform distributions and requires a non negligible rate of common randomness available at the nodes.
Our proposed constructions are explicit and handle asymmetric settings through block Markov encoding instead of relying, as in [19] and related works, on the existence of some maps or a non-negligible amount of shared randomness; we provide further discussion contrasting the present work with [19] in Remark 1.
The coding mechanism underlying our coding schemes is "soft covering", which refers to the ability to approximate output statistics using codebooks. In particular, soft covering with random codebooks has been used to study problems in classical information theory such as Wyner's common information [20], the resolvability of a channel [21], secrecy over wiretap channels [17], [22]- [25], strong coordination [3], channel synthesis [4], [5], covert communication [26], [27], as well as in quantum information theory [2], [28]- [30]; see Section III-A for additional details. In our coding schemes, soft covering with polar codes is obtained via the special case of soft covering over noiseless channels, and via an appropriate block Markov encoding to "recycle" common randomness.

Remark 1. [19,
Theorem 3] provides a polar coding scheme for asymmetric channels for which reliability holds on average over a random choice of the sequence of "frozen bits". Thus, it proves existence of a specific sequence of "frozen bits" that ensures reliability. [19, Section III-A] also provides an explicit construction, which, however, requires that encoder and decoder share a non-negligible amount of randomness as the blocklength grows.
To circumvent these issues, we use instead the technique of block-Markov encoding, which has been successfully applied to Wyner-Ziv coding in [31], [32], and to channel coding in [33], [32]. 1 Unlike problems that only involve reliability constraints, an additional difficulty of block Markov encoding for coordination is to ensure approximation of the target distribution jointly over all encoding blocks, despite potential inter-block dependencies.
The remainder of the paper is organized as follows. Section II provides the notation and Section III reviews the notion of resolvability and coordination. Section IV demonstrates the ability of polar codes to achieve channel resolvability. For a two-node network, Sections V and VI provide polar coding schemes that achieve the empirical coordination capacity region and the strong coordination capacity region, respectively. Finally, Section VII provides concluding remarks.

II. NOTATION
We let a, b be the set of integers between a and b . For n ∈ N, we let G n 1 0 1 1 ⊗n be the source polarization transform defined in [15]. The components of a vector X 1:N of size N are denoted with superscripts, i.e., X 1:N (X 1 , X 2 , . . . , X N ). For any set A ⊂ 1, N , we let X 1: be the components of X 1:N whose indices are in A. We let V(·, ·) and D(·||·) denote the variational distance and the Kullback-Leibler divergence, respectively, between two distributions. For joint probability distributions p XY and q XY defined over X × Y, we write the conditional Kullback-Leibler divergence as All logs are taken with respect to base 2. Finally, the indicator function is denoted by 1{ω}, which is equal to 1 if the predicate ω is true and 0 otherwise.

III. REVIEW OF RESOLVABILITY AND COORDINATION
We first review the definition of channel resolvability [21], which plays a key role in the analysis of strong coordination. We then review the related notion of source resolvability, which will relate to a building block of our proposed coding schemes. Finally, we review the definition of empirical and strong coordination in two-node networks as introduced in [3]. Observe that a characteristic of the problems reviewed is that they do not require a reconstruction algorithm to ensure a reliability condition, as it is the case, for instance, for source or channel coding, but requires, instead, a "good" approximation of given probability distributions.

A. Soft covering and Channel resolvability
Soft covering is concerned with the approximation theory of output statistics [21] and has first appeared in the analysis of the common information between random variables [20]. Channel resolvability [21] is the fundamental limit of soft-covering and can be understood as the minimal bit rate required to simulate a given process at the output of a channel. More specifically, consider a discrete memoryless channel (X , q Y |X , Y) and a memoryless source (X , q X ) with X and Y representing finite alphabets. Define the target distribution q Y as the output of the channel when the input distribution is q X as As depicted in Figure 1, the encoder wishes to form a sequence with the minimal amount of randomness such that the sequence sent over the channel (X , q Y |X , Y) produces an output Y 1:N , whose distribution A formal definition is given as follows.

consists of
• a randomization sequence S uniformly distributed over S 1, 2 N R ; • an encoding function f N : S → X N ; and operates as follows: • the encoder forms f N (S); • the encoder transmits f N (S) over the channel q Y 1:N |X 1: Definition 2. A rate R is achievable for an input distribution q X if there exists a sequence of (2 N R , N ) for the input distribution q X and ∀y 1:N ∈ Y N , p Y 1:N (y 1:N ) where p fN (S) denotes the probability distribution of the encoder output f N (S).
As summarized in Theorem 1, the infimum of achievable rates for any input distribution q X is called channel resolvability and has been characterized in [4], [17], [21], [26].

B. Source resolvability and conditional resolvability
Source resolvability corresponds to channel resolvability over a noiseless channel and thus characterizes the minimal rate of a uniformly distributed sequence required to simulate a source with given statistics.
We review here the slightly more general notion of conditional resolvability [35].
Consider a discrete memoryless source (X × Y, q XY ) with X and Y finite alphabets. As depicted in Figure 2, given N realizations of the memoryless source (Y, q Y ), the encoder wishes to form X 1:N with the minimal amount of randomness such that the joint distribution of ( X 1:N , Y 1:N ), denoted by p X 1:N Y 1:N , is close to q X 1:N Y 1:N N i=1 q XY . Note that the traditional definition of source resolvability [21] is recovered by setting Y = ∅. A formal definition is as follows.
Definition 3. A (2 N R , N ) code C N for a discrete memoryless source (X × Y, q XY ) consists of • a randomization sequence S uniformly distributed over S 1, 2 N R ; • an encoding function f N : S × Y N → X N ; and operates as follows: • the encoder observes N realizations Y 1:N of the memoryless source (Y, q Y ); • the encoder forms X 1:N f N (S, Y 1:N ).
The joint distribution of ( X 1:N , Y 1:N ) is denoted by p X 1:N Y 1:N . with p X 1:N Y 1:N the joint probability distribution of the encoder output X 1:N , and where Y 1:N is available at the encoder.
The infimum of achievable rates is called conditional resolvability and is characterized as follows [4], [35].

Remark 2.
In [35], conditional resolvability is described as the minimum randomness required to approximate a target conditional distribution representing a channel given a fixed input process. We prefer to approach conditional resolvability as an extension of source resolvability since the corresponding interpretation in terms of random number generation [21] and the special case Y = ∅ seem more natural in the context of our proofs. In the following, we use the term resolvability to designate conditional resolvability or source resolvability, when no confusion with channel resolvability is possible.
The task described in Definitions 3 and 4, is a random number generation that can be seen as performing soft covering over noiseless channels. Resolvability achieving random number generations will be the main building block of our coding schemes to emulate soft covering over noisy channels.

C. Coordination
Consider a memoryless source (X Y, q XY ) with X and Y finite alphabets, and two nodes, Node 1 and Node 2. As depicted in Figure 3, Node 1 observes a sequence of action X 1:N and sends a message M over a noiseless channel to Node 2. M must be constructed such that from M and some randomness C, pre-shared with Node 1, Node 2 can produce Y 1:N such that the joint distribution of ( X 1:N , Y 1:N ), A formal definition is as follows.
• common randomness C with rate R 0 shared by Node 1 and Node 2; • an encoding function f N : and operates as follows: • Node 1 observes X 1:N , N independent realizations of (X , q X ); • Node 1 transmits f N (X 1:N , C) to Node 2; , whose joint distribution with X 1:N is denoted by The notion of empirical and strong coordination are then defined as follows.
Definition 6. A rate pair (R, R 0 ) for a fixed joint distribution q XY is achievable for empirical coordi- where for a sequence (x 1:N , y 1:N ) generated at Nodes 1, 2, and for (x, y) ∈ X × Y, The closure of the set of achievable rates is called the empirical coordination capacity region.
The closure of the set of achievable rate pairs is called the strong coordination capacity region.
The capacity regions for empirical coordination and strong coordination have been fully characterized in [3].

Theorem 3 ([3]). The empirical coordination capacity region is
). The strong coordination capacity region is

IV. POLAR CODING FOR CHANNEL RESOLVABILITY
We propose in this section an explicit and low-complexity coding scheme to achieve channel resolvability. The key ideas that will also be used in our coding scheme for empirical and strong coordination are (i) resolvability achieving random number generation and (ii) randomness recycling through block Markov encoding.
Informally, our coding scheme operates over k ∈ N * encoding blocks of length N 2 n , n ∈ N * as follows. In the first block, given the randomness R 1 , we perform a resolvability achieving random number generation, i.e., we generate a random variable whose distribution is close to q X 1:N with R 1 close to H(X). When the produced random variable is sent over the channel q Y |X , the channel output distribution is close to q Y 1:N . Note that the amount of randomness used is non-optimal, since we are approximately "wasting" randomness with rate close to H(X|Y ) by Theorem 1. Therefore, the encoding for the next blocks will be identical to the encoding of the first block but part of the randomness R 1 will be reused from the previous blocks to perform randomness recycling. More specifically, we will reuse the fraction of randomness that is almost independent from the channel output of the first block and whose rate can be shown to approach H(X|Y ). The main difficulty will be to ensure that the target distribution at the output of the channel is correctly approximated over all blocks jointly despite reusing part of the randomness R 1 in all blocks.
We provide a formal description of the coding scheme in Section IV-A, and present its analysis in Section IV-B. Part of the analysis for channel resolvability will be directly reused for the problem of strong coordination in Section VI.

A. Coding Scheme
Fix a joint probability distribution q XY over X × Y, where |X | is a prime number. Define U 1:N X 1:N G n and define for β < 1/2, δ N 2 −N β , the sets Note that the sets V X and V X|Y are defined with respect to q XY . Intuitively, U 1:N [V X|Y ] corresponds to the components of U 1:N that are almost independent from Y -see [34] for an interpretation of V X and V X|Y in terms of randomness extraction. Note also that We use the subscript i ∈ 1, k to denote random variables associated with the encoding of Block i. The encoding process is described in Algorithm 1. The functional dependence graph of the coding scheme is depicted in Figure 4 for the reader's convenience.
Successively draw the remaining components of U 1:N i , i.e., the components in V c X , according to 6: as the corresponding channel output.
7: end for reused over all blocks.
Remark 3. At the expense of additional computations, some of the randomizations described in (2) could be simplified by deterministic decisions as shown in [32].

B. Scheme Analysis
We now provide an analysis of the coding scheme of Section IV-A. Our analysis makes use of simple relations satisfied by the Kullback-Leibler divergence presented in the appendix.
We denote the distribution induced by the coding scheme, i.e., the joint distribution of We start with Lemma 1 that will help us to show in Lemma 2 that channel resolvability holds for each block individually.
Proof: For i ∈ 1, k , we have holds by invertibility of G n , (c) holds by the chain rule for divergence [37], (d) holds by uniformity of the symbols in positions V X , (e) holds by definition of where δ (2) where δ Proof: We only prove the first inequality, the other inequality is obtained similarly. For i ∈ 1, k , where (a) holds by Lemma 14 in the appendix with µ q Y 1:N = µ N qY , (b) holds by the data processing inequality and Lemma 1.
We now show an independence result for two consecutive blocks.
Lemma 3. For i ∈ 2, k , the outputs of two consecutive blocks are asymptotically independent, specifically, where δ (4) where (a) holds by Lemma 17 in the appendix, (b) holds by the chain rule for relative Kullback-Leibler divergence and invertibility of G n , (c) holds by Lemmas 1, 2.
Hence, for i ∈ 2, k , , as can be seen in Figure 4, (e) holds by uniformity of ], (f ) holds because conditioning reduces entropy.
The following lemma shows an independence result among all blocks.
Lemma 4. The outputs of all the blocks are asymptotically independent, specifically, where (a) holds by Lemma 15 in the appendix, (b) holds because for any i ∈ 3, k , for any j ∈ 1, i−2 , the Markov chain Y 1: holds as can be seen in Figure 4, (c) holds by Lemma 3.
We are now ready to show that the target output distribution is correctly approximated over all blocks jointly.
Lemma 5. We have where δ

Proof:
First, observe that where the inequality holds by Lemma 2.
Then, we have where (a) holds by Lemma 16 in the appendix and because µ q Y 1:kN = µ kN qY , (b) holds by Lemma 4 and by (3).
Finally, combining the previous lemmas we obtain the following theorem.
Theorem 5. The coding scheme of Section IV-A achieves channel resolvability, with respect to the Kullback-Leibler divergence, over the discrete memoryless channel (X , q Y |X , Y), where |X | is a prime number. It thus provides an explicit and low-complexity counterpart to the achievability part of Theorem 1.
Proof: The overall rate of uniform symbols required is where we have used [34,Lemma 7]. We have also used that for any i ∈ 1, k , which is proved as follows.
We have for i ∈ 1, k , for j ∈ V c X , where  Finally, we conclude that the optimal rate I(X; Y ) is achieved with Lemma 5.

V. POLAR CODING FOR EMPIRICAL COORDINATION
In this section, we develop an explicit and low-complexity coding scheme for empirical coordination that achieves the entire capacity region when the actions of Node 2 are from an alphabet of prime cardinality. The idea to perform (i) a resolvability achieving random number generation and (ii) randomness recycling through Markov block encoding is the same as in Section IV for channel resolvability.
However, the coding scheme is simpler as the common randomness recycling can be performed and studied more directly than for channel resolvability. In particular, we will see that the encoding blocks can be treated independently of each other since the approximation of the target distribution is concerned with a one dimensional probability distribution, as opposed to an kN dimensional probability distribution in Section IV.
More specifically, the coding scheme can be informally summarized as follows. From X 1:N and some randomness C 1 of rate close to H(Y |X) shared with Node 2, Node 1 constructs a random variable Y 1:N whose joint probability distribution with X 1:N is close to the target distribution q X 1:N Y 1:N , i.e., Node 1 performs a resolvability achieving random number generation. Moreover, Node 1 can construct a message M with rate close to I(X; Y ) such that Node 2 can reconstruct Y 1:N with M and C 1 . Finally, randomness recycling is obtained by performing encoding over k ∈ N * blocks with the same randomness C 1 , so that the overall rate of shared randomness vanishes to zero as the number of blocks increases.
We formally describe the coding scheme in Section V-A, and present its analysis in Section V-B.

A. Coding Scheme
Note that in the following we redefine some notation. Consider the random variables X, Y distributed according to q XY over X ×Y, where |Y| is a prime number. Let N 2 n , n ∈ N * . Define U 1:N Y 1:N G n and define for β < 1/2, δ N 2 −N β , the sets Note that the sets V Y , H Y , V Y |X , and H Y |X are defined with respect to q XY . Note also that  [31], [34] for an interpretation of these sets in terms of privacy amplification and source coding with side information.
Encoding is performed over k ∈ N * blocks of length N . We use the subscript i ∈ 1, k to denote random variables associated with encoding Block i. The encoding and decoding procedures are described in Algorithms 2, 3, respectively.
The protocol described for each encoding block in Algorithm 2 performs a resolvability achieving random number generation as defined in Section III-B, whereas randomness recycling is performed via C 1 which is reused over all blocks.
Remark 5. The coding scheme for each block is similar to lossy source coding schemes [19], [39], as suggested by the optimal communication rate described in Theorem 3. However, the performance metric of interest is different.
Algorithm 2 Encoding algorithm at Node 1 for empirical coordination Require: A vector C 1 of |V Y |X | uniformly distributed symbols shared with Node 2 and X 1:N 1:k . 1: for Block i = 1 to k do 5:

B. Scheme Analysis
The following lemma shows that p Y 1:N X 1:N , defined by p X 1:N q X 1:N and Equation (7), approximates q X 1:N Y 1:N . C i ← C 1 3: Using C i , successively draw the remaining components of U 1:N i according to q U j |U 1:j−1 6: The proof of Lemma 6 is similar to the proof of Lemma 9 in Section VI-B and is thus omitted. The following lemma shows that empirical coordination holds for each block. Note that lim N →∞ P q [(X 1:N , Y 1:N ) ∈ T (q XY )] = 1. Let i ∈ 1, k , we have where we have used Lemma 6 and the AEP for strongly typical sets [37].
We now show that empirical coordination holds for all blocks jointly. hence, where the limit holds by Lemma 7 and because convergence in probability and uniform integrability implies convergence in the mean. We then obtain the claim because convergence in the mean implies convergence in probability.
Theorem 6. The coding scheme described in Algorithms 2, 3 achieves the two-node network empirical coordination capacity region of Theorem 3 for an arbitrary target distribution q XY over X × Y, where |Y| is a prime number.
Proof: The communication rate is where we have used [34,Lemmas 6,7] for the limit.
Node 1 also communicates randomness to reconstruct U 1: which can be shown using Lemma 6 similar to the proof of Theorem 5. Then, the common randomness rate is where the limit holds by [34,Lemma 7].
Finally, we conclude that the region described in Theorem 3 is achieved with Lemma 8.
Remark 6. The claim in Section V-A that the encoding algorithm performs a resolvability achieving random number generation in each block is proved by Lemma 6 and because

VI. POLAR CODING FOR STRONG COORDINATION
In this section, we design an explicit and low-complexity coding scheme for strong coordination that achieves the entire capacity region when the actions of Node 2 are from an alphabet of prime cardinality.
The idea to perform (i) resolvability achieving random number generation and (ii) common randomness recycling with block Markov encoding in Section IV are again reused in this section. In addition, we treat the simulation of a discrete memoryless channel with polar codes to account for an implementation of the coding scheme, as opposed to assuming that channel this operation can be perfectly realized.
An informal description of the strong coordination coding scheme is as follows. From X 1:N and some randomness (C 1 ,C 1 ) of rate close to H(V |X) shared with Node 2, Node 1 constructs a random variable V 1:N whose joint probability distribution with X 1:N is close to the target distribution q X 1:N V 1:N , i.e., Node 1 performs a resolvability achieving random number generation. Moreover, Node 1 can construct a message M with rate close to I(X; V ) such that Node 2 can reconstruct V 1:N with M and (C 1 ,C 1 ). Then, Node 2 simulates a discrete memoryless channel with input V 1:N to form Y 1:N whose joint distribution with X 1:N is close to q X 1:N Y 1:N . Finally, common randomness recycling is realized by encoding over k ∈ N * blocks with the same randomnessC 1 , so that the overall rate of shared randomness becomes the rate of C 1 , which we will see can be chosen on the order of I(V ; Y |X). As in Section IV for channel resolvability, the main difficulty is to ensure that the joint probability distributions of the actions approach the target distribution over all blocks jointly, despite reusingC 1 over all blocks and despite an imperfect simulation of discrete memoryless channels.
The coding scheme is formally described in Section VI-A, and its analysis is presented in Section VI-B.

A. Coding Scheme
In the following we redefine some notation.
Consider the random variables X, Y , V distributed according to q XY V over X × Y × V such that Moreover, assume that |Y| and |V| are prime numbers. By Theorem 4, one can choose |V| as the smallest prime number greater or equal than (|X ||Y|+1). Let N 2 n , n ∈ N * . Define U 1:N V 1:N G n , T 1:N Y 1:N G n , and define for β < 1/2 and δ N 2 −N β the sets Note that the sets H V , V V |X , V V |XY , and V Y |V are defined with respect to q XY V . Similar to the previous sections, we have forms a partition of 1, N . Encoding is performed over k ∈ N * blocks of length N . We use the subscript i ∈ 1, k to denote random variables associated to encoding Block i. The encoding and decoding procedures are described in Algorithms 4, 5, respectively.
The functional dependence graph of the coding scheme is depicted in Figure 5.
The protocol described for each encoding block in Algorithm 4 performs a resolvability achieving random number generation as defined in Section III-B, whereas randomness recycling is performed viā C 1 which is reused over all blocks.

B. Scheme Analysis
Although the coordination metric defined in Section III-C is the variational distance, our analysis will be performed with the Kullback-Leibler divergence to highlight similarities with the analysis of channel Block i 1 Block i Block i + 1 Using C i , successively draw the remaining components of U 1:N i according to q U j |U 1:j−1 7:  Pinsker's inequality.
The following lemma shows that p V 1:N i X 1:N i , defined by p X 1:N i q X 1:N and Equation (8), approximates q V 1:N X 1:N .
We now show that strong coordination holds for each block in the following lemma.
Lemma 10. For i ∈ 1, k , we have where (a) holds by Lemma 16 in the appendix and Lemma 9 with (d) holds by Lemma 9, (e) holds by Lemma 14 in the appendix. We bound the right hand side of (9) by analyzing Step 8 of Algorithm 5 as follows: where (e) holds by invertibility of G n and the chain rule for divergence, (f ) holds by the chain rule for divergence and positivity of the divergence, (g) holds by the proof of Lemma 9, (h) holds by the chain rule for divergence, (i) holds by definition of V Y |V . Finally, combining (9), (10) yields the claim.
Using Lemma 10, we show in the following lemma that an asymptotic independence result holds for two consecutive blocks.
Lemma 11. For i ∈ 2, k , we have, where δ (C) Proof: We reuse the proof of Lemma 3 with the substitutions q U 1:N ← q V 1:N , q Y 1:N ← q X 1:N Y 1:N , Note that we indeed have the Markov condition as can be seen in Figure 5.
Using Lemma 11 we can show an asymptotical independence result for all blocks.
Lemma 12. We have where δ (C) N is defined in Lemma 11.
Proof: We reuse the proof of Lemma 4 with the substitutions p Y 1:N indeed that the Markov condition X 1: holds, as it can be seen in Figure 5.
Using Lemmas 10, 12, we can now show that strong coordination holds over all blocks.
Lemma 13. We have where δ (C) Proof: We reuse the proof of Lemma 5 with the substitutions q Y 1: Finally, we will prove that the communication rate and the common randomness rate are optimal. We can then state our final result as follows.
Theorem 7. The coding scheme described in Algorithms 4, 5 achieves the two-node network strong coordination capacity region of Theorem 4 for an arbitrary target distribution q XY over X × Y, where |Y| is a prime number.

Proof:
The common randomness rate is where we have used [34,Lemma 7].
Moreover, for any i ∈ 1, k , which can be proved using Lemma 10 similar to the proof of Theorem 5.
Moreover, the communication rate and the common randomness rate sum to I(V ; X) + I(V ; Y |X) = I(V ; XY ), which together with (11) and (12) recover the bounds of Theorem 4.
Finally, we conclude that the entire region described in Theorem 4 is achieved with Lemma 13 and Pinsker's inequality.

VII. CONCLUDING REMARKS
We have demonstrated the ability of polar codes to provide solutions to problems related to soft covering. Specifically, we have proposed an explicit and low-complexity coding scheme for channel resolvability by relying on (i) resolvability achieving random number generation and (ii) randomness recycling through block Markov encoding. As discussed in the introduction, our coding scheme generalizes previous explicit coding schemes that achieve channel resolvability but were restricted to uniform distributions or symmetric channels.
Furthermore, leveraging on the idea of the coding scheme to achieve channel resolvability, we have proposed explicit and low-complexity polar coding schemes that achieve the capacity regions of empirical coordination and strong coordination in two-node networks. Our proposed solutions improve previous constructions that were restricted to uniform distributions of actions obtained through a binary symmetric channel, or that required a non-negligible amount of common randomness for empirical coordination, or that assumed that the simulation of discrete memoryless channels can be perfectly implemented.
Note that our coding scheme requires that the cardinality of the alphabet of actions at Node 2 is a prime number. This assumption could be removed if [34,Lemma 6,7]  provides an upper-bound on the difference of the entropy of two random variables defined over the same alphabet.
Lemma 14. Let p, q be two distributions over the finite alphabet X with supports equal to X . We have where µ q min x∈X q(x).
Note that a generalization of Lemma 14 appears in [40]. We provide a short proof for completeness.
Proof: We have where (a) holds by positivity of the Kullback-Leibler divergence, (b) holds by definition of µ q and because ∀x ∈ X , p(x) 1. Finally, we conclude with Pinsker's inequality.
Lemma 15. Let (X i ) i∈ 1,k be arbitrary discrete random variables with joint probability p X1:k . We have where the inequality holds by definition of µ q and because ∀x ∈ X , r(x) 1. Finally, we conclude with Pinsker's inequality.