Say we have a joint distribution on a finite alphabet $\mathcal{X}\times \mathcal{Y}$. It could be a communication link where we want to send a random message $X$ over a channel, but it gets garbled into $Y$. The joint distribution of $(X,Y)$ can be visualized as an undirected, weighted bipartite graph on the vertex set $\mathcal{X}\times \mathcal{Y}$.
If we fix a small $\varepsilon > 0$ and repeat the experiment enough times, then by the joint-AEP, for $n$ large enough, the outcome will be nearly uniformly distributed in some small subset $S \subset \mathcal{X}^n \times \mathcal{Y}^n$. Then with up to negligible probability, the outcome corresponds to an edge picked (nearly) uniformly at random from the unweighted bipartite graph $G=(\mathcal{X}^n,\mathcal{Y}^n,E)$, where there is only an edge between $x$ and $y$ if $(x,y)\in S$.
If we repeat the experiment $n\cdot i$ times, then we will be choosing edges from some bigger graph $G_i$ on vertex set $\mathcal{X}^{n\cdot i}\times\mathcal{Y}^{n\cdot i} $ where there is an edge between $(x,y)$ if $(x,y)\in S\underset{i\ \text{times}}{\underbrace{\times \dots \times}} S$.
This can be described succinctly by defining a shorthand operation $\tilde\ast$ on general undirected, unweighted bipartite graphs $G_A=(\mathcal{X}_A,\mathcal{Y}_A,E_A)$ and $G_B=(\mathcal{X}_B,\mathcal{Y}_B,E_B)$:
$G_A\tilde\ast G_B$ is the bipartite graph $(\mathcal{X}_A\times \mathcal{X}_B,\mathcal{Y}_A\times \mathcal{Y}_B,E_A\times E_B).$
Then $G_{i+1}= G_i \tilde\ast G$. Here is my question:
As $i$ gets large, then does the graph $G_i$ eventually cluster, and become close to a disjoint union of a bunch of complete bipartite graphs? (In particular, $2^{nI(X;Y)}$ complete bipartite graphs $K_{2^{nH(X|Y)},2^{nH(Y|X)}}$)
This would be a very handy property from the perspective of information theory and communications. It implies that if you have enough noisy observations $Y$, then on average you can extract $I(X;Y)$ bits of pure, noiseless information about $X$ from them.
We know from unrelated analysis that this information extraction can be done when $(X,Y)$ is multivariate Gaussian.
Update: This is false, but a similar statement about encoding a Gaussian source is true.
Things I have tried
- The planar separator theorem for arbitrary genus cannot help us. If it could, a contradiction would arise where $G_i$ eventually clusters arbitrarily well, which we know can't be true.
- Spectral clustering ideas tells us that if $G_i$ does eventually cluster, then the eigenvectors which correspond to the smallest eigenvalues of $G_i'$s Laplacian should eventually start looking like indicator functions for clusters as $i$ gets large. Unfortunately, even if the alphabet $\mathcal{X}\times \mathcal{Y}$ is small, the product distribution's alphabet gets large very fast, even after taking few products so I can't directly test this.
Nonetheless, if $(X,Y) \sim \frac{1}{8}\left[\begin{smallmatrix}1 & 1 & 0 & 0 \\ 1& 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 0& 0& 1 & 1\end{smallmatrix}\right],$ $G_5$'s Laplacian is computationally easy. Ignoring the trivial 0 eigenvalue, there are 10 small eigenvectors of $G_5$'s Laplacian. They look like:
While each eigenvector obviously preferences some nodes and discards others, no immediate indicator-function structure is apparent to me, at least without more intelligent sorting.
Any pertinent intuitions are appreciated. Thanks for reading
