7
$\begingroup$

Given a function $f$ from a finite set $X$ to itself, it seems natural to consider $\kappa_f := (\sum_{x \in X} |f^{-1}(x)|^2)/|X|$ as a measure of the non-invertibility of $f$: it equals 1 if $f$ is invertible, equals $|X|$ if $f$ is constant, and is strictly between 1 and $|X|$ otherwise. It also admits a probabilistic interpretation: $\kappa_f / |X|$ equals the probability that two IID draws $x,x’$ chosen uniformly from $X$ satisfy $f(x)=f(x’)$. Does the quantity $\kappa$ (or the related quantities $\kappa |X|$ or $\kappa / |X|$) have a standard name?

Note: I’ve added the graph-theory tag since analogous quantities (mean-squared indegree for directed graphs, mean-squared degree for graphs) may already have been considered there.

Note: I've also added the information-theory tag since $\kappa$ is a measure of how much information (in the colloquial sense) is lost when passing from $x$ to $f(x)$ (where $x$ denotes a random draw from the uniform distribution on $X$); it seems possible that there are known results linking this sort of information to Shannon information.

Update: I'm considering calling this quantity the "degree" of $f$. If you think this is a bad choice, please post to The degree of a (combinatorial) selfmap explaining why.

$\endgroup$
1
  • 1
    $\begingroup$ Perhaps mean square fiber multiplicity. $\endgroup$
    – Ben McKay
    Nov 20, 2019 at 13:31

3 Answers 3

5
$\begingroup$

You're right that this is a significant quantity information-theoretically. It's essentially the Rényi entropy of order $2$, as I'll explain.

First let me generalize your setting ever so slightly, because I find it a distraction that you've made the domain and codomain the same. For any function $f: X \to Y$ between finite sets, put $$ \kappa_f = \sum_{y \in Y} |f^{-1}(y)|^2/|X|. $$ This extends your definition, and continues to have the kind of properties you want: $\kappa_f = 1$ iff $f$ is injective, and $\kappa_f = |X|$ iff $f$ is constant. Anyway, you can ignore my generalization if you want and stick with $Y = X$.

The function $f: X \to Y$ gives rise to a probability distribution $\mathbf{p} = (p_y)_{y \in Y}$ on $Y$, defined by $$ p_y = |f^{-1}(y)|/|X|. $$ Like any probability distribution on any finite set, $\mathbf{p}$ has a Rényi entropy of order $q$ for every $q \in [-\infty, \infty]$. When $q \neq 1, \pm\infty$, this is by definition $$ H_q(\mathbf{p}) = \frac{1}{1 - q} \log \sum_y p_y^q, $$ where the sum runs over the support of $\mathbf{p}$. The exceptional cases are got by taking limits in $q$, which explicitly means that $H_1$ is Shannon entropy: $$ H_1(\mathbf{p}) = - \sum_y p_y \log p_y $$ and that $$ H_\infty(\mathbf{p}) = -\log\max_y p_y, \qquad H_{-\infty}(\mathbf{p}) = -\log\min_y p_y $$ (where again, the min is over the support of $\mathbf{p}$).

Many of the good properties of Shannon entropy are shared by the Rényi entropies $H_q$. For example, over all probability distributions $\mathbf{p}$ on an $n$-element set, the maximum value of $H_q(\mathbf{p})$ is $\log n$, which is attained when $\mathbf{p}$ is uniform, and the minimum value is $0$, which is attained when $\mathbf{p} = (0, \ldots, 0, 1, 0, \ldots, 0)$. That's true for every $q \in [-\infty, \infty]$.

Often it's better to work with the exponentials of the Rényi entropies, which I'll write as $D_q = \exp H_q$. For instance, $$ D_2(\mathbf{p}) = 1\Big/\sum_y p_y^2. $$ (D stands for diversity, since ecologists use $D_q$ to measure biodiversity; in ecology, $D_q$ is called the "Hill number" of order $q$.) So the maximum value of $D_q(\mathbf{p})$ over distributions $\mathbf{p}$ on a fixed finite set is the cardinality of that set, not its logarithm.

