46.05.04 · information-theory / side-information

Common Information: Wyner's and Gacs-Korner Definitions

shipped3 tiersLean: none

Anchor (Master): Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §15.8; Wyner 1975 The common information of two dependent random variables; Gacs & Korner 1973 Common information is far less than mutual information; Ahlswede & Korner 1975 On the common information of two discrete random variables

Intuition Beginner

Two random variables $X$ and $Y$ share some information. The standard measure is mutual information $I (X; Y)$ — how much knowing $X$ reduces uncertainty about $Y$ . But mutual information is a single number that captures the total shared information, not its structure.

A natural question: how much of this shared information is "extractable" in a meaningful sense? The answer depends on what you mean by "extractable," and there are two distinct definitions.

The first, due to Gacs and Korner, asks: what is the largest function of $X$ that can also be determined from $Y$ alone? For example, if $X = (A, B)$ and $Y = (A, C)$ share the component $A$ , then $A$ is the common part. Its entropy $H (A)$ is the Gacs-Korner common information. This is the most restrictive notion: it captures only information that can be extracted identically from either variable.

The second, due to Wyner, asks: what is the minimum rate of shared randomness that two agents need in order to separately generate $X$ and $Y$ with the correct joint distribution? This is more generous: the shared randomness does not need to equal any function of $X$ or $Y$ , it just needs to enable both agents to sample from the correct joint distribution.

The relationship is: Gacs-Korner common information $\leq$ mutual information $\leq$ Wyner common information. Mutual information sits between the two, and all three can be different.

Visual Beginner

Figure: a Venn diagram for two random variables $X$ and $Y$ . The intersection is labeled "Mutual Information $I (X; Y)$ ". Within the intersection, a small inner region is labeled "Gacs-Korner $C_{G K}$ " (the common part). Extending beyond the intersection, a larger region encompassing part of both variables is labeled "Wyner $C_{W}$ " (the minimum shared randomness for distributed generation).

Quantity	Symbol	Relationship	Operational meaning
Gacs-Korner common info	$C_{G K} (X; Y)$	$C_{G K} \leq I (X; Y)$	Entropy of the common function
Mutual information	$I (X; Y)$	$C_{G K} \leq I (X; Y) \leq C_{W}$	Total shared information
Wyner common info	$C_{W} (X; Y)$	$I (X; Y) \leq C_{W}$	Minimum shared randomness for generation

Worked example Beginner

Let $X$ be a uniform random variable on ${0, 1, 2, 3}$ and $Y = X mod 2$ (the parity). Then $X$ determines $Y$ , so $I (X; Y) = H (Y) = 1$ bit.

Gacs-Korner: what function of $X$ can be determined from $Y$ alone? Since $Y$ is only the parity (0 or 1), the only function of $X$ that can be recovered from $Y$ is $Y$ itself. So $C_{G K} (X; Y) = H (Y) = 1$ bit. But wait — can $Y$ be determined from $X$ ? Yes, since $Y = X mod 2$ . And can some function of $Y$ be determined from $X$ ? Yes, $Y$ itself. The common function is $Y$ , so $C_{G K} = H (Y) = 1$ bit.

Wyner: $C_{W} (X; Y) = min_{X \to W \to Y} I (X, Y; W)$ . Since $Y$ is a function of $X$ , choose $W = Y$ . Then $I (X, Y; W) = I (X, Y; Y) = H (Y) = 1$ bit. The Markov chain $X \to Y \to Y$ holds. So $C_{W} = 1$ bit.

In this case, all three quantities coincide: $C_{G K} = I (X; Y) = C_{W} = 1$ bit.

Now let $X$ and $Y$ be independent fair coins with $Z = X \oplus Y$ (XOR). Consider $(X, Z)$ and $(Y, Z)$ . Then $I (X, Z; Y, Z) = I (X; Y, Z) + I (Z; Y, Z ∣ X)$ . $Z$ is a function of $(X, Y)$ , so $H (Z ∣ X, Y) = 0$ . The common part: both $(X, Z)$ and $(Y, Z)$ contain $Z$ , so $C_{G K} ((X, Z); (Y, Z)) = H (Z) = 1$ bit. Mutual information is larger because of the additional correlation through the XOR structure.

