Skip to main content
2 of 4
Added a tag
James Propp
  • 19.7k
  • 5
  • 55
  • 136

Quantifying the noninvertibility of a function

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.

James Propp
  • 19.7k
  • 5
  • 55
  • 136