Returning to your question, we had a function $f: X \to Y$ between finite sets and the induced probability distribution $\mathbf{p}$ on $Y$. It's a trivial manipulation to show that $$ \kappa_f = |X|/D_2(\mathbf{p}). $$ So as I claimed at the start, $\kappa_f$ is essentially (up to a simple transformation) the Rényi entropy of order $2$ (of the distribution $\mathbf{p}$ induced by $f$).

You might also want to consider $$ |X|/D_q(\mathbf{p}) $$ for other values of $q$, especially the Shannon case $q = 1$. Although entropies of order $2$ are the easiest to manipulate (being essentially quadratic forms), it's $q = 1$ that has the really magical properties.

Incidentally, in ecology $D_2(\mathbf{p})$ is known as the Simpson or Gini-Simpson index; there $p_1, \ldots, p_n$ are the relative abundances of the $n$ species in some community. Jack Good wrote in 1982 that it should really bear the name of Turing, but also that "any statistician of this century who wanted a measure of homogeneity would have taken about two seconds to suggest $\sum p_i^2$." Thanks, Jack.

$\endgroup$
4
$\begingroup$

$\lambda(f):=\kappa_f-1$ is called "the coefficient of coalescence of $f$" here:

https://msp.org/pjm/1982/103-2/pjm-v103-n2-p03-p.pdf

(note the typo on p.269, the correct definition appears on p.272).

Of course, $\lambda(f)/|X|$ (the square of the Euclidean distance between the preimage distribution ($p(x)=|f^{-1}(x)|/|X|$) and the uniform distribution on $X$), and $\lambda(f)\,|X|$ (the value of the $\chi^2$ test statistic for a (uniform) random mapping) are specific instances of well known concepts (but to the best of my knowledge without special names).

$\endgroup$
0
$\begingroup$

There is a relationship between difficulty of guessing/predicting an unknown random variable $X$, when only atomic queries of the type

Is $X=a$?

are allowed. Such non-powerful queries apply, for example, to guessing passwords where you can't ask

Is the first character of the password $a$?

but you can try the query

Is the password $astor\&Piazzola$?

In particular, the direct use of Shannon entropy can give misleading results but Renyi entropies help, as first demonstrated by Arikan [1] and further by Boztas [2] in response to a question of Jim Massey in the 1994 IEEE International Symposium on Information Theory.

For example, if $X$ is a discrete random variable with $M$ points in its support $H(X)$ can be close to its maximum value $\log M$ while the probability of an optimal guessor (who asks questions of the form Is $X=a$? in decreasing order of the probabilites $\mathbb{P}(a),$ discovering the actual value of $X$ in $k$ sequential questions is much less than $2^{H(X)}.$

Moreover, not only the expected number of guesses, but arbitary moments of the number of guesses can be related to Renyi entropies of various order.

In particular the expected number of guesses $\mathbb{E}[G]$ to determine $X$ obeys

$$\frac{2^{H_{1/2}(X)}}{H_{max}}\approx \frac{2^{H_{1/2}(X)}}{1 + \log M } =\frac{\sum_{a=1}^{M} \mathbb{P}(a)^{1/2}}{1+\ln M} \leq \mathbb{E}[G]\stackrel{(a)}{\leq}2^{H_{1/2}(X)-1}$$

where $H_{1/2}(X)$ denotes the Renyi entropy of order $\alpha=1/2,$ and $H_{max}$ denotes the maximum entropy (all Renyi entropies, as well as the Shannon entropy are the same when $X$ is uniform). Note that the inequality $(a)$ holds only for a class of guessing sequences, including the optimum guessing sequence, as shown in .

For general moments, the lower bound $$ \frac{\left(\sum_{a=1}^{M} \mathbb{P}(a)^{1/(1+\rho)}\right)^{1+\rho}}{\left(1+\ln M\right)^\rho} \leq \mathbb{E}[G^{\rho}],\quad \rho\geq 0, $$ proved by Arikan follows from the Holder inequality, and the special case of the expectation corresponds to $\rho=1.$

[1]: E. Arikan, An inequality on Guessing and its application to Sequential Decoding, IEEE Trans. Information Theory 42(1), 1996

[2]: S. Boztas, Comments on "An inequality on Guessing and its application to Sequential Decoding", IEEE Trans. Information Theory 43(6), 1997

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.