Check your understanding Beginner

Formal definition Intermediate+

Definition (Gacs-Korner common information). The Gacs-Korner common information of $(X, Y)$ is:

C_{G K} (X; Y) = max {H (f (X)) : f (X) = g (Y) for some functions f, g} .

Equivalently, $C_{G K}$ is the entropy of the "common part" — the maximal random variable that is a deterministic function of both $X$ and $Y$ .

Definition (Wyner common information). The Wyner common information of $(X, Y)$ is:

C_{W} (X; Y) = p (w ∣ x, y) X \to W \to Y min I (X, Y; W),

where the minimum is over all auxiliary variables $W$ such that $X$ and $Y$ are conditionally independent given $W$ (i.e., $X \to W \to Y$ forms a Markov chain).

Theorem (Ordering). For any pair $(X, Y)$ :

C_{G K} (X; Y) \leq I (X; Y) \leq C_{W} (X; Y) .

Key theorem with proof Intermediate+

Theorem (Wyner 1975). $C_{W} (X; Y) \geq I (X; Y)$ with equality if and only if $X$ and $Y$ can be expressed as $X = f (Z_{1}, Z_{2})$ and $Y = g (Z_{1}, Z_{3})$ where $Z_{1}, Z_{2}, Z_{3}$ are independent.

Proof (inequality). For any $W$ satisfying $X \to W \to Y$ :

$I (X, Y; W) \geq I (X; W) \geq I (X; Y),$

where the first inequality follows because $I (X, Y; W) = I (X; W) + I (Y; W ∣ X) \geq I (X; W)$ , and the second follows from the data-processing inequality applied to the Markov chain $X \to W \to Y$ : $I (X; W) \geq I (X; Y)$ . $□$

Theorem (Gacs-Korner 1973). $C_{G K} (X; Y) \leq I (X; Y)$ with equality if and only if there exist functions $f$ and $g$ such that $f (X) = g (Y)$ almost surely and $H (f (X)) = I (X; Y)$ .

Proof. Let $W = f (X) = g (Y)$ be the common part. Then:

$I (X; Y) = I (X; Y ∣ W) + I (X; Y; W)$

Wait — by the chain rule: $I (X; Y) = I (W; X, Y) - I (W; X ∣ Y) - I (W; Y ∣ X) + correction$ . Directly: since $W$ is a function of $X$ and also a function of $Y$ , we have $H (W ∣ X) = 0$ and $H (W ∣ Y) = 0$ . Therefore $I (W; X) = H (W)$ and $I (W; Y) = H (W)$ . By the data-processing inequality, $I (X; Y) \geq I (f (X); g (Y)) = I (W; W) = H (W)$ . So $H (W) \leq I (X; Y)$ for any common function $W$ , giving $C_{G K} \leq I (X; Y)$ . $□$

