Entropy and Distributed Source Coding of Connected Soft Random Geometric Graphs Oliver Baker and Carl P. Dettmann Abstract We consider the distributed compression of Soft Random Geometric Graphs (SRGGs) above the connectivity threshold. We establish the Slepian-Wolf rate region for the SRGG in the setting where there are a finite number of encoders compressing sections of the graph independently. To do so, we prove novel limit theorems and asymptotic equipartition properties for the SRGG and its entropy, which allow us to use random binning techniques for distributed compression. I Introduction In the modern world, devices are more connected than ever. This results in networks becoming larger, increasing the need for research on compression of networks. In particular, in areas of application such as wireless networking, random models of large networks with a spatial embedding have gained popularity [ 8 ] . One popular model for wireless networks is the Soft Random Geometric Graph (SRGG). In this model, nodes are connected at random according to a function of their spatial distance [ 12 ] . Despite their numerous applications, the information theory of these random graphs is not well understood. In recent years there have been a growing number of works that have concentrated on this model or similar ones such as graphons. In [ 10 ] a limit theorem for the entropy of W random graphs (which include SRGGs as a special case) was proven. Since then, there have been a number of works attempting to bound or quantify the entropy, such as [ 5 , 2 , 4 ] . Also, the compression of random graphs has gained popularity recently. Models such as sparse Erdős-Rényi graphs [ 3 ] , stochastic block models [ 1 , 14 ] and preferential attachment graphs [ 15 ] have all been considered. Compression of the SRGG (or generalisations) has been studied in [ 6 , 11 , 13 ] . Crucially, all of these works focus on compression in the centralised setting. That is, we have an encoder that sees the entire graph, and compresses it for a decoder to later decompress. However, in many applications, it is perhaps more realistic to assume that nodes, or blocks of nodes only have access to partial information about the network. In [ 7 ] , the distributed compression of Erdős-Rényi and configuration model graphs is studied, but distributed compression of the SRGG is, to the best of our knowledge, unstudied. In this work, we consider the regime where we have a fixed, but arbitrary number of encoders which have access to different sections of the graph. Our other source of novelty is the specific regime in which we study the SRGG. In the above works, when the SRGG (or W random graph) is made sparse (by which we mean that the expected degree of a node is sublinear in the total number of nodes), it is done by randomly removing a fraction of the edges of a dense ensemble. However, this places less emphasis on the geometry, since the length scale of edges does not scale with the number of nodes. In our work, we study the more commonly considered regime, for example in the work of Penrose [ 12 ] , where the ‘connection range’ of each node is decreasing in the number of nodes. Equivalently, the size of the domain in which we embed the graph is growing as we add more nodes. We make this idea more precise later. To the best of our knowledge, this regime has not yet been studied in an information-theoretic context. We also note that the SRGG is an example of a non-standard source , in that it cannot be written as a string of stationary, ergodic or Markovian symbols. We must therefore employ the ideas of information spectrum theory to study its information theoretic properties. In this work, we contribute the following. 1. A limit theorem for the entropy rate of the SRGG, 2. an Asymptotic Equipartition Property (AEP) for the SRGG, 3. a complete characterisation of the Slepian-Wolf region for the distributed compression of the SRGG. In Section II we formally introduce the model, the information spectrum, and the distributed compression setting. Section III presents our main results, and Section IV contains proof ideas. The full proofs may be found in the supplemental material. Finally, Section V concludes. II Model and Problem Formulation II-A Soft Random Geometric Graphs Definition 1 (Soft Random Geometric Graph) . Let Z_{1},...,Z_{n} be independent, uniformly distributed points in a compact set \mathcal{K}\subset\mathbb{R}^{d} with unit volume, a non-empty interior, whose boundary is piecewise smooth, of finite length and has a finite number of corners. The Soft Random Geometric Graph (SRGG) G_{n}=(V_{n},E_{n}) is the graph with vertex set V_{n}=[n]:=\{1,2,...,n\} , and edge set formed by connecting each pair of vertices i,j\in V_{n} independently with probability p_{n}(R_{ij}) , where R_{ij}:=\|Z_{i}-Z_{j}\| is the Euclidean distance between nodes i and j , and p_{n}:[0,\infty)\to[0,1] is the ‘connection function’. Let \mathcal{G}_{n} be the set of all SRGGs on n nodes, then \mathcal{G}_{n} is called the ensemble of SRGGs. In this work, we will consider specifically the following form of connection function. Let \{s(n)\}_{n=1}^{\infty} be a positive, decreasing sequence of real numbers. We call s(n) the sparsity of the SRGG. Then, we focus on connection functions p_{n}(r)=p(r/s(n)) , where p:[0,\infty)\to[0,1] . One can think of this form of connection function in two equivalent ways. First, we can imagine fixing the domain \mathcal{K} , and decreasing the ‘connection range’ of each node, that is, the length scale at which two nodes are likely to be connected is decreasing with n . Alternatively, we can imagine instead fixing the connection range, and increasing the size of \mathcal{K} with n . We note that this is a different regime to the other commonly considered SRGG, where p_{n}(r)=s(n)p(r) . We will require that 1\gg s(n)\gg\left(\frac{\log n}{n}\right)^{1/d} . This requirement has two interpretations. The first is that this is the regime where the SRGG is connected with high probability as n\rightarrow\infty [ 12 ] . The second is that the entropy of the labelled graph is asymptotically equivalent to the entropy of the unlabelled graph. Definition 2 (Entropy of the SRGG) . The Shannon Entropy of the SRGG is denoted by H(\mathcal{G}_{n}) , and is given by H(\mathcal{G}_{n}):=-\sum_{G\in\mathcal{G}_{n}}\mathbb{P}\left(G_{n}\right)\log\mathbb{P}\left(G_{n}\right) (1) where the logarithm is to base 2, and we take the convention that 0\log 0=0 . Also, if Z_{n} is the random vector containing the locations of each node, then the conditional entropy H(\mathcal{G}_{n}|\mathcal{Z}_{n})=\mathbb{E}[H(\mathcal{G}_{n}|Z_{n})] is given by H(\mathcal{G}_{n}|\mathcal{Z}_{n})=\binom{n}{2}\int_{0}^{\infty}f_{\mathcal{K}}(r)h_{2}(p_{n}(r))dr (2) where f_{\mathcal{K}} is the probability density of pairwise distances in \mathcal{K} , and h_{2}(p)=-p\log p-(1-p)\log(1-p) is the binary entropy function. We treat the following as a standing assumption for the remainder of the paper. Assumption 1 . The connection function p_{n} is given by p_{n}(r)=p(r/s(n)) , where p is a Hölder continuous function, that is, for every (x,y),(x^{\prime},y^{\prime})\in\mathcal{K}^{2} , |p(x,y)-p(x^{\prime},y^{\prime})|\leq L\|(x,y)-(x^{\prime},y^{\prime})\|^{\alpha} (3) with L,\alpha>0 as constants. We assume that, if d is the dimension of the space \mathcal{K}\subset\mathbb{R}^{d} , \int_{0}^{\infty}r^{2d}h_{2}(p(r))dr<\infty (4) and \int_{0}^{\infty}r^{d-1}p(r)(1-p(r))\log^{2}\left(\frac{p(r)}{1-p(r)}\right)dr<\infty (5) We also define the following integral h^{*}:=\kappa_{d-1}\int_{0}^{\infty}r^{d-1}h_{2}(p(r))dr<\infty (6) where \kappa_{d-1} is the volume of the unit d-1 ball. II-B The Information Spectrum As briefly mentioned in the introduction, the SRGG is what is known as a ‘non-standard source’. In classical Information Theory, sources are considered to consist of a sequence of i.i.d. symbols, or at the very least, to be stationary and ergodic. However, the SRGG has neither of these properties. Instead, we must consider the graph G_{n} in its entirety. Information spectrum theory was developed to deal with general sources such as the SRGG. The theory is developed around spectral entropy rates . We first define the limit superior in probability , and the limit inferior in probability . Let (X_{1},X_{2},...) be a real-valued sequence of random variables, then p\mbox{-}\limsup_{n\rightarrow\infty}X_{n}:=\inf\left\{\alpha|\lim_{n\rightarrow\infty}\mathbb{P}\left(X_{n}>\alpha\right)=0\right\} (7) p\mbox{-}\liminf_{n\rightarrow\infty}X_{n}:=\sup\left\{\beta|\lim_{n\rightarrow\infty}\mathbb{P}\left(X_{n}<\beta\right)=0\right\} (8) If p\mbox{-}\liminf_{n\rightarrow\infty}X_{n}=p\mbox{-}\limsup_{n\rightarrow\infty}X_{n}=X^{*} , we say that p\mbox{-}\lim_{n\rightarrow\infty}X_{n}=X^{*} , which is equivalent to X_{n}\to X^{*} in probability as n\rightarrow\infty . Definition 3 (Spectral Entropy Rates) . The spectral sup-entropy of an ensemble of SRGGs \mathcal{G}_{n} with sparsity s(n) is defined as \overline{H}(\mathcal{G}_{n})=p\mbox{-}\limsup_{n\rightarrow\infty}\frac{1}{\binom{n}{2}s(n)^{d}}\log\frac{1}{\mathbb{P}\left(G_{n}\right)} (9) Similarly, the spectral inf-entropy is defined as \underline{H}(\mathcal{G}_{n})=p\mbox{-}\liminf_{n\rightarrow\infty}\frac{1}{\binom{n}{2}s(n)^{d}}\log\frac{1}{\mathbb{P}\left(G_{n}\right)} (10) These quantities are similar to the spectral entropy rates used in information spectrum theory for general sources [ 9 ] . The difference is in the normalisation. Normalising by the blocklength \binom{n}{2} , would give \overline{H}(\mathcal{G}_{n})=0 . This is not a very interesting result, since the sparsity induced by s(n) means the graph has a vanishing density, and so the majority of edges are absent in the n\to\infty limit. Our definition may be thought of as an ‘effective’ spectral entropy rate, capturing the leading order behaviour of compression length, rather than simply dividing through by the number of symbols in the source. It is simple to check that these quantities retain their operational meaning after replacing the standard scaling of 1/n by 1/(\binom{n}{2}s(n)^{d}) . III Main Results We first establish the following limit theorem for the entropy of the SRGG. Theorem 1 (Limit Theorem) . Let \mathcal{G}_{n} be the ensemble of SRGGs with connection function p_{n}(r)=p(r/s(n)) . Then, \lim_{n\rightarrow\infty}\frac{H(\mathcal{G}_{n})}{\binom{n}{2}s(n)^{d}}=h^{*} (11) The next result strengthens the above to an AEP. Instead of dealing with the entropy, we look at the spectral entropy rates. The result shows that the spectral sup-entropy rate is equal to the spectral inf-entropy rate. Theorem 2 (Asymptotic Equipartition Property) . If G_{n} is a random SRGG sampled from \mathcal{G}_{n} , p\mbox{-}\lim_{n\rightarrow\infty}\frac{1}{\binom{n}{2}s(n)^{d}}\log\frac{1}{\mathbb{P}\left(G_{n}\right)}=h^{*} (12) In other words, \overline{H}(\mathcal{G}_{n})=\underline{H}(\mathcal{G}_{n})=h^{*} (13) This implies the existence of sets defined for all \epsilon>0 , \mathcal{T}_{n}^{\epsilon}:=\left\{G_{n}:\left|\log\frac{1}{\mathbb{P}\left(G_{n}\right)}-H(\mathcal{G}_{n})\right|\leq\binom{n}{2}s(n)^{d}\epsilon\right\} (14) such that 1. \mathbb{P}\left(G_{n}\in\mathcal{T}_{n}^{\epsilon}\right)\to 1 as n\rightarrow\infty 2. For each G_{n}\in\mathcal{T}_{n}^{\epsilon} , 2^{-\binom{n}{2}(s(n)^{d}h^{*}+\epsilon)}\leq\mathbb{P}\left(G_{n}\right)\leq 2^{-\binom{n}{2}s(n)^{d}(h^{*}-\epsilon)} 3. For every \delta>0 , there exists an n^{*} so that for all n>n^{*} , we have (1-\delta)2^{\binom{n}{2}s(n)^{d}(h^{*}-\epsilon)}\leq|\mathcal{T}_{n}^{\epsilon}|\leq 2^{\binom{n}{2}s(n)^{d}(h^{*}+\epsilon)} (15) We now introduce the distributed compression scheme for the SRGG. For each node i\in[n] , let N_{i} be a \{0,1\}^{(n-1)} -valued random vector representing the neighbourhood of i in G_{n} . That is, N_{i}=(X_{ij})_{j\neq i} , where X_{ij}=1 if i and j share an edge, and is 0 otherwise. The distributed compression problem is formulated as follows. Let L\in\mathbb{N} be a constant. We partition the graph G_{n} into L ‘blocks’, given by B^{(n)}_{l}=\left\{N_{i}:\frac{(l-1)n}{L}0 . This means that we can choose any m=m(n) such that \log(m)\ll ns(n)^{d} and ms(n)^{(d+\alpha)/\alpha}\gg 1 to get \frac{H(\mathcal{G}_{n})-H(\mathcal{G}_{n}|\mathcal{Z}_{n})}{\binom{n}{2}s(n)^{d}}\leq\frac{nd\log m}{\binom{n}{2}s(n)^{d}}+(1+o(1))C\frac{\log(s(n)m)}{s(n)^{d+\alpha}m^{\alpha}} (24) which goes to 0 as n\rightarrow\infty . To complete the result, we use Theorem 1 from [ 2 ] . Under the assumption ( 6 ), this gives \frac{H(\mathcal{G}_{n}|\mathcal{Z}_{n})}{\binom{n}{2}s(n)^{d}}\overset{n\rightarrow\infty}{\to}h^{*} (25) Combining with the above argument yields the result. ∎ IV-B Theorem 2 To prove this theorem, we need the following lemma, which is a simple consequence of the weak law of large numbers. The only condition we need to verify is that: \displaystyle\frac{\text{Var}(\log\mathbb{P}\left(G_{n}|Z_{n}\right))}{\binom{n}{2}^{2}s(n)^{2d}} \displaystyle=\frac{\text{Var}(X_{12}\log\mathbb{P}\left(X_{12}|Z_{n}\right)+(1-X_{ij})\log(1-\mathbb{P}(X_{12}|Z_{n})))}{\binom{n}{2}s(n)^{2d}} is finite. This is proven by a similar argument to the proof of [ 2 , Theorem 1] cited above, and uses assumptions ( 4 ) and ( 5 ). Lemma 1 (Conditional AEP) . Let \{(G_{n},Z_{n})\}_{n=2}^{\infty} be a sequence of pairs of random sparse SRGGs and the node locations that generated it. Then, s(n)^{-d}\binom{n}{2}^{-1}\left(-\log\mathbb{P}\left(G_{n}|Z_{n}\right)-H(\mathcal{G}_{n}|\mathcal{Z}_{n})\right)\to 0 (26) almost surely as n\rightarrow\infty . Once this is proven, we can bound \displaystyle|-\log\mathbb{P}\left(G_{n}\right)-H(\mathcal{G}_{n})| \displaystyle\leq|H(\mathcal{G}_{n})-H(\mathcal{G}_{n}|\mathcal{Z}_{n})| \displaystyle+|-\log\mathbb{P}\left(G_{n}\right)-H(\mathcal{G}_{n}|\mathcal{Z}_{n})| By Theorem 1 the first term is o(n^{2}s(n)^{d}) , and for the second term, we use \displaystyle\mathbb{P}(|-\log \displaystyle\mathbb{P}\left(G_{n}\right)-H(\mathcal{G}_{n}|\mathcal{Z}_{n})|>\binom{n}{2}s(n)^{d}\epsilon) \displaystyle\leq\frac{\mathbb{E}_{G_{n}}[|-\log\mathbb{P}\left(G_{n}\right)-H(\mathcal{G}_{n}|\mathcal{Z}_{n})|]}{\binom{n}{2}s(n)^{d}\epsilon} \displaystyle=\frac{\mathbb{E}_{G_{n},Z_{n}}[|-\log\mathbb{P}\left(G_{n}\right)-H(\mathcal{G}_{n}|\mathcal{Z}_{n})||Z_{n}]}{\binom{n}{2}s(n)^{d}\epsilon} \displaystyle\leq\frac{\mathbb{E}_{G_{n},Z_{n}}[|-\log\mathbb{P}\left(G_{n}|Z_{n}\right)-H(\mathcal{G}_{n}|\mathcal{Z}_{n})|]}{\binom{n}{2}s(n)^{d}\epsilon} \displaystyle+\frac{\mathbb{E}_{G_{n},Z_{n}}[|\log\mathbb{P}\left(G_{n}|Z_{n}\right)-\log\mathbb{P}\left(G_{n}\right)|]}{\binom{n}{2}s(n)^{d}\epsilon} (27) Here, the first term goes to zero, since Lemma 1 may be upgraded to convergence in expectation due the finite variance condition we established above. The second term goes to 0 via the following argument. Let r_{n}=r(G_{n},Z_{n})=\frac{\mathbb{P}\left(G_{n}|Z_{n}\right)}{\mathbb{P}\left(G_{n}\right)}. (28) Then, we have \mathbb{E}_{G_{n},Z_{n}}[|\log\mathbb{P}\left(G_{n}|Z_{n}\right)-\log\mathbb{P}\left(G_{n}\right)|]=\mathbb{E}_{G_{n},Z_{n}}[|\log r_{n}|] =\mathbb{E}_{Z_{n}}\left[\sum_{G_{n}\in\mathcal{G}_{n}}\mathbb{P}\left(G_{n}|Z_{n}\right)|\log r_{n}|\right] (29) =\mathbb{E}_{Z_{n}}\left[\sum_{G_{n}\in\mathcal{G}_{n}}\mathbb{P}\left(G_{n}\right)|r_{n}\log r_{n}|\right] (30) Then, we make the following two observations. First, |x|=x-2x\mathbbm{1}(x<0) (31) and second, for x\in(0,1) 0<-x\log x<\frac{1}{e}\log e (32) And therefore, \displaystyle\mathbb{E}_{G_{n},Z_{n}}[|\log r_{n}|]\leq\mathbb{E}_{Z_{n}}\left[\sum_{G_{n}\in\mathcal{G}_{n}}\mathbb{P}\left(G_{n}\right)r_{n}\log r_{n}\right] \displaystyle-2\mathbb{E}_{Z_{n}}\left[\sum_{G_{n}\in\mathcal{G}_{n}}\mathbb{P}\left(G_{n}\right)r_{n}\log r_{n}\Bigg|r_{n}<1\right] (33) \leq\mathbb{E}_{Z_{n}}\left[\sum_{G_{n}\in\mathcal{G}_{n}}\mathbb{P}\left(G_{n}\right)r_{n}\log r_{n}\right]+\frac{2}{e}\log(e)\mathbb{E}_{Z}\left[\sum_{G_{n}\in\mathcal{G}_{n}}\mathbb{P}\left(G_{n}\right)\right] (34) =\mathbb{E}_{G_{n},Z_{n}}\left[\log\frac{\mathbb{P}\left(G_{n}|Z_{n}\right)}{\mathbb{P}\left(G_{n}\right)}\right]+\frac{2}{e}\log e (35) =H(\mathcal{G}_{n})-H(\mathcal{G}_{n}|\mathcal{Z}_{n})+\frac{2}{e}\log e=o(n^{2}s(n)^{d}) (36) This places an o(1) bound on the probability that |\log(1/\mathbb{P}\left(G_{n}\right))-H(\mathcal{G}_{n})|>\binom{n}{2}s(n)^{d}\epsilon for any \epsilon>0 . Combining this with the fact that (\binom{n}{2}s(n)^{d})^{-1}H(\mathcal{G}_{n})\to h^{*} as n\rightarrow\infty , we get p\mbox{-}\lim_{n\rightarrow\infty}\frac{1}{\binom{n}{2}s(n)^{d}}\log\frac{1}{\mathbb{P}\left(G_{n}\right)}=h^{*} (37) The properties of the typical set are derived using simple standard techniques. IV-C Theorem 3 The proof of Theorem 3 hinges on the following lemma. For a set S\subseteq V_{n} , define by S^{c} the set V_{n}\setminus S . Lemma 2 . Let S\subseteq V_{n} , then H(N_{S}|N_{S^{c}})=H(\mathcal{G}_{|S|}) (38) This implies that if \{S_{n}\}_{n=1}^{\infty} is a sequence of subsets of V_{n} indexed by n , such that |S_{n}|\to\infty as n\rightarrow\infty , then p\mbox{-}\lim_{n\rightarrow\infty}\frac{1}{\binom{|S_{n}|}{2}s(|S_{n}|)^{d}}\log\frac{1}{\mathbb{P}\left(N_{S_{n}}|N_{S_{n}^{c}}\right)}=h^{*} (39) Proof. We show this for {S}=\{1,..,k\} , which generalises to any set {S} by re-labelling the graph. Writing out N_{{S}} in full, we have N_{{S}}=\{X_{ij}\}_{\begin{subarray}{c}i\in{S},1\leq j\leq n\\ i\neq j\end{subarray}},N_{{S}^{c}}=\{X_{ij}\}_{\begin{subarray}{c}i\notin{S},1\leq j\leq n\\ i\neq j\end{subarray}} (40) Then, the entropy H(N_{S}|N_{S^{c}}) is the entropy of A_{{S}}:=N_{S}\setminus(N_{S}\cap N_{{S}^{c}}) conditioned on B_{S}:=N_{{S}^{c}}\setminus(N_{{S}}\cap N_{{S}^{c}}) , since the edges in the intersection do not contribute to the entropy. The key observation is that if X_{ij}\in A_{S} , then there does not exist an edge X_{uv} in B_{S} with u=i or v=j . Therefore, every edge variable in A_{S} is independent of all those in B_{S} . Then, H(N_{S}|N_{S^{c}})=H(A_{S}|B_{S})=H(\{X_{ij}\}_{1\leq i0 we have a typical set \mathcal{T}_{n}^{\epsilon}(B^{(n)}_{\Lambda}) , which we define as \displaystyle\mathcal{T}_{n}^{\epsilon}(B^{(n)}_{\Lambda}):=\Bigg\{(B_{\Lambda}^{(n)},B_{\Lambda^{c}}^{(n)}): \displaystyle\Bigg|\log\frac{1}{\mathbb{P}\left(B_{\Lambda}^{(n)}|B_{\Lambda^{c}}^{n}\right)}-h^{*}\Bigg|<{\binom{\frac{|\Lambda|n}{L}}{2}s\left(\frac{\Lambda n}{L}\right)^{d}\epsilon}\Bigg\} (41) whose existence is guaranteed by the second part of Lemma 2 by taking S_{n}=\{i:i\in\{\frac{(l-1)n}{L},...,\frac{ln}{L}\text{for some }l\in\Lambda\}\} . With this, we can apply the standard random binning argument, which we sketch here. Let L be a fixed integer, then we design the codebook as follows for an L -tuple of rates (R_{1},...,R_{L}) . For each l=1,...,L , we generate assignments by independently assigning each b_{l}^{(n)}\in\mathcal{B}_{l}^{(n)} a uniformly random element, which we call its index, from the codebook \mathcal{M}_{l}^{(n)}:=\{1,2,3,...,2^{\frac{n}{L}(n-1)s(n)^{d}R_{l}}\} (42) we denote the index of b_{l}^{(n)} as \phi_{l}^{(n)}(b_{l}^{(n)}) . Note that more than one realisation b_{l}^{(n)} may be assigned the same index. We reveal these assignments to both the encoder, and the decoder. To encode a graph, each encoder l sees its block, b_{l}^{(n)} . Then, the independent encodings are sent as the tuple (\phi_{1}^{(n)}(b_{1}^{(n)}),...,\phi_{L}^{(n)}(b_{L}^{(n)})) . The decoder receives this tuple, and searches for their own tuple (\hat{b}_{1}^{(n)},...,\hat{b}_{L}^{(n)}) (or equivalently a graph \hat{G}_{n} ), such that (\hat{b}_{1}^{(n)},...,\hat{b}_{L}^{(n)}) is unique, typical, and \phi_{l}^{(n)}(\hat{b}_{l}^{(n)})=\phi_{l}^{(n)}(b_{l}^{(n)}) for every l . If they cannot find such a tuple, an error is declared. Therefore, an error occurs if, first, the graph is atypical, or second, there exists an alternative decoding that is typical, and matches the encoding of the target graph. By Theorem 2 the first error probability goes to 0. For \Lambda\subseteq\{1,...,L\} , let B_{\Lambda}^{(n)}=\bigcup_{l\in\Lambda}B_{l}^{(n)} . Then the probability of the second error event is bounded above by the sum over such \Lambda of \displaystyle\mathbb{P}\left(E_{2}(\Lambda)\right)=\mathbb{P}\Big(\exists \displaystyle\hat{b}_{\Lambda}^{(n)}\neq B_{\Lambda}^{(n)}\text{ s.t. }(N_{\hat{b}_{\Lambda}^{(n)}},N_{B_{\Lambda^{c}}^{(n)}})\in\mathcal{T}_{n}^{\epsilon}(B_{\Lambda}^{(n)}) \displaystyle\text{ and }\phi_{l}^{(n)}(\hat{b}_{l}^{(n)})=\phi_{l}^{(n)}(B_{l}^{(n)})\forall l\in\Lambda\Big) Following the standard argument, this can be bounded above by \mathbb{P}\left(E_{2}(\Lambda)\right)\leq 2^{-\frac{n(n-1)}{L}s(n)^{d}\sum_{l\in S}R_{l}}|\mathcal{T}_{n}^{\epsilon}(B_{\Lambda}^{(n)})| (43) \leq 2^{-\frac{n(n-1)}{L}s(n)^{d}\sum_{l\in\Lambda}R_{l}+\binom{v}{2}s(v)^{d}(h^{*}+\epsilon)} (44) where v=|B_{\Lambda}^{(n)}|=|\Lambda|n/L . From this we can see that a sufficient condition for achievability with high probability as n\rightarrow\infty is \sum_{l\in\Lambda}R_{l}\geq\frac{|\Lambda|}{L}\frac{h^{*}}{2}\lim_{n\rightarrow\infty}\frac{s(|\Lambda|n/L)^{d}}{s(n)^{d}} (45) For the converse direction, define a_{n}(\Lambda)=\frac{|\Lambda|n}{L}(n-1)s\left(\frac{|\Lambda|n}{L}\right)^{d} . As a consequence of [ 9 , Lemma 7.2.2] , we have for any \Lambda\subseteq[L] , \displaystyle P_{E}^{(n)}\geq\mathbb{P}\bigg( \displaystyle\frac{1}{a_{n}(\Lambda)}\log\frac{1}{\mathbb{P}\left(B_{\Lambda}^{(n)}|B_{\Lambda^{c}}^{(n)}\right)} \displaystyle\geq\frac{1}{a_{n}(\Lambda)}\sum_{l\in\Lambda}\log|\mathcal{M}_{l}^{(n)}|+\gamma\bigg)-2^{-a_{n}(\Lambda)\gamma} (46) Suppose \limsup_{n\rightarrow\infty}\frac{1}{a_{n}(\Lambda)}\sum_{l\in\Lambda}\log|\mathcal{M}_{l}^{(n)}|\leq\sum_{l\in\Lambda}R_{l} , then \displaystyle\lim_{n\rightarrow\infty}P_{E}^{(n)}\geq\lim_{n\rightarrow\infty}\mathbb{P}\Big(\frac{1}{a_{n}(\Lambda)}\log\frac{1}{\mathbb{P}\left(G_{|B_{\Lambda|}}\right)}\geq\sum_{l\in\Lambda}R_{l}+\gamma\Big) \displaystyle=\begin{cases}1&\lim_{n\rightarrow\infty}2\frac{s(n)^{d}(n-1)}{s\left(\frac{|\Lambda|n}{L}\right)^{d}\left(\frac{|\Lambda|n}{L}-1\right)}\left(\sum_{l\in S}R_{l}+\gamma\right)