Return to Question

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.

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.

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.

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.

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?

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.