本文探讨了在两个随机变量中是否存在一个近似的最大冗余Ω的问题。文章首先介绍了精确冗余和近似冗余的概念，并提出了对最大冗余Ω的定义和要求。文章的核心是悬赏500美元，寻找证明在任何两个随机变量X1和X2上都存在满足上述要求的Ω。文章还讨论了误差界限的合理性，以及该问题对解决其他悬赏问题和简化自然潜变量计算的潜在价值。最后，文章简要介绍了精确情况下的证明，并解释了该问题的重要性。

💡精确冗余是指一个随机变量Γ，当且仅当X1→X2→Γ和X2→X1→Γ时，X1和X2给出了关于Γ的完全相同的信息，即P[Γ|X1]=P[Γ|X2]=P[Γ|X]。

🔍近似冗余通过近似上述条件定义，用ϵred来衡量近似程度，即ϵred≥DKL(P[X,Γ]||P[X1]P[X2|X1]P[Γ|X2])和ϵred≥DKL(P[X,Γ]||P[X2]P[X1|X2]P[Γ|X1])。

🏆悬赏目标是证明存在一个近似的最大冗余Ω，它包含(近似地)其他任何冗余包含的关于X的所有信息，并满足X→Ω→Γ，且Ω是X的近似确定性函数，即ϵdet≥H(Ω|X)。

💰悬赏金额为500美元，如果误差界限足够合理，则可以解决另一个悬赏问题，总计1000美元。

💡解决该问题对于解决其他悬赏问题、改进Telephone Theorem以及简化自然潜变量的数值计算具有重要意义。

Published on May 6, 2025 11:05 PM GMT

A lot of our work involves "redunds".^[1] A random variable $\Gamma$ is a(n exact) redund over two random variables $X_1,X_2$ exactly when both

$X_1\to X_2\to \Gamma$

$X_2\to X_1\to \Gamma$

Conceptually, these two diagrams say that $X_1$ gives exactly the same information about $\Gamma$ as all of $X$, and $X_2$ gives exactly the same information about $\Gamma$ as all of $X$; whatever information $X$ contains about $\Gamma$ is redundantly represented in $X_1$ and $X_2$. Unpacking the diagrammatic notation and simplifying a little, the diagrams say $P\left[\Gamma |X_1\right]=P\left[\Gamma |X_2\right]=P\left[\Gamma |X\right]$ for all $X$ such that $P\left[X\right]>0$.

The exact redundancy conditions are too restrictive to be of much practical relevance, but we are more interested in approximate redunds. Approximate redunds are defined by approximate versions of the same two diagrams:

Unpacking the diagrammatic notation, these two diagrams say

${ϵ}_{red}\ge D_{KL}\left(P\right[X,\Gamma \left]||P\right[X_1\left]P\right[X_2|X_1\left]P\right[\Gamma |X_2\left]\right)$

${ϵ}_{red}\ge D_{KL}\left(P\right[X,\Gamma \left]||P\right[X_2\left]P\right[X_1|X_2\left]P\right[\Gamma |X_1\left]\right)$

This bounty problem is about the existence of a(n approximate) maximal redund $\Omega$: a redund which contains (approximately) all the information about $X$ contained in any other (approximate) redund. Diagrammatically, a maximal redund $\Omega$ satisfies:

Finally, we'd like our maximal redund $\Omega$ to be an approximately deterministic function of $X$, i.e. ${ϵ}_{det}\ge H\left(\Omega |X\right)$, which is equivalent to the diagram

What We Want For The Bounty

This bounty pays out $500 for establishing that there always, over any two random variables $X_1$, $X_2$, exists an $\Omega$ satisfying the requirements above, i.e.

... with reasonable error bounds.

What counts as reasonable error bounds? We're expecting all the other $ϵ$'s to scale with ${ϵ}_2$ in the diagrams above, and ideally be small constant multiples of ${ϵ}_2$. In other words: the higher the approximation error on allowable redunds $\Gamma$, the more approximation error we allow for all the conditions on $\Omega$. Reasonableness of error bound is partially a judgement call on our part, but small constant (like e.g. 2 or 3) multiples of ${ϵ}_2$ would definitely suffice.

Bounds should be global, i.e. apply even when ${ϵ}_2$ is large. We're not interested in e.g. first or second order approximations for small ${ϵ}_2$ unless they provably apply globally.

If the error bounds are sufficiently reasonable, a solution to this problem will also solve our other open bounty problem, paying out another $500, for a total of $1000.

If people post major intermediate steps which are load-bearing for an eventual solution, we might allocate the bounty based on our judgement of different peoples' relative contributions; the hope is to incentivize sharing intermediate results.

We might also partially pay out for counterexamples. That's a judgement call depending on how thoroughly the counterexample kills hope of any theorem vaguely along the lines intended.

In terms of rigor and allowable assumptions, roughly the level of rigor and assumptions in the posts linked above is fine.

Some Intuition From The Exact Case

A proof in the exact case is straightforward; we'll walk through it here to build some intuition.

The exact redundancy conditions say

$P\left[\Gamma |X\right]=P\left[\Gamma |X_1\right]=P\left[\Gamma |X_2\right]$

wherever $P\left[X\right]>0$. So, we can form a bipartite graph, where each vertex represents a value $x_1$ of $X_1$ or a value $x_2$ of $X_2$, and two vertices are connected iff $P[X_1=x_1,X_2=x_2]>0$. Then the definition of redundancy  says that, for ANY redund $\Gamma$, $P\left[\Gamma |X_1\right]$ and $P\left[\Gamma |X_2\right]$ are the same for ANY values of $X_1$ and $X_2$ (respectively) in the same connected component.

So, let $f\left(X\right)$ be defined as the connected component in which $X$ falls. For any redund $\Gamma$, $P\left[\Gamma |X\right]$ must be a function of $f\left(X\right)$ (since two $X$-values in the same connected component have the same $P\left[\Gamma |X\right]$). Thus

$X\to f\left(X\right)\to \Gamma$

$f\left(X\right)$ is therefore a(n exactly) deterministic function of $X$, and (exactly) mediates between X and any redund $\Gamma$. Thus, $f\left(X\right)$ satisfies our requirements, in the exact case (i.e. when ${ϵ}_2=0$).

Alas, this proof does not easily generalize to the approximate case.

Why We Want This

This is a conjecture which we've had on the back burner for a while, and it would be relevant in many places. It would solve our other open bounty problem, it would likely be our starting point for a new version of the Telephone Theorem which more explicitly connects to the natural latents framework, and it would directly simplify the problem of computing natural latents numerically. Probably there are other use-cases which we're not thinking about right at the moment.

 

1. ^{^}

   A lot of our work involves "redunds".

Discuss