Bridge. The common information definitions build toward the understanding of distributed generation and distributed computing by quantifying the minimum shared resources two agents need to reproduce a joint distribution. This is exactly the resource that appears in Slepian-Wolf coding 46.05.01 as the boundary between correlation that can be exploited without communication and correlation that requires transmission. The result appears again in the Wyner-Ziv setting 46.05.02 as the part of the side information that the decoder can extract for free (without the encoder's help). The foundational reason the three quantities $C_{G K} \leq I (X; Y) \leq C_{W}$ are generally different is that the Gacs-Korner notion requires exact functional commonality (both parties extract the same deterministic value), mutual information captures statistical dependence (not necessarily extractable), and Wyner's notion allows any shared randomness that enables correct joint sampling (a much weaker constraint). Putting these together, the central insight is that "what $X$ and $Y$ have in common" is not a single quantity but a spectrum, ranging from exactly shared functions (Gacs-Korner) to statistically dependent structure (mutual information) to the shared randomness needed for distributed generation (Wyner). This result generalises the intuition behind Slepian-Wolf coding and builds toward the multi-user separation between correlation that is free and correlation that costs communication.

Exercises Intermediate+

Exercise (medium, numeric).

Let $X$ and $Y$ be binary with joint distribution $p (0, 0) = p (1, 1) = 0.4$ and $p (0, 1) = p (1, 0) = 0.1$ . Compute $C_{G K} (X; Y)$ and $I (X; Y)$ .

Hint

Check if there is a non-constant common function. Both marginals are uniform.

Answer

Both $X$ and $Y$ are uniform on ${0, 1}$ (each has probability 0.5). For the Gacs-Korner common information: is there a non-constant function $f (X)$ that equals some $g (Y)$ ? Since $X$ is binary, the only non-constant function is the identity (or its negation). $f (X) = X$ : can $X$ be recovered from $Y$ ? No, because when $Y = 0$ , $X$ could be 0 (probability 0.4/0.5 = 0.8) or 1 (probability 0.1/0.5 = 0.2). So $C_{G K} (X; Y) = 0$ .

$I (X; Y) = H (X) + H (Y) - H (X, Y) = 1 + 1 - H (0.4, 0.1, 0.1, 0.4) = 2 - (- 2 (0.4) lo g 0.4 - 2 (0.1) lo g 0.1) = 2 - (0.529 + 0.332 + 0.332 + 0.529) = 2 - 1.722 = 0.278$ bits. (Using $H (0.4, 0.1, 0.1, 0.4) \approx 1.722$ bits.)

So $C_{G K} = 0 < I (X; Y) = 0.278$ bits.

Exercise (hard, short answer).

Prove that $C_{W} (X; Y) = I (X; Y)$ if and only if there exist independent random variables $Z_{1}, Z_{2}, Z_{3}$ and functions $f, g$ such that $X = f (Z_{1}, Z_{2})$ and $Y = g (Z_{1}, Z_{3})$ .

Hint

This is the "doubly stochastic" decomposition. For the "if" direction, take $W = Z_{1}$ .

Answer

If: Let $X = f (Z_{1}, Z_{2})$ and $Y = g (Z_{1}, Z_{3})$ with $Z_{1}, Z_{2}, Z_{3}$ independent. Take $W = Z_{1}$ . Then $X \to W \to Y$ holds because $X$ depends on $(Z_{1}, Z_{2})$ and $Y$ depends on $(Z_{1}, Z_{3})$ , so given $Z_{1} = W$ , $X$ and $Y$ are independent (via $Z_{2} ⊥ Z_{3}$ ). $I (X, Y; W) = I (X, Y; Z_{1}) = H (Z_{1})$ . Now $I (X; Y) = H (Z_{1})$ because $X$ and $Y$ share exactly the information in $Z_{1}$ . So $C_{W} = I (X; Y)$ .

Only if: If $C_{W} = I (X; Y)$ , there exists $W$ with $X \to W \to Y$ and $I (X, Y; W) = I (X; Y)$ . By the data-processing inequality, $I (X; Y) \leq I (X; W) \leq I (X, Y; W) = I (X; Y)$ . So $I (X; W) = I (X; Y)$ , meaning $W$ captures all the mutual information. Decompose $X = (f (X ∣ W), W)$ and $Y = (g (Y ∣ W), W)$ where $f (X ∣ W)$ and $g (Y ∣ W)$ are the "innovations" of $X$ and $Y$ given $W$ . By the Markov condition $X \to W \to Y$ , these innovations are independent given $W$ . Setting $Z_{1} = W$ , $Z_{2} = f (X ∣ W)$ , $Z_{3} = g (Y ∣ W)$ gives the decomposition.

Exercise (hard, short answer).

Connect Wyner common information to distributed generation: show that $C_{W} (X; Y)$ is the minimum rate of common randomness needed for two agents to generate $X^{n}$ and $Y^{n}$ separately with vanishing total variation distance from the true joint distribution.

Hint

Use the achievability proof: both agents share a random seed $W^{n}$ and use it to generate their respective outputs.

Answer

Achievability: Both agents share $W^{n}$ drawn i.i.d. from $p (w)$ . Agent 1 generates $X^{n}$ from $W^{n}$ using the conditional distribution $p (x ∣ w)$ . Agent 2 generates $Y^{n}$ from $W^{n}$ using $p (y ∣ w)$ . By the Markov chain $X \to W \to Y$ , the joint distribution of $(X^{n}, Y^{n})$ satisfies $p (x^{n}, y^{n} ∣ w^{n}) = p (x^{n} ∣ w^{n}) p (y^{n} ∣ w^{n})$ . Averaging over $W^{n}$ : $p (x^{n}, y^{n}) = \sum_{w^{n}} p (w^{n}) p (x^{n} ∣ w^{n}) p (y^{n} ∣ w^{n})$ . As $n \to \infty$ , this approaches the true joint distribution by the law of large numbers. The rate of shared randomness is $H (W^{n}) / n = H (W)$ . Minimizing over $W$ gives $C_{W}$ .

Converse: Any shared randomness $W^{'}$ that enables correct generation must satisfy $X \to W^{'} \to Y$ (otherwise the generated distribution would not match the joint distribution). The rate of shared randomness is at least $I (X, Y; W^{'})$ , and minimizing gives $C_{W}$ .

Exercise (hard, short answer).

Show that for the binary symmetric joint distribution ( $X, Y$ binary with $Pr [X \neq = Y] = p$ ), $C_{W} (X; Y) > I (X; Y)$ when $0 < p < 1/2$ .

Hint

$I (X; Y) = 1 - H (p)$ . Show that no $W$ with $X \to W \to Y$ achieves $I (X, Y; W) = 1 - H (p)$ for $0 < p < 1/2$ .

Answer

For the binary symmetric pair with crossover $p$ : $I (X; Y) = 1 - H (p)$ . Suppose $C_{W} = I (X; Y)$ . By the equality condition, $X = f (Z_{1}, Z_{2})$ and $Y = g (Z_{1}, Z_{3})$ with independent $Z_{1}, Z_{2}, Z_{3}$ . For the binary symmetric pair, this means the correlation must decompose into a shared part $Z_{1}$ and independent innovations $Z_{2}, Z_{3}$ . But the binary symmetric joint distribution has the form $p (x, y) = \frac{1}{2} [(1 - p) δ_{x, y} + p δ_{x \neq = y}]$ . This cannot be written as a product of independent innovations plus a shared part unless $p = 0$ (perfect correlation) or $p = 1/2$ (independent). For $0 < p < 1/2$ , any shared variable $W$ that makes $X$ and $Y$ conditionally independent must carry more information than the mutual information, so $C_{W} > I (X; Y)$ .

Lean formalization Intermediate+

Mathlib does not define Gacs-Korner or Wyner common information. The Gacs-Korner definition requires identifying the maximal common function of two random variables, which involves partition refinement on the sample spaces. The Wyner definition requires optimization over auxiliary random variables satisfying a Markov chain constraint. Neither the variational characterization nor the ordering theorems are formalized. This unit ships without formalization.

Advanced results Master

The exact value of Wyner common information for the binary symmetric pair

For the binary symmetric pair $(X, Y)$ with $Pr [X \neq = Y] = p$ , the Wyner common information was computed by Wyner himself:

C_{W} (X; Y) = 0 \leq α \leq 1 min [H (α * p) + H (α * p) - 2 H (p)],

where $α * p = α (1 - p) + (1 - α) p$ is binary convolution. This is strictly greater than $I (X; Y) = 1 - H (p)$ for $0 < p < 1/2$ .

The gap $C_{W} - I (X; Y)$ represents the rate of additional shared randomness needed beyond the mutual information to enable distributed generation of the joint distribution.

Common information and channel capacity

There is a deep connection between common information and channel capacity. The Wyner common information $C_{W} (X; Y)$ equals the minimum rate of communication needed for the "distribution generation" problem: two terminals observe independent randomness and want to generate $(X, Y)$ with the correct joint distribution using the minimum rate of one-way communication.

This connects to the interactive communication complexity of generating correlated random variables, which has applications in cryptography (key agreement), distributed computing, and mechanism design.

Common information and the Gray-Wyner network

The Gray-Wyner network is a source coding problem where a single encoder observes $(X^{n}, Y^{n})$ and sends three messages: a common message $W_{0}$ to both decoders, and private messages $W_{1}$ and $W_{2}$ to decoders 1 and 2 respectively. The rate region is characterized by:

R_{0} + R_{1} \geq H (X), R_{0} + R_{2} \geq H (Y), R_{0} + R_{1} + R_{2} \geq H (X, Y) .

The minimum common rate $R_{0}$ on the sum-rate boundary equals $C_{W} (X; Y)$ . This provides another operational interpretation: Wyner common information is the minimum rate of common message needed in the optimal Gray-Wyner source coding scheme.

Synthesis. Common information reveals that "what two random variables share" is not a single quantity but a spectrum with three canonical points: Gacs-Korner common information $C_{G K}$ (exact functional commonality), mutual information $I (X; Y)$ (statistical dependence), and Wyner common information $C_{W}$ (minimum shared randomness for distributed generation). The central insight is that these three quantities are generally different because they capture fundamentally different notions of sharing: deterministic extraction, statistical dependence, and stochastic generation. The result builds toward the Gray-Wyner network where $C_{W}$ determines the minimum common-message rate, and connects to Slepian-Wolf coding 46.05.01 where the gap between $C_{G K}$ and $I (X; Y)$ determines how much correlation is exploitable without communication versus how much requires transmission. The foundational reason the ordering $C_{G K} \leq I \leq C_{W}$ is strict in general is that deterministic extraction is much harder than statistical dependence, which is much harder than enabling distributed generation. Putting these together, common information is the conceptual framework that unifies the side-information strand of information theory, quantifying the resource that makes distributed coding possible.

Full proof set Master

Proposition (Gacs-Korner common information via partition refinement). The Gacs-Korner common information can be computed by partition refinement:

Start with the partition $P_{X}$ of the joint sample space $X \times Y$ induced by the value of $X$ : ${x} \times Y$ for each $x$ .
Similarly, partition by $Y$ : $X \times {y}$ for each $y$ .
The common refinement $P_{X} \land P_{Y}$ consists of the non-empty intersections.
The atoms of the common refinement that are singletons within each $X$ -fiber and each $Y$ -fiber define the common function.

Proof. A function $f (X)$ can be determined from $Y$ if and only if for every value $y$ , all $x$ with $p (x, y) > 0$ satisfy $f (x) = c (y)$ for some function $c$ . This means $f$ must be constant on each set ${x : p (x, y) > 0}$ for all $y$ . The common function is the maximal $f$ satisfying both this condition and the condition that $f (X)$ is a function of $Y$ (i.e., $g (Y)$ for some $g$ ). The partition refinement identifies exactly these constraints. $□$

Connections Master

46.01.02 — Mutual information $I (X; Y)$ is the intermediate quantity between Gacs-Korner and Wyner common information; all three measure "shared information" with different operational meanings.
46.05.01 — Slepian-Wolf coding exploits the mutual information $I (X; Y)$ for distributed compression; the Gacs-Korner common part can be extracted without any communication.
46.05.02 — Wyner-Ziv rate-distortion with side information depends on the mutual information structure; common information determines what is freely available and what must be communicated.
46.05.03 — Gelfand-Pinsker coding uses the transmitter's knowledge of channel state; the common information between state and output determines the DPC rate.
46.06.01 — The MAC with correlated messages has a capacity region that depends on common information between the messages.

Historical & philosophical context Master

Peter Gacs and Janos Korner published "Common Information is Far Less Than Mutual Information" in Problems of Control and Information Theory (vol. 2, no. 2, 1973, pp. 149-162). The paper introduced the common-part definition and showed that it is generally strictly less than mutual information, with equality only when the joint distribution has a special product structure. The title captures the key insight: mutual information measures statistical dependence, which is much larger than what can be extracted as a common function.

Aaron Wyner published "The Common Information of Two Dependent Random Variables" in the IEEE Transactions on Information Theory (IT-21, no. 2, 1975, pp. 163-179). Wyner's definition was motivated by the distributed generation problem: how much shared randomness do two agents need to generate a joint distribution? The answer — the Wyner common information — is generally larger than mutual information, because the shared randomness must enable correct joint sampling, not merely capture statistical dependence.

Rudolf Ahlswede and Janos Korner extended the framework in "On the Common Information of Two Discrete Random Variables" (Problems of Control and Information Theory, 1975), establishing further properties and connecting common information to multi-user source coding.

The Gray-Wyner network (Gray and Wyner, 1974) provided the first operational interpretation of Wyner common information as the minimum common-message rate, connecting the abstract quantity to a concrete source coding problem.

Bibliography Master

@article{wyner1975,
  author  = {Wyner, A. D.},
  title   = {The Common Information of Two Dependent Random Variables},
  journal = {IEEE Transactions on Information Theory},
  volume  = {IT-21},
  number  = {2},
  pages   = {163--179},
  year    = {1975},
}
@article{gacs-korner1973,
  author  = {Gacs, P. and Korner, J.},
  title   = {Common Information is Far Less Than Mutual Information},
  journal = {Problems of Control and Information Theory},
  volume  = {2},
  number  = {2},
  pages   = {149--162},
  year    = {1973},
}
@book{cover-thomas2006,
  author    = {Cover, T. M. and Thomas, J. A.},
  title     = {Elements of Information Theory},
  edition   = {2nd},
  publisher = {Wiley},
  year      = {2006},
}
@article{ahlswede-korner1975,
  author  = {Ahlswede, R. and Korner, J.},
  title   = {On the Common Information of Two Discrete Random Variables},
  journal = {Problems of Control and Information Theory},
  volume  = {4},
  pages   = {37--52},
  year    = {1975},
}

Prerequisites

46.05.01
46.01.02

Tier anchors

beginner: Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §15.8 (how much do two random variables have in common? two competing definitions with different operational meanings)
intermediate: Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §15.8 (Wyner common information and Gacs-Korner common information, their properties, and the gap between them)
master: Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §15.8; Wyner 1975 The common information of two dependent random variables; Gacs & Korner 1973 Common information is far less than mutual information; Ahlswede & Korner 1975 On the common information of two discrete random variables

References

Wyner, A. D. — The Common Information of Two Dependent Random Variables · IEEE Transactions on Information Theory IT-21(2) (1975) 163-179; introduces the common information $C_{W} (X; Y) = min_{X \to W \to Y} I (X, Y; W)$ as the minimum rate of common randomness $W$ needed for two agents to separately generate $X$ and $Y$ with the correct joint distribution. Wyner proves $I (X; Y) \leq C_{W} (X; Y) \leq min (H (X), H (Y))$ and shows that $C_{W} (X; Y) = I (X; Y)$ if and only if $X$ and $Y$ are "doubly symmetric" — a strong condition rarely satisfied in practice.
Gacs, P. & Korner, J. — Common Information is Far Less Than Mutual Information · Problems of Control and Information Theory 2(2) (1973) 149-162; introduces the Gacs-Korner common information $C_{G K} (X; Y)$ as the entropy of the "common part" of $X$ and $Y$ — the maximal function $f (X)$ that can be determined from either $X$ or $Y$ alone. They show $C_{G K} (X; Y) \leq I (X; Y)$ with strict inequality in general, hence the title: common information (in their sense) is far less than mutual information.
Cover, T. M. & Thomas, J. A. — Elements of Information Theory (2nd ed.) · Wiley (2006). Section 15.8: the two definitions of common information, their properties, the relationship to Slepian-Wolf coding, and examples. Wyner common information is the minimum rate of shared randomness for distributed generation; Gacs-Korner common information is the entropy of the common function.

Estimated time

beginner: 15m
intermediate: 45m
master: 90m