2
$\begingroup$

Let $\mathcal{Y}$ and $\mathcal{X}$ be finite sets and let $Q_Y$ be a fixed probability mass function on $\mathcal{Y}$. Also, let $P_{X | Y}$ be some fixed conditional distribution on $\mathcal{X} \times \mathcal{Y}$ and let $R$ be a positive constant.

We define

\begin{equation} A^- =\min_{Q_{U | Y}: I(U;Y) \leq R} \max_{Q_{X | Y}} \left[H(X | U) - D(Q_{X | Y} || P_{X | Y})\right], \end{equation}

where $\max_{Q_{X | Y}}$ is taken over the conditional distributions on $\mathcal{X} \times \mathcal{Y}$ and $\min_{Q_{U | Y}}$ is taken over the conditional distributions on $\mathcal{U} \times \mathcal{Y}$ with $\mathcal{U}$ being any finite set. $D$ denotes the Kullback-Leibler Divergence, $H$ is the Shannon Entropy and $I$ the mutual information. In the above expression, $I(U;Y)$ is computed with respect to $Q_YQ_{U | Y}$ and $H(X | U)$ is computed with respect to the Markov chain $Q_YQ_{U | Y}Q_{X | Y}$.

Next, we define

\begin{equation} A^+ =\min_{Q_{U | Y}: I(U;Y) \leq R} \max_{Q_{X | Y, U}} \left[H(X | U) - D(Q_{X | Y, U} || P_{X | Y})\right], \end{equation}

where $\max_{Q_{X | Y, U}}$ is taken over the conditional distributions on $\mathcal{X} \times \mathcal{Y} \times \mathcal{U}$ and $\min_{Q_{U | Y}}$ is taken over the conditional distributions on $\mathcal{U} \times \mathcal{Y}$ with $\mathcal{U}$ being any finite set. $I(U;Y)$ is computed with respect to $Q_YQ_{U | Y}$ and $H(X | U)$ is computed with respect to $Q_YQ_{U | Y}Q_{X | Y, U}$ (i.e., no longer with respect to a Markov chain).

Numerical evidence appears to suggest that

\begin{equation} A^+ = A^-. \end{equation}

I appreciate any ideas on how one might go about proving or disproving the (implied) conjecture. Observe that while in $A^+$ we have more freedom in tuning $H(X | U)$, we potentially pay for this freedom as $D(Q_{X | Y, U} || P_{X | Y}) \geq D(Q_{X | Y} || P_{X | Y})$ with equality iff $Q_{X | Y, U} = Q_{X | Y}$.

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.