Extension Profile Shape Functions

---
name: extension-profile-shape-functions
description: "Beyond mutual information — extension profiles and shape functions of random variable pairs. Use when analyzing structural properties of joint distributions not captured by mutual information alone, connecting information theory to spectral graph theory, or deriving non-Shannon-type information inequalities."
---

# Extension Profiles and Shape Functions

## Description
A framework for studying the extension profile of jointly distributed random variables (X,Y), defined as the set of all triples (H(X|W), H(Y|W), I(X:Y|W)) obtained by extending the pair with an auxiliary random variable W. Introduces the shape function (Legendre-Fenchel transform of the profile boundary) to characterize structural properties of joint distributions not determined by entropies and mutual information alone.

## Activation Keywords
- extension profile
- shape function
- mutual information beyond
- non-Shannon information inequalities
- Legendre-Fenchel transform
- Gacs-Korner common information
- 扩展轮廓
- 形状函数
- joint distribution structure
- biregular bipartite graph

## Core Mathematical Framework

### Extension Profile Definition
For jointly distributed finite-valued random variables (X,Y):

```
Extension Profile = {(H(X|W), H(Y|W), I(X:Y|W)) : W is auxiliary}
```

This captures structural properties NOT determined solely by:
- H(X), H(Y) (marginal entropies)
- I(X:Y) (mutual information)

### Shape Function
- Defined as the Legendre-Fenchel transform of the nontrivial profile boundary
- Characterizes the achievable region of conditional entropies and conditional mutual information
- General upper and lower bounds in terms of classical information-theoretic quantities

### Graph-Theoretic Interpretation
For pairs uniform on their support:
1. Interpret support as a **biregular bipartite graph**
2. Relate extension profile to combinatorial and spectral properties
3. Bounds on shape function in terms of **second-largest eigenvalue**
4. Small second eigenvalue → restricted class of extensions

### Key Connections
| Concept | Connection |
|---------|-----------|
| Non-Shannon inequalities | Extension profile boundaries |
| Gács-Körner common information | Profile structure |
| Spectral graph theory | Second eigenvalue bounds |
| Biregular bipartite graphs | Support structure |

## Usage Patterns

### Pattern 1: Joint Distribution Analysis
When mutual information alone is insufficient:
1. Compute the extension profile of (X,Y)
2. Map the achievable (H(X|W), H(Y|W), I(X:Y|W)) region
3. Use the shape function to characterize the boundary
4. Identify structural properties hidden from standard measures

### Pattern 2: Spectral Bound Analysis
For uniform-on-support distributions:
1. Construct the biregular bipartite graph from the support
2. Compute the second-largest eigenvalue λ₂
3. Apply the spectral bound on the shape function
4. Small λ₂ implies restricted extensions

### Pattern 3: Non-Shannon Inequality Derivation
When deriving information inequalities beyond Shannon type:
1. Use the extension profile to identify infeasible regions
2. The shape function boundary provides tight constraints
3. Relate to Gács-Körner common information for tightness

## Instructions for Agents

### Step 1: Verify Joint Distribution Structure
- Check if (X,Y) is uniform on support
- If yes: proceed with graph-theoretic interpretation
- If no: use general bounds on shape function

### Step 2: Compute Extension Profile
- Enumerate auxiliary variables W
- Compute (H(X|W), H(Y|W), I(X:Y|W)) for each W
- Map the achievable region in 3D space

### Step 3: Derive Shape Function
- Apply Legendre-Fenchel transform to profile boundary
- Compute upper and lower bounds
- For graph case: use spectral properties

### Step 4: Interpret Results
- Restricted extensions → strong structural constraints
- Non-restricted extensions → flexibility in joint distribution
- Connect to Gács-Körner and spectral graph theory

## Error Handling

### Non-Uniform Support
- The graph-theoretic interpretation requires uniform-on-support
- For non-uniform pairs: use general information-theoretic bounds
- The shape function still exists but lacks spectral interpretation

### Large Alphabet
- Extension profile computation scales with alphabet size
- Use spectral bounds for computational tractability
- The second eigenvalue approach is more efficient

## Resources
- arXiv:2606.23849 - "Beyond Mutual Information: Extension Profiles and Shape Functions of Random Variable Pairs" by Rostislav Matveev, Andrei Romashchenko
- 42 pages, 2 figures