How to define the statistical distance between two functions?

Question

The statistical difference between two families of distributions of random variables:

Let $\mathrm{\mathbf{X}} = \{ X_{l} \}_{l}$ and $\mathrm{\mathbf{Y}} = \{ Y_{l} \}_{l}$ be two families of distributions of random variables, the statistical difference of $\mathrm{\mathbf{X}}$ and $\mathrm{\mathbf{Y}}$ is defined as $$d^{\mathrm{\mathbf{X}}, \mathrm{\mathbf{Y}}} ( l )= \frac{1}{2}\sum_{s} \left\vert \Pr[X_{l} = s] - \Pr[Y_{l} = s] \right\vert$$

The computational difference between two families of distributions of random variables:

Let $\mathrm{\mathbf{X}} = \{ X_{l} \}_{l}$ and $\mathrm{\mathbf{Y}} = \{ Y_{l} \}_{l}$ be two families of distributions of random variables, for any PPT algorithm $A$, the computational difference of $\mathrm{\mathbf{X}}$ and $\mathrm{\mathbf{Y}}$ is defined as $$d^{\mathrm{\mathbf{X}}, \mathrm{\mathbf{Y}}}_{A} ( l )=\left\vert \Pr[s \leftarrow X_{l} : A \left( 1^{l}, s \right) = 1] - \Pr[s \leftarrow Y_{l} : A \left( 1^{l}, s \right) = 1] \right\vert$$

This notion can be used to define the PRGs.

The computational difference between two families of distributions of functions:

Let $\mathrm{\mathbf{F}} = \{ F_{l} \}_{l}$ and $\mathrm{\mathbf{G}} = \{ G_{l} \}_{l}$ be two families of distributions of functions, for any PPT algorithm $A$, the computational difference of $\mathrm{\mathbf{F}}$ and $\mathrm{\mathbf{G}}$ is defined as $$d^{\mathrm{\mathbf{F}}, \mathrm{\mathbf{G}}}_{A} ( l )= \left\vert \Pr[f \leftarrow F_{l} : A^{f(\cdot)} \left( 1^{l} \right) = 1] - \Pr[g \leftarrow G_{l} : A^{g(\cdot)} \left( 1^{l} \right) = 1] \right\vert$$

This notion can be used to define the PRFs.

I am thinking that there should be a definition about the statistical difference between two families of distributions of functions. (It is denoted as $d^{\mathrm{\mathbf{F}}, \mathrm{\mathbf{G}}} ( l )$).

There is a possible way:

For every input $x \in \{\ 0,1 \,\}^{*}$, let $F_{l} \left( x \right)$ denotes the distribution of $f(x)$ where $f \leftarrow F_{l}$. Maybe one can use $d^{\mathrm{\mathbf{F}}(x),\mathrm{\mathbf{G}}(x)} (\cdot)$ to define the statistical difference between $\mathrm{\mathbf{F}}$ and $\mathrm{\mathbf{G}}$, where $\mathrm{\mathbf{F}}(x) = \{ F_{l}(x) \}_{l}$ and $\mathrm{\mathbf{G}}(x) = \{ G_{l}(x) \}_{l}$.

However, $d^{\mathrm{\mathbf{F}}(x),\mathrm{\mathbf{G}}(x)} (l)$ depends on both $x$ and $l$. Thus, there exists a problem, $d^{\mathrm{\mathbf{F}}(x),\mathrm{\mathbf{G}}(x)} (l)$ may not be consistency for $x$. If I define $$d^{\mathrm{\mathbf{F}},\mathrm{\mathbf{G}}} (l) =\sup_{x \in \{\, 0,1 \,\}^{*}} d^{\mathrm{\mathbf{F}}(x),\mathrm{\mathbf{G}}(x)} (l) =\sup_{x \in \{\, 0,1 \,\}^{*}}\frac{1}{2}\sum_{s} \left\vert \Pr[F_{l}(x) = s] - \Pr[G_{l}(x) = s] \right\vert$$ Then $d^{\mathrm{\mathbf{F}},\mathrm{\mathbf{G}}} (\cdot)$ may be not negligible even if for every $x$, $d^{\mathrm{\mathbf{F}}(x),\mathrm{\mathbf{G}}(x)} (\cdot)$ is negligible.

Answer 1

It can be seen that statistical difference is equivalent to computational difference if a PPT algorithm is replaced by a computationally unbounded one, i.e. an arbitrary function. For distributions of random variables, if $A(1^l,s)=1$ when $\Pr[X_l=s]>\Pr[Y_l=s]$ and $A(1^l,s)=0$ otherwise, then $d_A^{\mathbf X,\mathbf Y}(l)=d^{\mathbf X,\mathbf Y}(l)$, and this is the maximum for any $A$.

For functions, a similar argument can be used: a computationally unbounded algorithm can return $1$ on an arbitrary subset of functions, so it seems that the best choice would be to return $1$ for such $f$ that $\Pr[F_l=f]>\Pr[G_l=f]$. Then, $$d^{\mathbf F,\mathbf G}(l)=d_A^{\mathbf F,\mathbf G}(l)=\frac12\sum\limits_f\lvert\Pr[F_l=f]-\Pr[G_l=f]\rvert.$$ Here, the sum is taken over all possible functions. This sum well-defined, because all summands are nonnegative.