Deterministic Gács–Körner common part and Wyner common information

Let $(X,Y)$ have a joint probability vector $p_{XY}$ on finite nonempty alphabets $\mathcal{X}\times \mathcal{Y}$. Its support bipartite graph has left vertices $x$ with $p_X(x)>0$, right vertices $y$ with $p_Y(y)>0$, and an edge $x\text{\hspace{0.17em}⁣}\text{–}\text{\hspace{0.17em}⁣}y$ exactly when $p_{XY}(x,y)>0$. Let $\mathcal{K}$ be the finite nonempty set of connected components. Define $K_X(x)$ and $K_Y(y)$ to be the component containing the corresponding vertex when that vertex has positive marginal mass; assign any fixed component label to zero-mass symbols, which do not affect the law of the random labels. Along every support edge the two labels agree, so define the finite random variable $K:=K_X(X)=K_Y(Y)$ almost surely. If $f(X)=g(Y)$ almost surely for any other finite-valued deterministic common output, then $f(x)=g(y)$ along every support edge; equality propagates along graph paths, so both functions are constant on each component and the common output is a function of $K$. Thus $K$ is the maximal deterministic common part up to relabeling. Its finite entropy $H(K)$ is the deterministic Gács–Körner common information, using Finite distributions, entropy, divergence, and stochastic matrices.

A finite auxiliary random variable $U$ is Wyner-admissible for $p_{XY}$ when a joint law $p_{XYU}$ has $(X,Y)$-marginal $p_{XY}$ and, for every $u$ with $p_U(u)>0$, $p_{XY\mid U=u}(x,y)=p_{X\mid U=u}(x)p_{Y\mid U=u}(y)\mathrm{.}$ The finite-alphabet Wyner common information is $C_W(X;Y):={\inf }_{U\text{ finite, Wyner-admissible}}I((X,Y);U),$ where mutual information and natural-log units are as in Finite mutual information and Information units and logarithm-base convention. The Gács–Körner object is a deterministic common output of both terminals; Wyner's quantity optimizes mutual information over an auxiliary variable that makes the terminals conditionally independent. They are distinct definitions. This page does not identify them or use either as a Slepian–Wolf rate coordinate.

The admissible class is nonempty: $U=(X,Y)$ is finite and makes each positive-mass conditional joint law a product of point masses. Hence the infimum is over a nonempty set of finite real mutual informations.