Introduction
In many data science applications, data appears in the form of large-scale graphs. For example, in social networks, vertices represent users and an edge between vertices represents friendship; in the World Wide Web, vertices are websites and edges indicate the hyperlinks from one site to the other; in biological systems, vertices can be proteins and edges illustrate protein-to- protein interaction. Such graphs may contain billions of vertices. In addition, edges tend to be correlated with each other since, for example, two people sharing many common friends are likely to be friends as well. How to efficiently compress such large-scale structural information to reduce the I/O and communication costs in storing and transmitting such data is a persisting challenge in the era of big data.
The problem of graph compression has been studied in different communities, following various different methodologies. Several methods exploited combinatorial properties such as cliques and cuts in the graph [1], [2]. Many works targeted at domain-specific graphs such as web graphs [3], biological networks [4], [5], and social networks [6]. Various representations of graphs were proposed, such as the text-based method, where the neighbour list of each vertex is treated as a “word” [7], [8], and the
In this paper, we take an information theoretic approach to study lossless compression of graphs with vertex labels. We assume the graph is generated by some random graph model and investigate lossless compression schemes that achieve the theoretical limit, i.e., the entropy of the graph, asymptotically as the number of vertices goes to infinity. When the underlying distribution/statistics of the random graph model is known, optimal lossless compression can be achieved by methods like Huffman coding. However, in most real-world applications, the exact distribution is usually hard to obtain and the data we are given is a single realization of this distribution. This motivates us to consider the framework of universal compression, in which we assume the underlying distribution belongs to a known family of distributions and require that the encoder and the decoder should not be a function of the underlying distribution. The goal of universal compression is to design a single compression scheme that universally achieves the optimal theoretical limit, for every distribution in the family, without knowing which distribution generates the data. For this paper, we focus on the family of stochastic block models, which are widely used random graph models that capture the clustering effect in social networks. Our goal is to develop a universal graph compression scheme for a family of stochastic block models with as wide a range of parameters as possible.
How to design a computationally efficient universal compression scheme is a fundamental question in information theory. In the past several decades, a large number of universal compressors were proposed for one-dimensional sequences with fixed alphabet size, whose entropy is linear in the number of variables. Prominent results include the Laplace and Krichevsky–Trofimov (KT) compressors for i.i.d. processes [12], [13], Lempel–Ziv compressor [14], [15] and Burrows–Wheeler transform [16] for stationary ergodic processes, and context tree weighting [17] for finite memory processes. Many of these have been adopted in standard data compression applications such as
For the first challenge, a natural question arising is: can we convert the two-dimensional adjacency matrix of the graph into a one-dimensional sequence in some order and apply a universal compressor for the sequence? For some simple graph models such as Erdős- Rényi graph, where each edge is generated i.i.d. with probability
We alleviate these challenges by designing a decomposition of the adjacency matrix into submatrices. We then show in Proposition 2 that with a carefully chosen parameter, the submatrix decomposition converts two-dimensional correlated entries into a sequence of almost i.i.d. submatrices with slowly growing alphabet size. To address the second challenge, we introduce a new definition of universality that accommodates data with an unknown leading order in its entropy expression. The new universality normalizes the compression length by the entropy of data, requiring it to go to one, as compared to normalizing by the number of variables in the standard definition. Normalizing by the number of variables, implicitly assumes that the entropy is linear in
Notation: For an integer
A. Problem Setup
1) Universal Graph Compressor:
For simplicity, we focus on simple (undirected, unweighted, no self-loop) graphs with labeled vertices in this paper. But our compression scheme and the corresponding analysis can be extended to more general graphs. Let
![Right-click on figure for MathML and additional features.](data:image/svg+xml,<svg xmlns="http://www.w3.org/2000/svg" width="24" height="20"><rect fill-opacity="0"/></svg> "Right-click on figure or equation for MathML and additional features."){kind=small}
\begin{equation*} H(A_{n})-\log (e(H(A_{n})+1)) \le \mathsf {E} [\ell (C(A_{n}))], \tag{1}\end{equation*}
and therefore \begin{equation*} \liminf _{n \to \infty }\frac { \mathsf {E}[\ell (C(A_{n}))] }{H(A_{n})} \ge 1.\end{equation*}
\begin{equation*} \limsup _{n \to \infty }\frac { \mathsf {E}[\ell (C(A_{n}))] }{H(A_{n})} = 1. \tag{2}\end{equation*}
2) Stochastic Block Model:
A stochastic block model
\begin{align*} \mathscr {P}_{1}( \epsilon ) \mathchoice {\colon }{\colon }{:\mspace {1mu}}{:}&\mathrm {SBM}(n,L, {\mathbf{p}}, {\mathbf{W}}) \\ & \text {with } f(n) = O(1), f(n)= \Omega \left ({\frac {1}{n^{2- \epsilon }}}\right ), \tag{3}\\ \mathscr {P}_{2}( \epsilon ) \mathchoice {\colon }{\colon }{:\mspace {1mu}}{:}&\mathrm {SBM}(n,L, {\mathbf{p}}, {\mathbf{W}}) \\ & \text {with } f(n) = o(1), f(n)= \Omega \left ({\frac {1}{n^{2- \epsilon }}}\right ). \tag{4}\end{align*}
Note that the edge probability 3) Minimax Redundancy:
Besides universality, which only concerns the first order terms in the expected length of the compressor and the entropy of the graph, the redundancy of a universal compressor is another important metric we wish to optimize in the design of universal graph compressors. Define the redundancy of a lossless compressor
\begin{equation*} R(C,A_{n}) = \mathsf {E}[\ell (C(A_{n}))] - H(A_{n}). \tag{5}\end{equation*}
Then the minimax redundancy over a distribution family \begin{equation*} R^{*}_{n}(\mathscr {P}) = \inf _{C} \sup _{ \mathsf {P}\in \mathscr {P}} R(C,A_{n}). \tag{6}\end{equation*}
\begin{align*} \mathscr {P}_{3}(f(n),Q_{\mathrm {max}}): &\mathrm {SBM}(n,L, {\mathbf{p}},f(n) {\mathbf{Q}}) \\ & \text {with } Q_{i,j} \le Q_{\mathrm {max}} \text {for all } i,j \in [n]. \tag{7}\end{align*}
B. Literature in the Information-Theoretic Framework
Under the information-theoretic framework, lossless graph compression has been studied in [20], [21], [22], [23], [24], [25], [26], [27], [28], [29], [30], [31], [32], [33], [34], [35], [36], [37], [38], [39], and [40] and lossy compression of directed graphs was studied in [41]. In [23] and [31], universal compression of unlabeled graphs (isomorphism classes) is investigated. For lossless compression of labeled graphs, [24] and [25] studied the compression of graphs generated from SBMs. However, it does not consider universal compression schemes. In [22], a universal compression algorithm is proposed for two-dimensional arrays of data by first converting the two-dimensional data into a one-dimensional sequence using a Hilbert–Peano curve and then applying the Lempel–Ziv algorithm [15] for sequences. In [26], [27], [28], [32], and [33], universal compression of tree graphs were studied. In [37], [38], [39], and [40], a minimum description length based method was proposed to infer network structures in stochastic block models. Recently, universal compression of graphs with marked edges and vertices was studied by Delgosha and Anantharam [34], [35]. They focus on the sparse graph regime, where the number of edges is in the same order as the number of vertices
C. Contribution and Organization
The main contributions of the paper are summarized as follows. Firstly, we propose a polynomial-time graph compressor and establish its universality over the corresponding family of stochastic block models. Secondly, we present upper and lower bounds for the minimax redundancy of stochastic block models. Finally, we analyze the proposed compressor under the local weak convergence framework considered in [34] and [42]. We show that the proposed compressor achieves the same performance guarantee (BC entropy) as the compressor in [34].
The rest of the paper is organized as follows. In Section I-A, we defined universality over a family of graph distributions, the stochastic block models and the minimax redundancy of a family of distributions. We present our main result in Section II, which is a polynomial-time graph compressor that is universal for a family containing most of the non-trivial stochastic block models. We describe the proposed graph compressor in Section II-A. In Section II-B, we state the main theorems of the paper—two theorems on the university of the proposed compressor as well as a theorem on upper and lower bounds for the minimax redundancy. In Section II-C, we implement our compressor in four benchmark graph datasets and compare its empirical performance to four competing algorithms. We illustrate key steps in establishing universality in Section III and elaborate on the proof of each step in Section IV. In Section V, we prove upper and lower bounds for the minimax redundancy. In Section VI, we provide the second-order analysis of the expected length of our compressor and compare it to the one in [34]. In Section VII, we explain why some natural attempts to compress stochastic block models are not applicable to our problem or not universal. In Section VIII, we conclude our results and introduce some open problems and potential future works.
Main Results
We present our compression scheme in Section II-A and state its performance guarantee in Theorems 1 and 2. The key idea in our design is a decomposition of the adjacency matrix into submatrices, which, with a carefully chosen parameter, converts the two-dimensional correlated entries in the adjacency matrix into a sequence of almost i.i.d. submatrices. We then compress the submatrices using a Krichevsky–Trofimov or Laplace compressor and generalize their length analyses from i.i.d. processes to arbitrarily correlated but identically distributed processes.
A. Algorithm: Universal Graph Compressor
In this section, we describe our universal graph compression scheme. For each integer
Submatrix decomposition. Let
n′=⌊n/k⌋ n~=⌊n/k⌋k 1≤i,j≤n′ Bij An (i−1)k+1,(i−1)k+2,…,ik (j−1)k+1,(j−1)k+2,…,jk View SourceB12=⎡⎣⎢⎢⎢⎢⎢A1,k+1A2,k+1⋮Ak,k+1A1,k+2A2,k+2⋮Ak,k+2⋯⋯⋱⋯A1,2kA2,2k⋮Ak,2k⎤⎦⎥⎥⎥⎥⎥.(8) \begin{align*} {\mathbf{B}}_{12} = \begin{bmatrix} A_{1, k +1} & A_{1, k + 2} & \cdots & A_{1, 2k}\\ A_{2, k +1} & A_{2, k + 2} & \cdots & A_{2, 2k}\\ \vdots & \vdots & \ddots & \vdots \\ A_{k, k +1} & A_{k, k +2} & \cdots & A_{k, 2k} \end{bmatrix}. \tag{8}\end{align*}
We then write the top-left n~×n~ An ⎡⎣⎢⎢⎢⎢⎢B11B21⋮Bn′,1B12B22⋮Bn′,2⋯⋯⋱⋯B1,n′B2,n′⋮Bn′,n′⎤⎦⎥⎥⎥⎥⎥.(9) \begin{align*} \begin{bmatrix} {\mathbf{B}}_{11} & {\mathbf{B}}_{12} & \cdots & {\mathbf{B}}_{1,n'}\\ {\mathbf{B}}_{21} & {\mathbf{B}}_{22} & \cdots & {\mathbf{B}}_{2,n'}\\ \vdots & \vdots & \ddots & \vdots \\ {\mathbf{B}}_{n',1} & {\mathbf{B}}_{n',2} & \cdots & {\mathbf{B}}_{n',n'} \end{bmatrix}. \tag{9}\end{align*}
But:=B12,B13,B23,…,B1,n′,⋯,Bn′−1,n′(10) \begin{equation*} {\mathbf{B}}_{\mathrm {ut}} : = {\mathbf{B}} _{12}, {\mathbf{B}}_{13}, {\mathbf{B}}_{23},\ldots , {\mathbf{B}}_{1,n'},\cdots , {\mathbf{B}}_{n'-1,n'} \tag{10}\end{equation*}
Bd:=B11,B22,…,Bn′,n′(11) \begin{equation*} {\mathbf{B}}_{\mathrm {d}} : = {\mathbf{B}} _{11}, {\mathbf{B}}_{22},\ldots , {\mathbf{B}}_{n',n'} \tag{11}\end{equation*}
Binary to
m m:=2k2 k×k But Bd [m] KT probability assignment. Apply KT sequential probability assignment for the two
m But Bd m x1,x2,…,xN N [m] j=0,1,2,…,N−1 View SourceqKT(i|xj):=qKT(Xj+1=i|Xj=xj)=Ni(xj)+1/2j+m/2for each i∈[m],(12) \begin{align*} q_{\mathrm {KT}}(i|x^{j}) & : = q_{\mathrm {KT}}(X_{j+1} = i| X^{j} = x^{j}) \\ &= \frac {N_{i}(x^{j}) + 1/2 }{j + m/2} \quad \text {for each } i \in [m], \tag{12}\end{align*}
where Xj:=(X1,…,Xj),xj:=(x1,x2,…,xj) Ni(xj):=∑jk=11{xk=i} i xj Adaptive arithmetic coding. With the KT sequential probability assignments, compress the two sequences
But Bd k=1 Bd But Encoding the remaining bits. The above process compressed the top-left
n~×n~ (n−n~)n~+(n−n~2) 2⌈logn⌉
Given the compressed graph sequence
Adaptive arithmetic decoding. With the KT sequential probability assignments defined in (12), decompress the two code sequences for
But Bd But Bd n′(n′−1)/2 n′ m m k2 k×k Adjacency matrix recovery. With the submatrices in
But Bd n~×n~ An Decoding the remaining bits. Recover the remaining
(n−n~)n~+(n−n~2) An
Remark 1 (Complexity):
The computational complexity and the space complexity of the proposed compressor are
To see this, we consider the time and space complexity of the encoder step by step. The steps of submatrix decomposition and binary to
Remark 2:
One can check that
Remark 3:
The orders in
Remark 4 (Laplace Probability Assignment):
As an alternative to the KT sequential probability assignment, one can also use the Laplace sequential probability assignment. Given an
\begin{align*} q_{ \mathrm {L}}(X_{j+1} = i| X^{j} = x^{j}) = \frac {N_{i}(x^{j}) + 1 }{j + m} \quad \text {for each } i \in [m]. \tag{13}\end{align*}
Both methods can be shown to be universal, while Laplace probability assignment has a much cleaner derivation. However, KT probability assignment produces a better empirical performance. For this reason, we keep both in the paper.B. Theoretical Performance
We now state the main result of this paper: the proposed compressor
Theorem 1 (Universality OverP1
For every
\begin{equation*} 0 < \delta < \epsilon , \quad k \le \sqrt { \delta \log n}, \quad \text {and } \quad k = \omega (1).\end{equation*}
Remark 5:
Recall that
It turns out that for
Theorem 2 (Universality OverP2
For every
Remark 6:
Any compressor universal over the class
The above results establish the universality of the proposed compressor over
Theorem 3 (Minimax Redundancy):
Let
\begin{align*} \frac {1}2\log \left ({\tfrac {\binom {n}{2}f(n)Q_{\mathrm {max}}}{\pi e}}\right )&\le {R}^{*}(\mathscr {P}_{3}(f(n),Q_{\mathrm {max}}))\\ &\le \frac {1}{e}(\log e)Q_{\mathrm {max}}\binom {n}{2}f(n).\end{align*}
Remark 7:
From Theorem 3, we can see that the lower bound scales as
In Section VI, we analyze the performance of the proposed compressor under the local weak convergence framework considered in [34]. It turns out that our proposed compressor achieves the optimal compression rate under the stronger universality criterion considered in that framework. This result requires a lot more definitions to introduce and we defer it to Theorem 5 in Section VI.
C. Empirical Performance
We implement the proposed universal graph compressor (UGC) in four widely used benchmark graph datasets: protein-to- protein interaction network (PPI) [46], LiveJournal friendship network (Blogcatalog) [47], Flickr user network (Flickr) [47], and YouTube user network (YouTube) [48]. The submatrix decomposition size
CSR: Compressed sparse row is a widely used sparse matrix representation format. In the experiment, we further optimize its default compressor exploiting the fact that the graph is simple and its adjacency matrix is symmetric with binary entries.
Ligra+: This is another powerful sparse matrix representation format [49], [50], which improves upon CSR using byte codes with run-length coding.
LZ: This is an implementation of the algorithm proposed in [22], which first transforms the two-dimensional adjacency matrix into a one-dimensional sequence using the Peano-Hilbert space-filling curve and then compresses the sequence using Lempel–Ziv 78 algorithm [15].
PNG: The adjacency matrix of the graph is treated as a grey-scaled image and the PNG lossless image compressor is applied.
Main Ideas in Establishing Universality
In this section, we establish Theorems 1 and 2 in Section II-B based on four intermediate propositions. We defer the proofs of the propositions to Section IV.
A. Graph Entropy
We first calculate the entropy of the (random) graph
Proposition 1 (Graph Entropy):
Let
Then
\begin{align*} H(A_{n}) &= {\binom{n }{ 2}} H(A_{12}|X_{1},X_{2}) (1+o(1)) \tag{14}\\ &= {\binom{n }{ 2}} {\mathbf{p}}^{T} h\bigl (f(n) {\mathbf{Q}}\bigr ) {\mathbf{p}}+ o\left ({n^{2}h\bigl (f(n)\bigr )}\right ). \tag{15}\end{align*}
In particular, when \begin{equation*} H(A_{n}) = {\binom{n }{ 2}} f(n)\log \left ({\frac {1}{f(n)}}\right )( {\mathbf{p}}^{T} {\mathbf{Q}} {\mathbf{p}} + o(1)). \tag{16}\end{equation*}
Remark 8:
In the regime
Remark 9:
Proposition 1 can be used to calculate the entropy of the graph for certain important regimes of
B. Asymptotic i.i.d. via Submatrix Decomposition
To compress the matrix
Proposition 2 (Submatrix Decomposition):
Let
\begin{align*} {\mathbf{B}}_{i_{1},j_{1}} &\stackrel {d}{=} {\mathbf{B}}_{i_{2},j_{2}}, \\ {\mathbf{B}}_{l_{1},l_{1}} &\stackrel {d}{=} {\mathbf{B}}_{l_{2},l_{2}}.\end{align*}
In addition, if \begin{equation*} \lim _{n\to \infty }\frac {H( {\mathbf{B}}_{\mathrm {ut}})}{\binom{n' }{ 2H( {\mathbf{B}}_{12})}} = 1. \tag{17}\end{equation*}
Remark 10:
In Proposition 2, we provide a more general result than what we need to prove Theorem 1. In Theorem 1, the range of
\begin{equation*} 0 < \delta < \epsilon , \quad k \le \sqrt { \delta \log n}, \quad \text {and } \quad k = \omega (1),\end{equation*}
while in Proposition 2, we show the asymptotic i.i.d property for a wider range Remark 11:
Proposition 2 implies that any probability assignment that is universal for i.i.d. sequences may be used to compress the blocks, provided that the compression length analysis can be expended to asymptotically i.i.d. sequences as in Propositions 3 and 4. The reason we choose to use the KT/Laplace probability assignment is that it is known to achieve the minimax redundancy and lead to better finite-length performance as compared to, for example, Lempel–Ziv coding which while still being universal incurs larger redundancy. Moreover, the KT-based approach leads to better empirical performance, as observed in Table II.
C. Length Analysis for Correlated Sequences
Thanks to the asymptotic i.i.d. property of the submatrix decomposition, we hope to compress these submatrices as if they are independent using a Laplace probability assignment (which, recall, is universal for the class of all
Proposition 3 (Laplace Probability Assignment for Correlated Sequence):
Consider arbitrarily correlated
\begin{equation*} q_{ \mathrm {L}}(z^{N}) : =\frac {N_{1}!N_{2}!\cdots N_{m}!}{N!}\cdot \frac {1}{\binom{N+m-1 }{ m-1}} \tag{18}\end{equation*}
with \begin{equation*} \mathsf {E}[\ell _{ \mathrm {L}}(Z^{N})] \le m\log (2eN) + N H(Z_{1})+2. \tag{19}\end{equation*}
We provide a similar result for the KT probability assignment.
Proposition 4 (KT Probability Assignment for Correlated Sequence):
Consider arbitrarily correlated
\begin{equation*} q_{\mathrm {KT}}(z^{N}) = \frac {(2N_{1} -1)!!(2N_{2} -1)!!\cdots (2N_{m} -1)!!}{m(m+2)\cdots (m+2N-2)} \tag{20}\end{equation*}
with \begin{align*}& \mathsf {E}[\ell _{\mathrm {KT}}(Z^{N})] \\ &\le \tfrac {m}{2}\log \left ({e\left({1+\tfrac {2N}{m}}\right)}\right )+\tfrac {1}2\log (\pi N)+NH(Z_{1})+2. \tag{21}\end{align*}
D. Proof of Theorem 1
To prove Theorem 1, we first state a technical lemma, the proof of which is deferred to Section IV-A.
Lemma 1:
Let
We have
\begin{equation*} H(A_{12})=h(f(n) \mathbf {p}^{T}\mathbf {Q}\mathbf {p}), \tag{22}\end{equation*}
and \begin{equation*} H(A_{12}|X_{1},X_{2})= {\mathbf{p}}^{T} h\bigl (f(n) {\mathbf{Q}}\bigr ) {\mathbf{p}}. \tag{23}\end{equation*}
\begin{equation*} h(f(n) \mathbf {p}^{T}\mathbf {Q}\mathbf {p})=\Theta ( {\mathbf{p}}^{T} h\bigl (f(n) {\mathbf{Q}}\bigr ) {\mathbf{p}}), \tag{24}\end{equation*}
\begin{equation*} h(f(n) \mathbf {p}^{T}\mathbf {Q}\mathbf {p})=(1+o(1)) {\mathbf{p}}^{T} h\bigl (f(n) {\mathbf{Q}}\bigr ) {\mathbf{p}}. \tag{25}\end{equation*}
Proof of Theorem 1:
We will prove the universality of
We use the bound in Proposition 3 to establish the upper bound on the length of the code. Recall that here we compress the diagonal submatrices
\begin{align*} &\frac { \mathsf {E}(\ell (C_{k}(A_{n})))}{H(A_{n})} \\ &= \frac { \mathsf {E}(\ell _{ \mathrm {L}}( {\mathbf{B}}_{\mathrm {ut}})) + \mathsf {E}(\ell _{ \mathrm {L}}( {\mathbf{B}}_{\mathrm {d}}))+ \mathsf {E}(2N_{r}\lceil \log n\rceil )}{H(A_{n})} \\ &\le \frac {\binom{n' }{ 2H( {\mathbf{B}}_{12}) + 2^{k^{2}}\log \left ({2e{\binom{n' }{ 2}}}\right ) + n'H( {\mathbf{B}}_{11})}}{H(A_{n})} \\ &\;\;\;+ \frac {2^{k^{2}}\log (2en')+4+ \mathsf {E}(2N_{r}\lceil \log n\rceil )}{H(A_{n})} \\ &\stackrel {(a)}{\le } \frac {\binom{n' }{ 2H( {\mathbf{B}}_{12}) + 2^{k^{2}}\log \left ({en^{2}}\right ) + n H( {\mathbf{B}}_{11}) }}{H(A_{n})} \\ &\;\;\;+ \frac {2^{k^{2}}\log (2en)+4+ \mathsf {E}(2N_{r}\lceil \log n\rceil )}{H(A_{n})} \\ &\stackrel {(b)}{\le } \frac {\binom{n' }{ 2H( {\mathbf{B}}_{12}) + 2^{k^{2}}\log \left ({2e^{2}n^{3}}\right ) + nk^{2} H(A_{12})}}{H(A_{n})} \\ &\;\;\;+ \frac {4+ \mathsf {E}(2N_{r}\lceil \log n\rceil )}{H(A_{n})} \\ &= \frac {\binom{n' }{ 2H( {\mathbf{B}}_{12})}}{H(A_{n})} + \frac {2^{k^{2}}\log \left ({2e^{2}n^{3}}\right )+4}{H(A_{n})} \\ &\;\;\;+ \frac {nk^{2} H(A_{12})}{H(A_{n})}+\frac { \mathsf {E}(2N_{r}\lceil \log n\rceil )}{H(A_{n})}, \tag{26}\end{align*}
where in (a) we bound \begin{align*} \frac {2^{k^{2}} \log (2en^{3})+4}{H(A_{n})} = O\left ({\frac {n^{ \delta } \log n}{n^{ \epsilon } \log n}}\right ) = O\left ({n^{ \delta - \epsilon }}\right ) = o(1) \tag{27}\end{align*}
\begin{align*} \frac {n k^{2} H(A_{12})}{H(A_{n})} &\le \frac {n k^{2} H(A_{12})}{H(A_{n}|X^{n})} \\ & = \frac {n k^{2} H(A_{12})}{\binom{n }{ 2H(A_{12}|X_{1},X_{2})}} \\ &= O\left ({\frac {k^{2}}{n}}\right ) = o(1), \tag{28}\end{align*}
For the last term in (26), we have
\begin{align*} \frac { \mathsf {E}(2N_{r}\lceil \log n\rceil )}{H(A_{n})}&=\frac {f(n) \mathbf {p}^{T}\mathbf {Q}\mathbf {p}\left ({(n-\tilde {n})\tilde {n} + \binom {n-\tilde {n}}{2}}\right )2\lceil \log n\rceil }{H(A_{n})} \\ &\stackrel {(c)}{=}O\left ({\frac {knf(n)\log n}{\binom {n}{2}f(n)\log \frac {1}{f(n)}}}\right )=o(1), \tag{29}\end{align*}
where (c) follows because \begin{align*} \frac { \mathsf {E}(\ell (C_{k}(A_{n})))}{H(A_{n})} &\le \frac {\binom{n' }{ 2H( {\mathbf{B}}_{12})}}{H(A_{n})} + \frac {2^{k^{2}}\log \left ({2en^{3}}\right )+4}{H(A_{n})}\\ &+ \frac {nk^{2} H(A_{12})}{H(A_{n})}+\frac { \mathsf {E}(2N_{r}\lceil \log n\rceil )}{H(A_{n})} \\ &= 1 + o(1),\end{align*}
E. Proof of Theorem 2
Proof:
To establish the universality of
\begin{align*} & \frac{\mathrm{E}\left(\ell\left(C_1\left(A_n\right)\right)\right)}{H\left(A_n\right)} \\ & \leq \frac{2 \log (2 e N)+N H\left(A_{12}\right)+2}{H\left(A_n\right)} \\ & \leq \frac{2 \log (2 e N)+N H\left(A_{12}\right)+2}{H\left(A_n \mid X_1^n\right)} \\ & =\left(\frac{2 \log (2 e N)+N H\left(A_{12}\right)+2}{N H\left(A_{12}\right)}\right) \frac{H\left(A_{12}\right)}{H\left(A_{12} \mid X_1, X_2\right)} \\ & =\left(1+\frac{2 \log (2 e N)+2}{N h\left(f(n) \mathrm{p}^T \mathrm{Qp}\right)}\right) \frac{h\left(f(n) \mathrm{p}^T \mathrm{Qp}\right)}{\mathrm{p}^T h(f(n) \mathrm{Q}) \mathrm{p}} \\ & \stackrel{(a)}{=} 1+o(1) .\end{align*}
Here, (a) is justified by noting that Remark 12:
When
Proof of Propositions 1–4
A. Graph Entropy
In this section, we establish Proposition 1. Towards that goal, we state and prove a stronger result on the graph entropy in Lemma 2, which will also be useful for proof of Theorem 3 later. Proposition 1 will follow easily from Lemma 2. The proofs of Lemmas 1 and 2 are provided after the proof of Proposition 1.
Lemma 2 (Graph entropy):
Let
Then
\begin{align*} H(A_{n}) &= {\binom{n }{ 2}} H(A_{12}|X_{1},X_{2}) (1+o(1)) \tag{30}\\ &= {\binom{n }{ 2}} {\mathbf{p}}^{T} h\bigl (f(n) {\mathbf{Q}}\bigr ) {\mathbf{p}}+ o\left ({n^{2}h\bigl (f(n)\bigr )}\right ). \tag{31}\end{align*}
In particular, when
\begin{align*} H(A_{n})=&\binom {n}{2}f(n)\bigg (\log \left ({\frac {1}{f(n)}}\right ) \mathbf {p}^{T}\mathbf {Q}\mathbf {p}+ \mathbf {p}^{T}\mathbf {Q}\mathbf {p}\log e \\ +& \mathbf {p}^{T}\mathbf {Q^{*}}\mathbf {p}+o(1)\bigg ), \tag{32}\end{align*}
where When
\begin{align*} H(A_{n})\le &\binom {n}{2}f(n)\bigg (\log \left ({\frac {1}{f(n)}}\right ) \mathbf {p}^{T}\mathbf {Q}\mathbf {p}+ \mathbf {p}^{T}\mathbf {Q}\mathbf {p}\log e \\ &+ \mathbf {p}^{T}\mathbf {Q}\mathbf {p}\log \frac {1}{ \mathbf {p}^{T}\mathbf {Q}\mathbf {p}}+o(1) \bigg ), \tag{33}\end{align*}
and lower bounded as \begin{align*} H(A_{n})\ge &\binom {n}{2}f(n)\bigg (\log \left ({\frac {1}{f(n)}}\right ) \mathbf {p}^{T}\mathbf {Q}\mathbf {p}+ \mathbf {p}^{T}\mathbf {Q}\mathbf {p}\log e \\ &+ \mathbf {p}^{T}\mathbf {Q^{*}}\mathbf {p}+o(1) \bigg ). \tag{34}\end{align*}
Now, we are ready to prove Proposition 1, which is restated as follows.
Proposition 5 (Graph Entropy):
Let
Then
\begin{align*} H(A_{n}) &= {\binom{n }{ 2}} H(A_{12}|X_{1},X_{2}) (1+o(1)) \qquad\qquad\quad (14)\\ &= {\binom{n }{ 2}} {\mathbf{p}}^{T} h\bigl (f(n) {\mathbf{Q}}\bigr ) {\mathbf{p}}+ o\left ({n^{2}h\bigl (f(n)\bigr )}\right ). \qquad (15)\end{align*}
In particular, when \begin{equation*} H(A_{n}) = {\binom{n }{ 2}} f(n)\log \left ({\frac {1}{f(n)}}\right )( {\mathbf{p}}^{T} {\mathbf{Q}} {\mathbf{p}} + o(1)). \qquad (16)\end{equation*}
Proof of Proposition 1:
Given Lemma 2, it suffices to prove equation (16) in Proposition 1. We consider two different cases. Firstly, assume that
\begin{align*} H(A_{n})&=\binom {n}{2}f(n)\bigg (\log \left ({\frac {1}{f(n)}}\right ) \mathbf {p}^{T}\mathbf {Q}\mathbf {p}+ \mathbf {p}^{T}\mathbf {Q}\mathbf {p}\log e\\ &\;\;\;+ \mathbf {p}^{T}\mathbf {Q^{*}}\mathbf {p}+o(1)\bigg )\\ &={\binom{n }{ 2}} f(n)\log \left ({\frac {1}{f(n)}}\right )( {\mathbf{p}}^{T} {\mathbf{Q}} {\mathbf{p}} + o(1)).\end{align*}
because Finally, we establish Lemmas 1 and 2.
Proof of Lemma 1:
We note that
\begin{align*} & \mathsf {P}(A_{12}=1)\\ &=\sum _{1\le i,j\le L} \mathsf {P}(A_{12}=1,X_{1}=i,X_{2}=j)\\ &=\sum _{1\le i,j\le L} \mathsf {P}(A_{12}=1|X_{1}=i,X_{2}=j)P(X_{1}=i,X_{2}=j)\\ &=\sum _{1\le i,j\le L}f(n)Q_{ij}p_{i}p_{j}=f(n) \mathbf {p}^{T}\mathbf {Q}\mathbf {p}.\end{align*}
Therefore, \begin{align*} H(A_{12}|X_{1},X_{2})&=\sum _{i,j} H(A_{12}|X_{1} = i,X_{2} = j)p_{i} p_{j} \\ &\stackrel {(a)}{=}\sum _{i,j} h(f(n)Q_{ij})p_{i} p_{j}\\ &= {\mathbf{p}}^{T} h\bigl (f(n) {\mathbf{Q}}\bigr ) {\mathbf{p}},\end{align*}
To see that
Now, consider the case of
\begin{align*} h(f(n) \mathbf {p}^{T}\mathbf {Q}\mathbf {p})=&f(n)\bigg (\log \left ({\frac {1}{f(n)}}\right ) \mathbf {p}^{T}\mathbf {Q}\mathbf {p}+ \mathbf {p}^{T}\mathbf {Q}\mathbf {p}\log e \\ &+\mathbf {p}^{T}\mathbf {Qp}\log \frac {1}{ \mathbf {p}^{T}\mathbf {Q}\mathbf {p}}+o(1)\bigg ), \tag{35}\end{align*}
and \begin{align*} {\mathbf{p}}^{T} h\bigl (f(n) {\mathbf{Q}}\bigr ) {\mathbf{p}}= &f(n)\bigg (\log \left ({\frac {1}{f(n)}}\right ) \mathbf {p}^{T}\mathbf {Q}\mathbf {p}+ \mathbf {p}^{T}\mathbf {Q}\mathbf {p}\log e \\ &+\mathbf {p}^{T}\mathbf {Q^{*}p}+o(1)\bigg ), \tag{36}\end{align*}
\begin{align*} &h(f(n) \mathbf {p}^{T}\mathbf {Q}\mathbf {p})- {\mathbf{p}}^{T} h\bigl (f(n) {\mathbf{Q}}\bigr ) {\mathbf{p}}\\ &=f(n)\left ({\mathbf {p}^{T}\mathbf {Qp}\log \frac {1}{ \mathbf {p}^{T}\mathbf {Q}\mathbf {p}}-\mathbf {p}^{T}\mathbf {Q^{*}p}+o(1)}\right )\\ &\stackrel {(b)}{=}o(h(f(n) \mathbf {p}^{T}\mathbf {Q}\mathbf {p})),\end{align*}
Proof of Lemma 2:
Note that
\begin{align*} H(A_{n}) &= H(A_{n}|X^{n}) + I(X^{n};A_{n}) \\ &= {\binom{n }{ 2}}H(A_{12}|X_{1},X_{2}) + I(X^{n};A_{n}) \tag{37}\\ &= {\binom{n }{ 2}} {\mathbf{p}}^{T} h\bigl (f(n) {\mathbf{Q}}\bigr ) {\mathbf{p}}+ I(X^{n};A_{n}), \tag{38}\end{align*}
where the last equality follows by Lemma 1 and the fact that all the \begin{align*} h(f(n))&=f(n)\log \frac {1}{f(n)}+(1-f(n))\log \frac {1}{1-f(n)}\\ &=\Theta (1)=\Theta \left ({f(n)\log \frac {1}{f(n)}}\right )\end{align*}
\begin{align*} h(f(n))&=f(n)\log \frac {1}{f(n)}+(1-f(n))\log \frac {1}{1-f(n)}\\ &=f(n)\log \frac {1}{f(n)}(1-f(n))\frac {f(n)}{1-f(n)}\\ &=f(n)\log \frac {1}{f(n)}(1+o(1))\end{align*}
\begin{equation*} H(A_{n})= {\binom{n }{ 2}} {\mathbf{p}}^{T} h\bigl (f(n) {\mathbf{Q}}\bigr ) {\mathbf{p}}+ o\left ({n^{2}f(n)\log \frac {1}{f(n)}}\right ).\end{equation*}
For
\begin{align*} 0 \le I(X^{n};A_{n}) &\le H(X^{n}) = n H(X_{1}) \\ &\le n \log L=o\left ({n^{2}f(n)\log \frac {1}{f(n)}}\right ), \tag{39}\end{align*}
which shows that \begin{align*} H(A_{n}) &= {\binom{n }{ 2}} {\mathbf{p}}^{T} h\bigl (f(n) {\mathbf{Q}}\bigr ) {\mathbf{p}}+ o\left ({n^{2} }\right )\\ &={\binom{n }{ 2}} {\mathbf{p}}^{T} h\bigl (f(n) {\mathbf{Q}}\bigr ) {\mathbf{p}}+ o\left ({n^{2}f(n)\log \frac {1}{f(n)}}\right ).\end{align*}
Next, consider the case when
\begin{align*} & {\mathbf{p}}^{T} h\bigl (f(n) {\mathbf{Q}}\bigr ) {\mathbf{p}} \\ &= f(n)\bigg (\log \left ({\frac {1}{f(n)}}\right ) \mathbf {p}^{T}\mathbf {Q}\mathbf {p}+ \mathbf {p}^{T}\mathbf {Q}\mathbf {p}\log e \\ &+\mathbf {p}^{T}\mathbf {Q^{*}p}+o(1)\bigg ) \\ &\stackrel {(a)}{=} f(n)\left ({\log \left ({\frac {1}{f(n)}}\right ) \mathbf {p}^{T}\mathbf {Q}\mathbf {p}}\right )(1+o(1)), \tag{40}\end{align*}
where (a) follows since Since
\begin{align*} I(X^{n};A_{n}) &\le H(X^{n}) = n H(X_{1}) \\ &\le n \log L=o\left ({f(n)\log \frac {1}{f(n)}n^{2}}\right ), \tag{41}\end{align*}
which proves (31). Substituting (40) and (41) into (38) yields \begin{align*} H(A_{n})=&\binom {n}{2}f(n)\bigg (\log \left ({\frac {1}{f(n)}}\right ) \mathbf {p}^{T}\mathbf {Q}\mathbf {p}+ \mathbf {p}^{T}\mathbf {Q}\mathbf {p}\log e\\ &+ \mathbf {p}^{T}\mathbf {Q^{*}}\mathbf {p}+o(1)\bigg ).\end{align*}
Finally, consider the case when
\begin{equation*} H(A_{n}|X^{n}) \le H(A_{n}) \le {\binom{n }{ 2}} H(A_{12}). \tag{42}\end{equation*}
By Lemma 1, we know that \begin{align*} {\binom{n }{ 2}} {\mathbf{p}}^{T} h(f(n) {\mathbf{Q}}) {\mathbf{p}}\le H(A_{n}) \le {\binom{n }{ 2}} h\left ({f(n) {\mathbf{p}}^{T} {\mathbf{Q}} {\mathbf{p}} }\right ). \tag{43}\end{align*}
\begin{align*} &{\binom{n }{ 2}} h\left ({f(n) {\mathbf{p}}^{T} {\mathbf{Q}} {\mathbf{p}} }\right ) \\ &=\binom {n}{2}f(n)\bigg (\log \left ({\frac {1}{f(n)}}\right ) \mathbf {p}^{T}\mathbf {Q}\mathbf {p}+ \mathbf {p}^{T}\mathbf {Q}\mathbf {p}\log e \\ &+\mathbf {p}^{T}\mathbf {Qp}\log \frac {1}{ \mathbf {p}^{T}\mathbf {Q}\mathbf {p}}+o(1)\bigg ). \tag{44}\end{align*}
\begin{align*} &\binom {n}{2}\mathbf {p^{T}}h(f(n)\mathbf {Q})\mathbf {p} \\ &=\binom {n}{2}f(n)\bigg (\log \left ({\frac {1}{f(n)}}\right ) \mathbf {p}^{T}\mathbf {Q}\mathbf {p}+ \mathbf {p}^{T}\mathbf {Q}\mathbf {p}\log e \\ &+\mathbf {p}^{T}\mathbf {Q^{*}p}+o(1)\bigg ), \tag{45}\end{align*}
\begin{align*} &{\binom{n }{ 2}} h\left ({f(n) {\mathbf{p}}^{T} {\mathbf{Q}} {\mathbf{p}} }\right )-{\binom{n }{ 2}} {\mathbf{p}}^{T} h(f(n) {\mathbf{Q}}) {\mathbf{p}}\\ &= {\binom{n }{ 2}} f(n)\left ({ \mathbf {p}^{T}\mathbf {Q}\mathbf {p}\log \frac {1}{ \mathbf {p}^{T}\mathbf {Q}\mathbf {p}}- \mathbf {p}^{T}\mathbf {Q^{*}}\mathbf {p}+o(1)}\right )\\ &\stackrel {(a)}{=}o\left ({n^{2} f(n)\log \frac {1}{f(n)}}\right ),\end{align*}
B. Asymptotic i.i.d. via Submatrix Decomposition
We first invoke a known property of stochastic block models (see, for example, [55], [56]). We include the proof here for completeness.
Lemma 3 (Exchangeability of SBM):
Let
\begin{equation*} A_{n} \stackrel {d}{=} \pi (A_{n}). \tag{46}\end{equation*}
Proof:
Let
\begin{align*} & \mathsf {P}(A_{n} = a_{n}) \\ &= \sum _{x^{n} \in [L]^{n}} \mathsf {P}(A_{n} = a_{n},X^{n} = x^{n})\\ &= \sum _{x^{n} \in [L]^{n}} \mathsf {P}(A_{n} = a_{n} | X^{n} = x^{n}) \prod _{i=1}^{n} \mathsf {P}(X_{i} = x_{i})\\ &\stackrel {(a)}{=} \sum _{x^{n} \in [L]^{n}} \prod _{\substack {i,j\\ 1 \le i < j \le n}} \mathsf {P}(A_{ij} = a_{ij}|X_{i} = x_{i}, X_{j} = x_{j}) \\ &\hspace {5em}\cdot \prod _{i=1}^{n} \mathsf {P}(X_{\pi (i)} = x_{i})\\ &\stackrel {(b)}{=} \sum _{x^{n} \in [L]^{n}}\prod _{\substack {i,j\\ 1 \le i < j \le n}} (W_{x_{i},x_{j}})^{a_{ij}}(1-W_{x_{i},x_{j}})^{1-a_{ij}} \\ &\hspace {5em}\cdot \prod _{i=1}^{n} \mathsf {P}(X_{\pi (i)} = x_{i})\\ &\stackrel {(c)}{=} \sum _{x^{n} \in [L]^{n}}\! \prod _{\substack {i,j\\ 1 \le i < j \le n}} \mathsf {P}(A_{\pi (i),\pi (j)} \!=\! a_{ij}|X_{\pi (i)} \!=\! x_{i}, X_{\pi (j)} = x_{j}) \\ &\hspace {5em}\cdot \prod _{i=1}^{n} \mathsf {P}(X_{\pi (i)} = x_{i}) \\ &{=} \sum _{x^{n} \in [L]^{n}} \mathsf {P}(\pi (A_{n}) = a_{n}, \pi (X^{n}) = x^{n})\\ &= \mathsf {P}(\pi (A_{n}) = a_{n}),\end{align*}
where \begin{align*} & \mathsf {P}(A_{ij} = a_{ij}|X_{i} = x_{i}, X_{j} = x_{j}) \\ &= \begin{cases} W_{x_{i},x_{j}} & \text {if } a_{ij} = 1\\ 1-W_{x_{i},x_{j}} & \text {if } a_{ij} = 0 \end{cases} \tag{47}\\ &= (W_{x_{i},x_{j}})^{a_{ij}}(1-W_{x_{i},x_{j}})^{1-a_{ij}}. \tag{48}\end{align*}
Now we are ready to establish Proposition 2, which is restated as follows.
Proposition 6 (Submatrix Decomposition):
Let
\begin{align*} {\mathbf{B}}_{i_{1},j_{1}} &\stackrel {d}{=} {\mathbf{B}}_{i_{2},j_{2}}, \\ {\mathbf{B}}_{l_{1},l_{1}} &\stackrel {d}{=} {\mathbf{B}}_{l_{2},l_{2}}.\end{align*}
In addition, if \begin{equation*} \lim _{n\to \infty }\frac {H( {\mathbf{B}}_{\mathrm {ut}})}{\binom{n' }{ 2H( {\mathbf{B}}_{12})}} = 1. \qquad (17)\end{equation*}
Proof of Proposition 2:
For any
\begin{align*} \pi _{1}(x) =\begin{cases} x + (i_{2}-i_{1})k & \text {for } (i_{1}-1)k + 1 \leq x \leq i_{1}k\\ x + (j_{2}-j_{1})k & \text {for } (j_{1}-1)k + 1 \leq x \leq j_{1}k \end{cases}\end{align*}
and the remaining \begin{equation*} \pi _{2}(x) = \begin{cases} x + (l_{2}-l_{1})k & \text {for } (l_{1}-1)k + 1 \leq x \leq l_{1}k \end{cases}\end{equation*}
Now, clearly
\begin{equation*} \limsup _{n \to \infty } \frac {H( {\mathbf{B}}_{\mathrm {ut}})}{\binom{n' }{ 2H( {\mathbf{B}}_{12})}} \le 1. \tag{49}\end{equation*}
Moreover, we have \begin{align*} \frac {H( {\mathbf{B}}_{\mathrm {ut}})}{\binom{n' }{ 2H( {\mathbf{B}}_{12})}} \ge \frac {\binom{n }{ 2 \left ({ {\mathbf{p}}^{T} h(f(n) {\mathbf{Q}}) {\mathbf{p}}- \frac {2 k h(f(n) {\mathbf{p}}^{T} {\mathbf{Q}} {\mathbf{p}} ) }{n-1}}\right )}}{\binom{n' }{ 2H( {\mathbf{B}}_{12})}}. \tag{50}\end{align*}
f(n)=Θ(1) View SourceH(B12)≤(a)H(B12|X2k1)+H(X2k1)=H(B12|X2k1)+2kH(p)=(b)k2H(A1,k+1|X1,Xk+1)+2kH(p)≤(c)k2(pTh(Q)p+2logLk),(51) \begin{align*} H( {\mathbf{B}}_{12}) &\stackrel {(a)}{\le } H( {\mathbf{B}}_{12}|X_{1}^{2k}) + H(X_{1}^{2k}) \\ &= H( {\mathbf{B}}_{12}|X_{1}^{2k}) + 2k H( {\mathbf{p}}) \\ &\stackrel {(b)}{=} k^{2} H(A_{1,k+1}|X_{1},X_{k+1}) + 2k H( {\mathbf{p}}) \\ &\stackrel {(c)}{\le } k^{2}\left ({ {\mathbf{p}}^{T} h( {\mathbf{Q}}) {\mathbf{p}}+ 2 \frac {\log L}{k}}\right ), \tag{51}\end{align*}
where (a) follows from the chain rule, (b) follows since all elements of the matrix B12 X1,⋯,X2k H(But)(n′2H(B12))≥(n2(pTh(Q)p−2kh(pTQp)n−1))(n′2k2(pTh(Q)p+2logLk)).(52) \begin{equation*} \frac {H( {\mathbf{B}}_{\mathrm {ut}})}{\binom{n' }{ 2H( {\mathbf{B}}_{12})}} \ge \frac {\binom{n }{ 2\left ({ {\mathbf{p}}^{T} h( {\mathbf{Q}}) {\mathbf{p}}- \frac {2k h( {\mathbf{p}}^{T} {\mathbf{Q}} {\mathbf{p}} )}{n-1}}\right )}}{\binom{n' }{ 2k^{2}\left ({ {\mathbf{p}}^{T} h( {\mathbf{Q}}) {\mathbf{p}}+ 2 \frac {\log L}{k}}\right )}}. \tag{52}\end{equation*}
k=o(n),k=ω(1) (n′2)k2∼(n2) lim infn→∞H(But)(n′2H(B12))≥1,(53) \begin{equation*} \liminf _{n \to \infty } \frac {H( {\mathbf{B}}_{\mathrm {ut}})}{\binom{n' }{ 2H( {\mathbf{B}}_{12})}} \ge 1, \tag{53}\end{equation*}
f(n)=Ω(1n2),f(n)=o(1): B12 k2 View SourceH(B12)≤k2h(A1,k+1)=k2h(f(n)pTQp).(54) \begin{equation*} H( {\mathbf{B}}_{12}) \le k^{2} h(A_{1,k+1}) = k^{2} h\left ({f(n) {\mathbf{p}}^{T} {\mathbf{Q}} {\mathbf{p}} }\right ). \tag{54}\end{equation*}
Plugging this into the RHS of (50) then yields H(But)(n′2H(B12))≥(n2(pTh(f(n)Q)p−2kh(f(n)pTQp)n−1))(n′2k2h(f(n)pTQp)).(55) \begin{align*} &\frac {H( {\mathbf{B}}_{\mathrm {ut}})}{\binom{n' }{ 2H( {\mathbf{B}}_{12})}} \ge \frac {\binom{n }{ 2\left ({ {\mathbf{p}}^{T} h(f(n) {\mathbf{Q}}) {\mathbf{p}}- \frac {2k h(f(n) {\mathbf{p}}^{T} {\mathbf{Q}} {\mathbf{p}} )}{n-1}}\right )}}{\binom{n' }{ 2k^{2} h\left ({f(n) {\mathbf{p}}^{T} {\mathbf{Q}} {\mathbf{p}} }\right )}}. \tag{55}\end{align*}
f(n)=o(1) pTh(f(n)Q)p=(1+o(1))h(f(n)pTQp).(56) \begin{equation*} {\mathbf{p}}^{T} h(f(n) {\mathbf{Q}}) {\mathbf{p}}=(1+o(1)) h\left ({f(n) {\mathbf{p}}^{T} {\mathbf{Q}} {\mathbf{p}} }\right ). \tag{56}\end{equation*}
k=o(n) (n′2)k2∼(n2) lim infn→∞H(But)(n′2H(B12))≥1,(57) \begin{equation*} \liminf _{n \to \infty } \frac {H( {\mathbf{B}}_{\mathrm {ut}})}{\binom{n' }{ 2H( {\mathbf{B}}_{12})}} \ge 1, \tag{57}\end{equation*}
C. Length of the Laplace Probability Assignment
In this section, we prove Proposition 3, which is restated as follows.
Proposition 7 (Laplace Probability Assignment for Correlated Sequence):
Consider arbitrarily correlated
\begin{equation*} q_{ \mathrm {L}}(z^{N}) : =\frac {N_{1}!N_{2}!\cdots N_{m}!}{N!}\cdot \frac {1}{\binom{N+m-1 }{ m-1}} \qquad (18)\end{equation*}
with \begin{equation*} \mathsf {E}[\ell _{ \mathrm {L}}(Z^{N})] \le m\log (2eN) + N H(Z_{1})+2. \qquad (19)\end{equation*}
Proof of Proposition 3:
The joint probability of Laplace probability assignment given in equation (18) is a classic result. Nonetheless, we provide the derivation of (18) in Appendix B.
Now, we move on to prove the expected length upper bound (19). Let us first elaborate on the relation between probability assignment and compression length. In Algorithm 1, the terms
\begin{align*} \sum _{j=0}^{N-1}\log (q(x_{j+1}|x^{j})) \!=\! \log \left ({\prod _{j=0}^{N-1} q(x_{j+1}|x^{j})}\right ) \!=\! \log (q(x^{N})). \tag{58}\end{align*}
The compression output length of Algorithm 1 is Now we analyze the compression length of the Laplace compressor for the sequence
\begin{align*} &\log \frac {1}{q_{ \mathrm {L}}(z^{N})} \\ &= \log \frac {\theta _{1}^{N_{1}}\theta _{2}^{N_{2}}\cdots \theta _{m}^{N_{m}}}{q_{ \mathrm {L}}(z^{N})} + \log \frac {1}{\theta _{1}^{N_{1}}\theta _{2}^{N_{2}}\cdots \theta _{m}^{N_{m}}} \\ &= \log {\binom{N+m-1 }{ m-1}} + \log \left ({\tfrac {N!}{N_{1}!N_{2}!\cdots N_{m}!}\theta _{1}^{N_{1}}\theta _{2}^{N_{2}}\cdots \theta _{m}^{N_{m}}}\right ) \\ &\;\;\;+ \log \frac {1}{\theta _{1}^{N_{1}}\theta _{2}^{N_{2}}\cdots \theta _{m}^{N_{m}}} \\ &\stackrel {(a)}{\le } \log {\binom{N+m-1 }{ m-1}} + \log \frac {1}{\theta _{1}^{N_{1}}\theta _{2}^{N_{2}}\cdots \theta _{m}^{N_{m}}} \\ &\stackrel {(b)}{\le } (m-1)\log \left ({e\left ({\frac {N}{m-1}+1}\right )}\right ) + \log \frac {1}{\theta _{1}^{N_{1}}\theta _{2}^{N_{2}}\cdots \theta _{m}^{N_{m}}} \\ &\le m \log (2eN) + \sum _{i=1}^{m} N_{i} \log \frac {1}{\theta _{i}}, \tag{59}\end{align*}
where (a) follows since \begin{align*} & \mathsf {E}\left [{ \log \frac {1}{q_{ \mathrm {L}}(Z^{N})} }\right ] \\[-2.5pt] &\le m \log (2e N) + \sum _{i=1}^{m} \mathsf {E}[N_{i}] \log \frac {1}{\theta _{i}} \\[-2.5pt] &= m \log (2e N) + \sum _{i=1}^{m} \mathsf {E}\left [{\sum _{k=1}^{N} {{\mathsf {1}}}\{Z_{k} = i\}}\right ] \log \frac {1}{\theta _{i}} \tag{60}\\ &\stackrel {(c)}{=} m \log (2e N) + \sum _{i=1}^{m} \left ({\sum _{k=1}^{N} \mathsf {E}\left [{ {{\mathsf {1}}}\{Z_{k} = i\}}\right ]}\right )\log \frac {1}{\theta _{i}} \tag{61}\\[-2.5pt] &\stackrel {(d)}{=} m \log (2e N) + \sum _{i=1}^{m} N \mathsf {P}(Z_{1} = i)\log \frac {1}{\theta _{i}} \tag{62}\\[-2.5pt] &= m \log (2eN) + \sum _{i=1}^{m} N \theta _{i} \log \frac {1}{\theta _{i}} \\[-2.5pt] &= m \log (2eN) + N H(Z_{1}),\end{align*}
\begin{align*}& \mathsf {E}[\ell _{ \mathrm {L}}(Z^{N})] \\ &\le \mathsf {E} \left [{ \log \frac {1}{q_{ \mathrm {L}}(Z^{N})} }\right ]+2 \le m\log (2eN) + N H(Z_{1})+2\end{align*}
D. Length of the KT Probability Assignment
To prove Proposition 4, we first state a technical lemma.
Lemma 4:
For any integer
\begin{equation*}\frac {\binom {N}{N_{1},N_{2}\cdots N_{m}}\theta _{1}^{N_{1}}\cdots \theta _{m}^{N_{m}}}{\binom {2N}{2N_{1},2N_{2}\cdots 2N_{m}}\theta _{1}^{2N_{1}}\cdots \theta _{m}^{2N_{m}}}\ge 1,\end{equation*}
where We defer the proof of Lemma 4 to Appendix A.
Remark 13:
Equivalently, consider an urn containing a known number of balls with
Now, we are ready to Proposition 4, which is restated as follows.
Proposition 8 (KT Probability Assignment for Correlated Sequence):
Consider arbitrarily correlated
\begin{equation*} q_{\mathrm {KT}}(z^{N}) = \frac {(2N_{1} -1)!!(2N_{2} -1)!!\cdots (2N_{m} -1)!!}{m(m+2)\cdots (m+2N-2)} \qquad (20)\end{equation*}
with \begin{align*}& \mathsf {E}[\ell _{\mathrm {KT}}(Z^{N})] \\ &\le \tfrac {m}{2}\log \left ({e\left({1+\tfrac {2N}{m}}\right)}\right )+\tfrac {1}2\log (\pi N)+NH(Z_{1})+2. \qquad (21)\end{align*}
Proof of Proposition 4:
The joint probability of KT probability assignment given in equation (20) is a classic result. Nonetheless, we provide the derivation of (20) in Appendix B.
Now, we move on to prove the expected length upper bound (21). In this proof, we define a generalized form of the factorial function. Let
\begin{align*} &m(m+2)\cdots (m+2N-2)\\ &=2^{N} \left ({\frac {m}{2}}\right ) \left ({\frac {m+2}{2}}\right )\cdots \left ({\frac {m+2N-2}{2}}\right )\\ &=2^{N}\frac {\left ({\frac {m}{2}+N-1}\right )!}{\left ({\frac {m}{2}-1}\right )!}.\end{align*}
Therefore we can rewrite the KT probability assignment in (20) as \begin{align*} &q_{\mathrm {KT}}(z^{N})\\[4pt]&=\frac {\left({\frac {m}{2}-1}\right)!}{2^{N}\left({\frac {m}{2}+N-1}\right)!}\frac {\binom {2N}{N}}{\binom {2N}{N}}\prod _{i=1}^{m} \frac {(2N_{i})!}{N_{i} ! 2^{N_{i}}}\\[4pt] &=\frac {\left({\frac {m}{2}-1}\right)!}{2^{N}\left({\frac {m}{2}+N-1}\right)!} \binom {2N}{N}N! \frac {N!}{(2N)!}\prod _{i=1}^{m} \frac {(2N_{i})!}{N_{i} !2^{N_{i}}} \\[4pt] &\stackrel {(a)}{\ge }\frac {\left ({\frac {m}{2}-1}\right )!\binom {2N}{N}}{4^{N} \left({N+\frac {m}{2}-\frac {1}{2}}\right)^{\frac {m-1}{2}}}\frac {N!}{(2N)!}\prod _{i=1}^{m} \frac {(2N_{i})!}{N_{i} !}\\[4pt] &\stackrel {(b)}{=}\frac {\theta _{1}^{N_{1}}\cdots \theta _{m}^{N_{m}}\left({\frac {m}{2}-1}\right)!\binom {2N}{N}}{4^{N} \left({N+\frac {m}{2}-\frac {1}{2}}\right)^{\frac {m-1}{2}}}\frac {\binom {N}{N_{1},N_{2}\cdots N_{m}}\theta _{1}^{N_{1}}\cdots \theta _{m}^{N_{m}}}{\binom {2N}{2N_{1},2N_{2}\cdots 2N_{m}}\theta _{1}^{2N_{1}}\cdots \theta _{m}^{2N_{m}}},\end{align*}
\begin{align*} &\log \frac {1}{q_{\mathrm {KT}}(z^{N})}\\[-2.5pt]&\le \log {\frac {1}{\theta _{1}^{N_{1}}\cdots \theta _{m}^{N_{m}}}}+\log {\frac {4^{N} \left({N+\frac {m}{2}-\frac {1}{2}}\right)^{\frac {m-1}{2}}}{\left({\frac {m}{2}-1}\right)!\binom {2N}{N}}}\\[-2.5pt] &=\log {\frac {1}{\theta _{1}^{N_{1}}\cdots \theta _{m}^{N_{m}}}}+\frac {m-1}{2}\log {\left ({N+\frac {m-1}{2}}\right )}\\[-2.5pt]&\;\;\;+\log {\frac {4^{N}}{\binom {2N}{N}}}-\log {\left ({\frac {m}{2}-1}\right )!}\\[-2.5pt] &\stackrel {(a)}{\le }\log {\frac {1}{\theta _{1}^{N_{1}}\cdots \theta _{m}^{N_{m}}}}+\frac {m-1}{2}\log {\left ({N+\frac {m-1}{2}}\right )}\\[-2.5pt]&\;\;\;+\log {\frac {4^{N}}{\binom {2N}{N}}}-\left ({\frac {m}{2}-1}\right )\log {\left({\frac {\frac {m}{2}-1}{e}}\right)}\\[-2.5pt] &\stackrel {(b)}{\sim }\log {\frac {1}{\theta _{1}^{N_{1}}\cdots \theta _{m}^{N_{m}}}}+\frac {m-1}{2}\log {\left ({N+\frac {m-1}{2}}\right )}\\[-2.5pt]&\;\;\;+\log {\sqrt {\pi N}}-\left ({\frac {m}{2}-1}\right )\log {\left ({\frac {\frac {m}{2}-1}{e}}\right )}\\[-2.5pt] &\sim \frac {m}{2}\log {\frac {e\left({\frac {m}{2}+N}\right)}{m/2}}+\log {\sqrt {\pi N}}+\log {\frac {1}{\theta _{1}^{N_{1}}\cdots \theta _{m}^{N_{m}}}}\\[-2.5pt] &=\frac {m}{2}\log \left ({e\left({1+\tfrac {2N}{m}}\right)}\right )+\frac {1}2\log (\pi N)+\sum _{i=1}^{m} N_{i} \log {\frac {1}{\theta _{i}}},\end{align*}
\begin{align*} & \mathsf {E}\left [{\log \frac {1}{q_{\mathrm {KT}}(z^{N})}}\right ]\\ &\le \frac {1}{2}m\log \left ({e\left({1+\tfrac {2N}{m}}\right)}\right )+\frac {1}2\log (\pi N)+NH(Z_{1}).\end{align*}
\begin{align*} & \mathsf {E}[\ell _{\mathrm {KT}}(Z^{N})]\le \mathsf {E} \left [{\log \frac {1}{q_{\mathrm {KT}}(z^{N})}}\right ]+2\\ &\le \tfrac {m}{2}\log \left ({e\left({1+\tfrac {2N}{m}}\right)}\right )+\tfrac {1}2\log (\pi N)+NH(Z_{1})+2.\end{align*}
Minimax Redundancy Analysis
So far, we have proved the universality of our proposed algorithms. For this, we showed that the expected length of the proposed compressor matches the first-order term in the graph entropy. In this section, we study the redundancy of the proposed compressor
Theorem 4 (Minimax Redundancy):
Let
\begin{align*} \frac {1}2\log \left ({\tfrac {\binom {n}{2}f(n)Q_{\mathrm {max}}}{\pi e}}\right )&\le {R}^{*}(\mathscr {P}_{3}(f(n),Q_{\mathrm {max}}))\\ &\le \frac {1}{e}(\log e)Q_{\mathrm {max}}\binom {n}{2}f(n).\end{align*}
Towards that goal, we first state a proposition that upper bounds the redundancy of compressor
Proposition 9:
For every
If
f(n)=o(1) f(n)=Ω(1n2−ϵ) Ck View SourceE[ℓ(Ck(An))]−H(An)≤(n2)f(n)(pTQplog(1pTQp)−pTQ∗p)+o(n2f(n))=o(H(An)),(63) \begin{align*} & \mathsf {E}[\ell (C_{k}(A_{n}))]-H(A_{n}) \\ &\le \binom {n}{2}f(n)\left ({ \mathbf {p}^{T}\mathbf {Q}\mathbf {p}\log \left ({ \frac {1}{ \mathbf {p}^{T}\mathbf {Q}\mathbf {p}}}\right )-\mathbf {p}^{T}\mathbf {Q^{*}p}}\right ) \\ &\;\;\;+o(n^{2}f(n)) \tag{63}\\ &= o(H(A_{n})),\end{align*}
where Q∗ L×L (i,j) Qijlog(1Qij) Qij≠0 Qij=0 If
f(n)=Θ(1) Ck View SourceE(ℓ(Ck(An)))−H(An)≤H(p)n2k+o(n2k)=o(H(An)),(64) \begin{align*} \mathsf {E}(\ell (C_{k}(A_{n})))-H(A_{n}) &\le H(\mathbf {p})\frac {n^{2}}{k}+o\left ({\frac {n^{2}}{k}}\right ) \tag{64}\\ &= o(H(A_{n})),\end{align*}
where H(p)=∑Li=1pilog(1pi)
Because
Proof of Theorem 3:
Firstly, we prove the lower bound for the minimax redundancy. The proof essentially follows from the redundancy-capacity theorem [57]. To start with, we will define a vector
\begin{align*} & {\boldsymbol{\Theta }}(\mathrm {SBM}(n,L, {\mathbf{p}},f(n) {\mathbf{Q}}))\\ &=(L,p_{1},\ldots ,p_{L-1},Q_{11},\ldots ,Q_{1L},Q_{22},\ldots ,Q_{2L},\ldots ,Q_{LL}).\end{align*}
Notice that by our definition, \begin{align*} \mathcal {W}:=&\{ {\boldsymbol{\Theta }}(\mathrm {SBM}(n,L, {\mathbf{p}},f(n) {\mathbf{Q}})):\\ &\mathrm {SBM}(n,L, {\mathbf{p}},f(n) {\mathbf{Q}})\in \mathscr {P}_{3}(f(n),Q_{\mathrm {max}})\}\end{align*}
\begin{equation*}R^{*}_{n}(\mathscr {P}_{3}(f(n),Q_{\mathrm {max}}))=\sup _{\mu} I_{\mu} ( {\boldsymbol{\Theta }};A_{n}),\end{equation*}
We now move on to evaluate the mutual information
\begin{align*} I_{\nu} ( {\boldsymbol{\Theta }};A_{n})&=I_{\nu} (Q_{11};A_{n})\\ &=h(Q_{11})-h(Q_{11}|A_{n})\\ &\stackrel {(a)}{\ge }\log Q_{\mathrm {max}}-h(Q_{11}|\hat {Q}_{11})\\ &=\log Q_{\mathrm {max}}-h(Q_{11}-\hat {Q}_{11}|\hat {Q}_{11})\\ &\ge \log Q_{\mathrm {max}}-h(Q_{11}-\hat {Q}_{11})\\ &\stackrel {(b)}{\ge }\log Q_{\mathrm {max}}-\frac {1}2\log \left ({2\pi e\mathrm {Var}(Q_{11}-\hat {Q}_{11})}\right ),\end{align*}
where (a) follows since \begin{align*} &\mathrm {Var}(Q_{11}-\hat {Q}_{11}|Q_{11}=q)\\ &= \mathsf {E}\left [{\left ({\frac {K}{\binom {n}{2}f(n)}-Q_{11}}\right )^{2}\Biggr |Q_{11}=q}\right ]\\ &=\frac {1}{\binom {n}{2}^{2}(f(n))^{2}} \mathsf {E}\left [{\left ({K-\binom {n}{2}f(n)q}\right )^{2}\Biggr |Q_{11}=q}\right ]\\ &\stackrel {(c)}{=}\frac {\binom {n}{2}f(n)q(1-f(n)q)}{\binom {n}{2}^{2}(f(n))^{2}}\\ &=\frac {q(1-f(n)q)}{\binom {n}{2}f(n)},\end{align*}
\begin{align*} \mathrm {Var}(Q_{11}-\hat {Q}_{11})&= \mathsf {E}\left [{\frac {Q_{11}(1-f(n)Q_{11})}{\binom {n}{2}f(n)}}\right ]\\ &\le \frac { \mathsf {E}[Q_{11}]}{\binom {n}{2}f(n)}=\frac {Q_{\mathrm {max}}}{2\binom {n}{2}f(n)}.\end{align*}
\begin{align*} I_{\nu} ( {\boldsymbol{\Theta }};A_{n})&\ge \log Q_{\mathrm {max}}-\frac {1}2\log \left ({2\pi e\mathrm {Var}(Q_{11}-\hat {Q}_{11})}\right )\\ &\ge \log Q_{\mathrm {max}}-\frac {1}2\log \left ({\frac {Q_{\mathrm {max}}\pi e}{\binom {n}{2}f(n)}}\right )\\ &=\frac {1}2\log \left ({\frac {\binom {n}{2}f(n)Q_{\mathrm {max}}}{\pi e}}\right ),\end{align*}
Now, we prove the upper bound for the minimax redundancy. Let
\begin{align*} &R^{*}_{n}(\mathscr {P}_{3}(f(n),Q_{\mathrm {max}}))\\ &=\inf \limits _{C}\sup \limits _{(L,\mathbf {p},\mathbf {Q})\in \mathcal {S}(f(n),Q_{\mathrm {max}})}( \mathsf {E}[\ell (C(A_{n}))]-H(A_{n}))\\ &\le \sup \limits _{(L,\mathbf {p},\mathbf {Q})\in \mathcal {S}(f(n),Q_{\mathrm {max}})}( \mathsf {E}[\ell (C_{k}(A_{n}))]-H(A_{n}))\\ &\stackrel {(d)}{\le } \sup \limits _{(L,\mathbf {p},\mathbf {Q})\in \mathcal {S}(f(n),Q_{\mathrm {max}})}\binom {n}{2}f(n)\bigg ( \mathbf {p}^{T}\mathbf {Q}\mathbf {p}\log \frac {1}{ \mathbf {p}^{T}\mathbf {Q}\mathbf {p}}\\ &\hspace {9em}-\mathbf {p}^{T}\mathbf {Q^{*}p}\bigg )+o(n^{2}f(n)),\end{align*}
where (d) follows since \begin{align*} & \mathbf {p}^{T}\mathbf {Q}\mathbf {p}\log \frac {1}{ \mathbf {p}^{T}\mathbf {Q}\mathbf {p}}-\mathbf {p}^{T}\mathbf {Q^{*}p}\\ &=\sum _{i,j\in [L]}p_{i}p_{j}Q_{ij}\log \frac {1}{\sum _{k,l\in [L]}p_{k}p_{l}Q_{kl}}\\ &\;\;\;-\sum _{i,j\in [L]}p_{i}p_{j}Q_{ij}\log \frac {1}{Q_{ij}}\\ &=Q_{\mathrm {max}}\Bigg (\sum _{i,j\in [L]}p_{i}p_{j}\frac {Q_{ij}}{Q_{\mathrm {max}}}\log \frac {1}{\sum _{k,l\in [L]}p_{k}p_{l}Q_{kl}}\\ &\;\;\;-\sum _{i,j\in [L]}p_{i}p_{j}\frac {Q_{ij}}{Q_{\mathrm {max}}}\log \frac {1}{Q_{ij}}\Bigg )\\ &=Q_{\mathrm {max}}\Bigg (\sum _{i,j\in [L]}p_{i}p_{j}\frac {Q_{ij}}{Q_{\mathrm {max}}}\log \left ({\frac {1}{\sum _{k,l\in [L]}p_{k}p_{l}\frac {Q_{kl}}{Q_{\mathrm {max}}}}\frac {1}{Q_{\mathrm {max}}}}\right )\\ &\;\;\;-\sum _{i,j\in [L]}p_{i}p_{j}\frac {Q_{ij}}{Q_{\mathrm {max}}}\log \left ({\frac {Q_{\mathrm {max}}}{Q_{ij}}\frac {1}{Q_{\mathrm {max}}}}\right )\Bigg )\\ &=Q_{\mathrm {max}}\Bigg (\sum _{i,j\in [L]}p_{i}p_{j}\frac {Q_{ij}}{Q_{\mathrm {max}}}\log \frac {1}{\sum _{k,l\in [L]}p_{k}p_{l}\frac {Q_{kl}}{Q_{\mathrm {max}}}}\\ &\;\;\;-\sum _{i,j\in [L]}p_{i}p_{j}\frac {Q_{ij}}{Q_{\mathrm {max}}}\log \frac {Q_{\mathrm {max}}}{Q_{ij}}\Bigg )\\ &=Q_{\mathrm {max}}\left ({\mathbf {p}^{T}\mathbf {Q'p}\log \frac {1}{\mathbf {p}^{T}\mathbf {Q'p}}-\mathbf {p}^{T}\mathbf {(Q')^{*}p}}\right ),\end{align*}
\begin{equation*}Q_{\mathrm {max}}\left ({\mathbf {p}^{T}\mathbf {Q'p}\log \frac {1}{\mathbf {p}^{T}\mathbf {Q'p}}-\mathbf {p}^{T}\mathbf {(Q')^{*}p}}\right )\le Q_{\mathrm {max}}\frac {1}{e}\log e.\end{equation*}
Proof of Proposition 9:
We discuss the redundancy in two cases: (1)
First assume
\begin{align*} H(A_{n})\ge &\binom {n}{2}f(n)\bigg (\log \left ({\frac {1}{f(n)}}\right ) \mathbf {p}^{T}\mathbf {Q}\mathbf {p}+ \mathbf {p}^{T}\mathbf {Q}\mathbf {p}\log e \\ &+ \mathbf {p}^{T}\mathbf {Q^{*}}\mathbf {p}+o(1) \bigg ). \tag{65}\end{align*}
Now, we will upper bound the redundancy of
\begin{align*} \mathsf {E}[(\ell (C_{k}(A_{n}))]\le &{\binom{n' }{ 2}}H( {\mathbf{B}}_{12}) + 2^{k^{2}}\log \left ({2e^{2}n^{3}}\right ) \\ &+ (nk^{2} H(A_{12})+4)+ \mathsf {E}(2N_{r}\lceil \log n\rceil ). \tag{66}\end{align*}
We will now analyze each of these four terms separately. Firstly, we have \begin{align*} &\binom {n'}{2}H(\mathbf {B}_{12}) \le \binom {n'}{2}k^{2}H(A_{1,k+1}) \\ &=\binom {n'}{2}k^{2}h(f(n) \mathbf {p}^{T}\mathbf {Q}\mathbf {p}) \\ &\stackrel {(a)}{=}\binom {n}{2}f(n)\bigg (\left ({\log \frac {1}{f(n)}}\right ) \mathbf {p}^{T}\mathbf {Q}\mathbf {p}+ \mathbf {p}^{T}\mathbf {Q}\mathbf {p}\log e \\ &\;\;\;+ \mathbf {p}^{T}\mathbf {Q}\mathbf {p}\log \frac {1}{ \mathbf {p}^{T}\mathbf {Q}\mathbf {p}}+o(1)\bigg ), \tag{67}\end{align*}
\begin{equation*} 2^{k^{2}}\log \left ({2e^{2}n^{3}}\right )\le n^{\delta} \log (2e^{2}n^{3})=o(n^{2}f(n)). \tag{68}\end{equation*}
\begin{align*} &nk^{2}H(A_{12})+4\le (n\delta \log n)H(A_{12})+4 \\ &=(n\delta \log n)O\left ({f(n)\log \frac {1}{f(n)}}\right )+4=o(n^{2}f(n)). \tag{69}\end{align*}
\begin{equation*} \mathsf {E}(2N_{r}\lceil \log n\rceil )=O(knf(n)\log n)=o(n^{2}f(n)). \tag{70}\end{equation*}
\begin{align*} & \mathsf {E}(\ell (C_{k}(A_{n})))-H(A_{n}) \\ &\le \binom {n}{2}f(n)\bigg (\left ({\log \frac {1}{f(n)}}\right ) \mathbf {p}^{T}\mathbf {Q}\mathbf {p}+ \mathbf {p}^{T}\mathbf {Q}\mathbf {p}\log e \\ &\;\;\;+ \mathbf {p}^{T}\mathbf {Q}\mathbf {p}\log \frac {1}{ \mathbf {p}^{T}\mathbf {Q}\mathbf {p}}+o(1)\bigg )+o(n^{2}f(n)) \\ &\;\;\;-\binom {n}{2}f(n)\bigg (\log \left ({\frac {1}{f(n)}}\right ) \mathbf {p}^{T}\mathbf {Q}\mathbf {p}+ \mathbf {p}^{T}\mathbf {Q}\mathbf {p}\log e \\ &\;\;\;+ \mathbf {p}^{T}\mathbf {Q^{*}}\mathbf {p}+o(1) \bigg ) \\ &=\binom {n}{2}f(n)\left ({ \mathbf {p}^{T}\mathbf {Q}\mathbf {p}\log \left ({ \frac {1}{ \mathbf {p}^{T}\mathbf {Q}\mathbf {p}}}\right )\!-\!\mathbf {p}^{T}\mathbf {Q^{*}p}}\right )\!+\!o(n^{2}f(n)) \\ &=o(H(A_{n})) \tag{71}\end{align*}
Now assume
\begin{align*} H(A_{n})\ge H(A_{n}|X^{n})&= \binom {n}{2}H(A_{12}|X_{1},X_{2}) \\ &=\binom {n}{2}\mathbf {p}^{T}h(f(n)\mathbf {Q})\mathbf {p}. \tag{72}\end{align*}
Still, we can upper bound the expected length of the compressor \begin{align*} &\binom {n'}{2}H(\mathbf {B}_{12}) \\ &=\binom {n'}{2}(H(\mathbf {B}_{12}|X_{1}^{2k})+I(X_{1}^{2k};\mathbf {B}_{12})) \\ &=\binom {n'}{2}(k^{2}H(A_{1,k+1}|X_{1},X_{k+1})+I(X_{1}^{2k};\mathbf {B}_{12})) \\ &\stackrel {(b)}{\le } \binom {n'}{2}(k^{2} \mathbf {p}^{T}h(f(n)\mathbf {Q})\mathbf {p}+H(X_{1}^{2k})) \\ &=\binom {n'}{2}(k^{2} \mathbf {p}^{T}h(f(n)\mathbf {Q})\mathbf {p}+2kH(\mathbf {p})) \\ &\le \frac {n(n-k)}{2} \mathbf {p}^{T}h(f(n)\mathbf {Q})\mathbf {p}+n(n'-1)H(\mathbf {p}), \tag{73}\end{align*}
\begin{align*} 2^{k^{2}}\log (2e^{2}n^{3})\le n^{\delta} \log (2e^{2}n^{3})=o\left ({\frac {n^{2}}{k}}\right ), \tag{74}\\ nk^{2}H(A_{12})+4\le n\delta \log n H(A_{12})+4=o\left ({\frac {n^{2}}{k}}\right ). \tag{75}\end{align*}
\begin{align*} & \mathsf {E}(2N_{r}\lceil \log n\rceil ) \\ &=f(n) \mathbf {p}^{T}\mathbf {Q}\mathbf {p}\left ({(n-\tilde {n})\tilde {n} + \binom {n-\tilde {n}}{2}}\right )2\lceil \log n\rceil \\ &=O(kn\log n)=o\left ({\frac {n^{2}}{k}}\right ). \tag{76}\end{align*}
\begin{align*} & \mathsf {E}(\ell (C_{k}(A_{n}))) - H(A_{n})\\ &\le \frac {n(n-k)}{2} \mathbf {p}^{T}h(f(n)\mathbf {Q})\mathbf {p}+n(n'-1)H(\mathbf {p})\\ &\;\;\;-\frac {n(n-1)}{2} \mathbf {p}^{T}h(f(n)\mathbf {Q})\mathbf {p}+o\left ({\frac {n^{2}}{k}}\right )\\ &=n(n'-1)H(\mathbf {p})+\frac {n(1-k)}{2} \mathbf {p}^{T}h(f(n)\mathbf {Q})\mathbf {p}+o\left ({\frac {n^{2}}{k}}\right )\\ &\le H(\mathbf {p})\frac {n^{2}}{k}+o\left ({\frac {n^{2}}{k}}\right )\\ &= o(H(A_{n})),\end{align*}
Performance Under the Local Weak Convergence Framework
In this section, we analyze the performance of the proposed compressor under the local weak convergence framework introduced in [34] and [42]. We focus on a subfamily of SBM in the
We first introduce some basic definitions of rooted graphs in Subsection VI-A. Then, we define the local weak convergence of graphs and derive the local weak convergence limit of the subfamily of stochastic block model in Subsection VI-B. Finally, we review the definition of BC entropy in Subsection VI-C and state the performance guarantee of our compression algorithm in Subsection VI-D.
A. Basic Definitions on Rooted Graphs
Let
\begin{align*} \hat {h}:=&\sup \{h\in \mathbb {Z}^{+}:(G_{1},o_{1})_{h}\simeq (G_{2},o_{2})_{h} \\ & \text {for some } (G_{1},o_{1}) \in [G_{1},o_{1}], (G_{2},o_{2}) \in [G_{2},o_{2}]\}\end{align*}
and define the metric \begin{align*}d^{*}([G_{1},o_{1}],[G_{2},o_{2}]):=\frac {1}{1+\hat {h}}.\end{align*}
\begin{equation*} \mu _{h}([G,o])=\sum _{[G',o]\in \mathcal {G}^{*}:[G',o]_{h}=[G,o]}\mu ([G',o]). \tag{77}\end{equation*}
\begin{equation*} U(G):=\frac {1}{|V|}\sum _{v\in V}\delta _{[G(v),v]}, \tag{78}\end{equation*}
For a sequence of graphs
B. Local Weak Convergence
In this section, we want to study the local weak limit of a sequence of graphs generated from stochastic block models. However, we notice that the definition for rooted neighbourhood distribution given in (78) is limited to deterministic graphs. Therefore, we first extend this definition to the case of random graphs. Suppose we have a random graph
\begin{align*} &U(G_{n})(B) \\ &=\sum _{g\in \mathrm {supp}(\Lambda _{n})} \mathsf {P}_{\Lambda _{n}}(G_{n}=g)\frac {1}n\sum _{i=1}^{n}{{\mathsf {1}}}\{[g(i),i]\in B\}, \tag{79}\end{align*}
i.e., we first generate a random graph \begin{align*} &U(G_{n})(B) \\ &=\frac {1}n\sum _{i=1}^{n}\sum _{g\in \mathrm {supp}(\Lambda _{n})} \mathsf {P}_{\Lambda _{n}}(G_{n}=g){{\mathsf {1}}}\{[g(i),i]\in B\} \\ &=\frac {1}n\sum _{i=1}^{n} \mathsf {P}_{\Lambda _{n}}([G_{n}(i),i]\in B). \tag{80}\end{align*}
\begin{equation*} U(A_{n})(B)= \mathsf {P}_{\Lambda _{n}}([A_{n}(\rho ),\rho ]\in B) \tag{81}\end{equation*}
To state the limiting distribution, we need to define the Galton–Watson tree probability distribution on rooted trees
Remember that the total variation distance between two probability measures
Proposition 10:
Let
\begin{equation*}d_{\mathrm {TV}}(\mathrm {Nbr}_{R},\mathrm {GWT}( \mathrm {Poi}(\lambda ))_{R})\rightarrow 0.\end{equation*}
The proof of Proposition 10 follows a similar idea as the proof of Proposition 2 in [53]. The key idea essentially follows from the fact that
To upper bound the total variation distance between these two distributions, we first review the definition of coupling between two probability distributions. Let
\begin{equation*}\gamma (A\times S)=\mu (A)\; and \; \gamma (S\times A)=\nu (A),\; \forall A\in \mathcal {S}.\end{equation*}
It is known that for two probability distributions \begin{equation*} \delta (\mu ,\nu )\le \mathsf {P} (X\neq Y),\end{equation*}
To formally state the proof of Proposition 10, we need a few more definitions. Let
Lemma 5:
If
Gr−1=Tr−1 Yu=Zu u∈∂Gr−1 Cr Dr
Proof of Lemma 5:
First of all, events
Next, we define a set of auxiliary events in order to complete the proof of our induction step. For any
\begin{equation*}E_{r}=\{|\partial G_{s}|\le 2^{s} Q_{\mathrm {max}}^{s}\log n,\; \forall s\le r+1\}.\end{equation*}
The utility of this auxiliary event is shown in the following two lemmas.Lemma 6:
For all
\begin{equation*} \mathsf {P}(E_{r}|E_{r-1})\ge 1-n^{-c}.\end{equation*}
Moreover, Proof of Lemma 6:
First of all, remember that for two random variables
\begin{equation*}Z\sim \mathrm {Binom}\left({2^{r} Q_{\mathrm {max}}^{r}n\log n,\frac { Q_{\mathrm {max}}}{n}}\right).\end{equation*}
Thus, \begin{align*} \mathsf {P}(E_{r}^{c}|E_{r-1})&= \mathsf {P}(|\partial G_{r+1}|>2^{r+1} Q_{\mathrm {max}}^{r+1}\log n |E_{r-1})\\ &\le \mathsf {P} (Z\ge 2 \mathsf {E} Z)\stackrel {(a)}{\le }\left ({\frac {e}{4}}\right )^{ \mathsf {E} Z},\end{align*}
\begin{equation*} \mathsf {P}(X>(1+\delta ) \mathsf {E} X)\le \left ({\frac {e^{\delta} }{(1+\delta )^{1+\delta }}}\right )^{ \mathsf {E} X}\end{equation*}
\begin{equation*} \mathsf {E} Z=2^{r} Q_{\mathrm {max}}^{r+1}\log n=\Omega ( \log ^{c_{1}} n),\end{equation*}
For the second part, on
\begin{align*} |G_{r}|&=\sum _{r=1}^{R}|\partial G_{r}|\\ &\le \sum _{r=1}^{R}2^{r} Q_{\mathrm {max}}^{r}\log n\le (2 Q_{\mathrm {max}})^{R+1}\log n=O(\log ^{2} n),\end{align*}
since Lemma 7:
For any
\begin{align*}& \mathsf {P}(C_{r}|E_{r-1})\ge 1-O(n^{-3/4})\\ & \mathsf {P}(D_{r}|E_{r-1})\ge 1-O(n^{-3/4}).\end{align*}
Proof:
For the first claim, fix
Moreover, we state a lemma to bound the total variation distance between the Binomial distribution and the Poisson distribution.
Lemma 8 (Lemma 5 in[53]):
If
\begin{equation*}d_{\mathrm {TV}}(\mathrm {Binom}(m,c/n), \mathrm {Poi}(c))=O\left ({\frac {\max \{1,|m-n|\}}{n}}\right ).\end{equation*}
Now, we are ready to prove Proposition 10.Proof:
[Proof of Proposition 10] For any random variable
\begin{equation*} \mathsf {P}\left ({||V^{(i)}|-np_{i}|\ge n^{3/4}}\right )\le 2e^{-\Omega (n^{1/2})}.\end{equation*}
It follows from the union bound that \begin{equation*} \mathsf {P}\left ({\forall i\in [L], ||V^{(i)}|-np_{i}| \le n^{3/4}}\right ) \ge 1 - 2Le^{-\Omega (n^{1/2})}.\end{equation*}
\begin{align*} np_{i}+n^{3/4}&\ge |V^{(i)}|\ge |V^{(i)}_{r-1}|\ge |V^{(i)}|-|G_{r-1}|\\ &\ge np_{i}-n^{3/4}-O(\log ^{2} n)\end{align*}
Next, let us analyze the distribution of
\begin{align*} &d_{\mathrm {TV}}(\mathrm {dist}(Y_{v}|G_{r-1}=g_{r-1}),\mathrm {dist}(Z_{v})) \\ &= d_{\mathrm {TV}}\left ({\mathrm {dist}(Y_{v}|X_{v}=j), \mathrm {Poi}\left ({\sum _{i=1}^{L}p_{i}Q_{ji}}\right )}\right )=O(n^{-1/4})\end{align*}
for any possible realization \begin{align*} \mathsf {P}(\exists v \in \partial G_{r-1}: Y_{v} \neq Z_{v}) &\le |\partial G_{r-1}| \mathsf {P}(Y_{v} \neq Z_{v})\\ &= O(\log ^{2} n)O(n^{-1/4})\\ &=O(n^{-1/5}).\end{align*}
\begin{equation*} \mathsf {P}(G_{r}=T_{r},E_{r}|G_{r-1}=T_{r-1},E_{r-1})\ge 1-O(n^{-\mathrm {min}(c,1/5)}).\end{equation*}
\begin{align*} & \mathsf {P}(G_{R}\neq T_{R})\\ &= \mathsf {P}(\exists r\in [R]\; \mathrm {s.t.}\; G_{r}\neq T_{r} \text {or }E_{r}^{c}|G_{r-1}=T_{r-1},E_{r-1})\\ &\le R\cdot O(n^{-\mathrm {min}(c,1/5)})\\ &=\Theta (\log \log \log n) O(n^{-\mathrm {min}(c,1/5)})\\ &\rightarrow 0\end{align*}
With Proposition 10, we are ready to establish the local weak convergence of the stochastic block model.
Proposition 11 (Local weak limit of sparse SBMs):
Consider a sparse stochastic block model
\begin{equation*}U(A_{n})\rightsquigarrow \mathrm {GWT}( \mathrm {Poi}(\lambda )).\end{equation*}
Remark 14:
When
Proof of Proposition 11:
We want to show that for any uniformly continuous and bounded function
\begin{equation*}\left |{\int fdU(A_{n})-\int f d\mathrm {GWT}( \mathrm {Poi}(\lambda ))}\right |\rightarrow 0\end{equation*}
as \begin{align*} &\left |{\int fd\mu _{h}-\int fd\mu }\right | \\ &=\left |{\sum _{[g,o]\in \mathcal {G}^{*}_{h}}f([g,o])\mu _{h}([g,o])-\sum _{[i,o]\in \mathcal {G}^{*}}f([i,o])\mu ([i,o])}\right |\\ &\le \sum _{[g,o]\in \mathcal {G}^{*}_{h}}\Bigg | f([g,o])\mu _{h}([g,o]) \\ &\hspace {5em}-\sum _{[i,o]\in \mathcal {G}^{*}:[i,o]_{h}=[g,o]}f([i,o])\mu ([i,o])\Bigg |\\ &\stackrel {(a)}{=}\sum _{[g,o]\in \mathcal {G}^{*}_{h}}\left |{\sum _{[i,o]\in \mathcal {G}^{*}:[i,o]_{h}=[g,o]}(f([g,o])-f([i,o]))\mu ([i,o])}\right |\\ &\le \sum _{[g,o]\in \mathcal {G}^{*}_{h}}\sum _{[i,o]\in \mathcal {G}^{*}:[i,o]_{h}=[g,o]}\left |{ f([g,o])-f([i,o])}\right |\mu ([i,o])\\ &\le \sum _{[g,o]\in \mathcal {G}^{*}_{h}}\sum _{[i,o]\in \mathcal {G}^{*}:[i,o]_{h}=[g,o]}\epsilon \mu ([i,o])=\epsilon ,\end{align*}
\begin{align*} &\left |{\int f dU(A_{n})-\int fd\mathrm {GWT}( \mathrm {Poi}(\lambda ))}\right |\\ &\le \left |{\int fdU(A_{n})_{h}-\int fdU(A_{n})}\right |\\ &\;\;\;+\left |{\int fd\mathrm {GWT}( \mathrm {Poi}(\lambda ))_{h}-\int fd\mathrm {GWT}( \mathrm {Poi}(\lambda ))}\right |\\ &\;\;\;+\left |{\int f d\mathrm {GWT}( \mathrm {Poi}(\lambda ))_{h}-\int fdU(A_{n})_{h}}\right |\\ & < 3\epsilon ,\end{align*}
C. BC Entropy
In this section, we review the notion of BC entropy introduced in [42], which is shown to be the fundamental limit of universal lossless compression for certain graph family [66].
For a Polish space
\begin{equation*} {\mathcal {G}_{n,m}}(\rho ,\epsilon )=\{G\in {\mathcal {G}_{n,m}} :U(G)\in B(\rho ,\epsilon )\},\end{equation*}
where \begin{equation*} {\overline {\Sigma }}(\rho ,\epsilon )=\limsup \limits _{n\rightarrow \infty }\frac {\log | {\mathcal {G}_{n,m}}(\rho ,\epsilon )|-m\log n}{n}\end{equation*}
\begin{equation*} {\overline {\Sigma }}(\rho )=\lim _{\epsilon \rightarrow 0} {\overline {\Sigma }}(\rho ,\epsilon ).\end{equation*}
\begin{equation*}\Sigma (\rho ):= {\overline {\Sigma }}(\rho )= {\underline {\Sigma }}(\rho ).\end{equation*}
The following lemma states the BC entropy of the Galton-Waston tree distribution.
Lemma 9 (Corollary 1.4 of[42]):
The BC entropy of the Galton–Watson tree distribution
\begin{equation*}\Sigma \left ({\mathrm {GWT}( \mathrm {Poi}(\lambda ))}\right )=\frac {\lambda }{2}\log \frac {e}{\lambda } \quad \mathrm {bits}.\end{equation*}
D. Achieving BC Entropy in the Sparse Regime
With the Lemma above, we can give a performance guarantee of our algorithm corresponding to the BC entropy. It is a Theorem analogous to Proposition 1 in [66].
Theorem 5:
Let
\begin{equation*}\limsup _{n \to \infty }\frac { \mathsf {E}[\ell (C_{k}(A_{n}))]-m\log n}{n}\le \Sigma \left ({\mathrm {GWT}( \mathrm {Poi}(\lambda ))}\right ).\end{equation*}
Proof:
By our proof of Proposition 9, we have
\begin{align*}& \mathsf {E}[\ell (C_{k}(A_{n}))]\le \binom {n'}{2}H(\mathbf {B}_{12})+2^{k^{2}}\log (2en^{3})\\ &\qquad \quad \qquad \qquad +nk^{2}_{n}H(A_{12})+4+ \mathsf {E}(2N_{r} \left \lceil{ \log n}\right \rceil ).\end{align*}
Notice that \begin{align*} \binom {n'}{2}H(\mathbf {B}_{12})&\le \binom {n'}{2}k^{2}H(A_{12})\\ &=\binom {n'}{2}k^{2}h(\lambda /n)\\ &\stackrel {(a)}{=}\binom {n'}{2}k^{2}\left ({\frac {1}{n}\lambda \log \frac {ne}{\lambda }+o\left ({\frac {1}{n}}\right )}\right )\\ &\stackrel {(b)}{\sim } \binom {n}{2}\left ({\frac {1}{n}\lambda \log n +\frac {1}{n}\lambda \log \frac {e}{\lambda }+o\left ({\frac {1}{n}}\right )}\right )\\ &=\binom {n}{2}\frac {1}{n}\lambda \log n+\frac {\lambda \log e-\lambda \log \lambda }{2}n+o(n)\\ &\stackrel {(c)}{=}m\log n+n\Sigma \left ({\mathrm {GWT}( \mathrm {Poi}(\lambda ))}\right )+o(n)\end{align*}
\begin{equation*} 2^{k^{2}}\log (2en^{3})\le 2^{\delta \log n}\log (2en^{3})=n^{\delta} \log (2en^{3})=o(n)\end{equation*}
\begin{align*} nk^{2}_{n}H(A_{12})+4&=nk^{2}_{n}h(\lambda /n)+4\\ &=nk^{2}_{n}\left ({\frac {1}{n}\lambda \log \frac {ne}{\lambda }+o\left ({\frac {1}{n}}\right )}\right )+4\\ &\le n\delta \log n \left ({\frac {1}{n}\lambda \log \frac {ne}{\lambda }+o\left ({\frac {1}{n}}\right )}\right )+4\\ &=\delta \log n \left ({\lambda \log \frac {ne}{\lambda }}\right )+o\left ({\log n}\right )\\ &=o(n),\end{align*}
\begin{align*} & \mathsf {E}(2N_{r}\lceil \log n\rceil )\\ &=\frac {1}n \mathbf {p}^{T}\mathbf {Q}\mathbf {p}\left ({(n-\tilde {n})\tilde {n} + \binom {n-\tilde {n}}{2}}\right )2\lceil \log n\rceil \\ &=O(k\log n)=o(n).\end{align*}
Theorem 5 shows that in the sparse regime
Comparison to Alternative Methods
In this section, we consider three alternative compression methods which are natural attempts at designing universal graph compressors for stochastic block models. We demonstrate why they are not applicable to our problem or not universal in the same sense as the proposed algorithm.
One intuitive attempt is to convert the entries in the adjacency matrix into a one-dimensional sequence according to some ordering and then apply a universal compressor to the sequence. Let us take a closer look at the correlation among entries in the adjacency matrix and explain why existing universal sequence compressors developed for stationary processes may not be immediately applicable for certain orderings of the entries. Compressing
For example, consider listing the bits in the upper triangle row-wise (i.e., first listing the bits in the first row, followed by the bits in the second and so on, ending with
Another potential approach is to first recover the community labels of all vertices, which allows one to rearrange the entries in the adjacency matrix into i.i.d. groups, and then apply a universal sequence compressor to each group of entries. There are two main issues with this approach. First, even when the exact recovery of labels is possible, to the best of our knowledge, all algorithms for community detection require knowledge of the graph parameters such as the number of communities and/or the edge probabilities [67]. Second, it is known that exact recovery is information-theoretically impossible when the edge probabilities are
Another approach is based on run-length coding for the adjacency matrix
Concluding Remarks
In this paper, we constructed a compressor that is universal for the class of stochastic block models with connection probabilities ranging from
ACKNOWLEDGMENT
The authors would like to thank the associate editor and the anonymous reviewers for their invaluable contributions and constructive suggestions, which have significantly enhanced the quality and clarity of this article. The author Chi Wang would like to thank Richard Peng for his suggestion in writing. The author Lele Wang would like to thank Emmanuel Abbe and Tsachy Weissman for stimulating discussions in the initial phase of the work. She is grateful to Young-Han Kim and Ofer Shayevitz for their interest and encouragement in this result.
Appendix A
Appendix A
Proof of Lemma 4
Let
\begin{align*} &\binom {N}{N_{1},N_{2}\cdots N_{m}}\\ &\ge \frac {\sqrt {2\pi N}N^{N} \exp \left ({\frac {1}{12N+1}-\frac {1}{12N_{1}}-\frac {1}{12N_{2}}-\cdots -\frac {1}{12N_{m}}}\right )}{(2\pi )^{m/2}(N_{1}N_{2}\cdots N_{m})^{1/2}N_{1}^{N_{1}}N_{2}^{N_{2}}\cdots N_{m}^{N_{m}}}\\ &=\frac {\exp \left ({\frac {1}{12N+1}-\frac {1}{12N_{1}}-\frac {1}{12N_{2}}-\cdots -\frac {1}{12N_{m}}}\right )}{(2\pi )^{\frac {m-1}{2}}(p_{1}p_{2}\cdots p_{m})^{1/2}N^{\frac {m-1}{2}}2^{-NH(p_{1},p_{2},\cdots ,p_{m})}}.\end{align*}
Similarly, we have \begin{align*} &\binom {2N}{2N_{1},2N_{2}\cdots 2N_{m}}\\ &\le \frac {\exp \left ({\frac {1}{24N}-\frac {1}{24N_{1}+1}-\frac {1}{24N_{2}+1}-\cdots -\frac {1}{24N_{m}+1}}\right )}{(2\pi )^{\frac {m-1}{2}}2^{\frac {m-1}{2}}(p_{1}p_{2}\cdots p_{m})^{1/2}N^{\frac {m-1}{2}}2^{-2NH(p_{1}\cdots p_{m})}}\cdot\end{align*}
\begin{align*} &f(N_{1},N_{2},\cdots ,N_{m})\\ &=\tfrac {1}{12N+1}-\tfrac {1}{24N}+\left({\tfrac {1}{24N_{1}+1}-\tfrac {1}{12N_{1}}}\right)+\left({\tfrac {1}{24N_{2}+1}-\tfrac {1}{12N_{2}}}\right)\\ &\;\;\;+\cdots +\left({\tfrac {1}{24N_{m}+1}-\tfrac {1}{12N_{m}}}\right)\end{align*}
\begin{equation*}g(n)=\frac {1}{24n+1}-\frac {1}{12n},\end{equation*}
\begin{align*} &\frac {\binom {N}{N_{1},N_{2}\cdots N_{m}}\theta _{1}^{N_{1}}\cdots \theta _{m}^{N_{m}}}{\binom {2N}{2N_{1},2N_{2}\cdots 2N_{m}}\theta _{1}^{2N_{1}}\cdots \theta _{m}^{2N_{m}}} \\ &\ge \frac {2^{\frac {m-1}{2}}\exp (f(N_{1},N_{2},\cdots ,N_{m}))}{2^{NH(p_{1}\cdots p_{m})}\theta _{1}^{N_{1}}\cdots \theta _{m}^{N_{m}}}\\ &\ge \frac {2^{\frac {m-1}{2}}\exp \left ({\frac {1}{12N+1}-\frac {1}{24N}+(1/25-1/12)m}\right )}{2^{-ND_{\mathrm {KL}}(p||\theta )}} \\ &=2^{\frac {m-1}{2}}2^{ND_{\mathrm {KL}}(p||\theta )}2^{\log {e}\left({\frac {1}{12N+1}-\frac {1}{24N}+(1/25-1/12)m}\right)}.\end{align*}
\begin{equation*}\frac {\binom {N}{N_{1},N_{2}\cdots N_{m}}\theta _{1}^{N_{1}}\cdots \theta _{m}^{N_{m}}}{\binom {2N}{2N_{1},2N_{2}\cdots 2N_{m}}\theta _{1}^{2N_{1}}\cdots \theta _{m}^{2N_{m}}} \ge 1.\end{equation*}
\begin{equation*}\frac {\binom {N}{N_{1},N_{2}\cdots N_{m}}\theta _{1}^{N_{1}}\cdots \theta _{m}^{N_{m}}}{\binom {2N}{2N_{1},2N_{2}\cdots 2N_{m}}\theta _{1}^{2N_{1}}\cdots \theta _{m}^{2N_{m}}}=\frac {1}{\theta _{1}^{N_{1}}\cdots \theta _{m}^{N_{m}}}>1.\end{equation*}
Joint Distributions Induce by Laplace and KT Probability Assignments
In this section, we re- derive the well-known joint distributions of Laplace and KT probability assignments for completeness. Firstly we consider the Laplace probability assignment. Recalled that we defined
\begin{equation*} q_{ \mathrm {L}}(X_{j+1} = i| X^{j} = x^{j}) = \frac {N_{i}(x^{j}) + 1 }{j + m} \quad \text {for each } i \in [m].\end{equation*}
Consider a sequence \begin{align*} q_{ \mathrm {L}}(x^{N})&=\prod _{j=0}^{N-1} q_{ \mathrm {L}}(X_{j+1}=x_{j+1}|X^{j}=x^{j}) \\ &=\prod _{j=0}^{N-1} \frac {N_{x_{j+1}}(x^{j}) + 1 }{j + m} \\ &\stackrel {(a)}{=}\frac {N_{1}!N_{2}!\cdots N_{m}!}{m(m+1)\cdots (m+N-1)}, \tag{82}\end{align*}
\begin{equation*} q_{ \mathrm {L}}(x^{N}) : =\frac {N_{1}!N_{2}!\cdots N_{m}!}{N!}\cdot \frac {1}{\binom{N+m-1 }{ m-1}}.\end{equation*}
Now, we consider KT probability assignment. Recalled that
\begin{equation*} q_{\mathrm {KT}}(X_{j+1} = i| X^{j} = x^{j}) = \frac {N_{i}(x^{j}) + 1/2 }{j + m/2} \quad \text {for each } i \in [m].\end{equation*}
Consider a sequence \begin{align*} q_{\mathrm {KT}}(x^{N})&=\prod _{j=0}^{N-1} q_{\mathrm {KT}}(X_{j+1}=x_{j+1}|X^{j}=x^{j}) \\ &=\prod _{j=0}^{N-1} \frac {N_{i}(x^{j}) + 1/2 }{j + m/2} \\ &=\prod _{j=0}^{N-1} \frac {2N_{i}(x^{j}) + 1 }{2j + m} \\ &\stackrel {(b)}{=}\frac {(2N_{1}-1)!!(2N_{2}-1)!!\cdots (2N_{n}-1)!!}{m(m+2)\cdots (m+2N-2)}. \tag{83}\end{align*}