# Showing that Normalized Redundancy is nonreliant on the properties of Bijection and Monotonicity

In information theory, the concept of mutual information states that for two features of arbitrary discretized probability, the following formula holds true:

\begin{aligned} I(X;Y) = \sum_{y \in Y} \sum_{x \in X} \ p(x,y)\ \log_b{ \left( \frac{p(x,y)}{p_1(x)\ p_2(y)} \right) } \end{aligned}

And that for continuous distributions: \begin{aligned} I(X;Y) = \int_Y \int_X \ p(x,y)\ \log_b{ \left( \frac{p(x,y)}{p_1(x)\ p_2(y)} \right) } \; dx\ dy \end{aligned}

(Source.)

It is further posited, as an application of mutual information, computing the nat, bit, or ban length of the combined source signal, with respect to the log base used, provides a useful normalized metric that can be used to show bags of information explain, or do not explain, one other.

That is, the absolute redundancy of information, $R$, may be expressed in terms of mutual information and the Shannon entropy of $X$ and $Y$ as:

\begin{aligned} R= \frac{I(X;Y)}{H(X)+H(Y)} \end{aligned}

Where $H(X)$ is defined in the discrete case as: \begin{aligned} H(X) =-\sum_{x \in X}\ {p(x)\ \log_b\ p(x)}, \end{aligned}

$H(Y)$ using the same formula.

One may then normalize this value by computing $R_{\max }$ as: \begin{aligned} R_{\max }=\frac{\min (H(X),H(Y))}{H(X)+H(Y)} \end{aligned}

Then, using the properties of mutual information and Shannon entropy, normalize between $[0, R_{\max }]$, since the result is guaranteed to be positive and upwardly bounded by $R_{\max }$.

Assuming all of this is correct, I am attempting to use this as a drop-in replacement for Pearson's and Spearman's correlations for determining feature dependence in pairspace, for relationships that are neither bijective nor monotonic (that is, for bags of categorical data with overlap and no defined natural order).

My question, then, is a means to or illustration of these properties (a lack of reliance on bijection and monotonicity) in closed form, such that I may present these data to my peers in a mathematically rigorous way. I am not a mathematician, and as point of fact, discovering these properties took me a great deal of research to piece together.

My long term goal is to use these formulae to provide a strong model for explainability without relying on crude determinants for correlation. So, a bonus question better directed towards Stats.SE, which may see a subset of this question: how might one derive a convincing PDF or discretized p-value from normalized redundancy within the result space? My intuition states that it's a simple matter of discretization, using normalized redundancy as a score.

-
Sounds like you want some empirical evidence to justify your choice of the relevant quantity for determining feature dependence in pairspace. –  sai Jul 7 '12 at 3:01