# How to define the statistical distance between two functions?

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.

• I think your definition of statistical distance is missing a factor of $1/2$. Nov 15, 2018 at 12:24
• @ Daniel, you are right, let me correct. I thought the factor does not important here. Nov 16, 2018 at 1:49
• The space of functions with a finite domain is a finite space itself, so you don't need to invent any additional concepts for statistical distance. Apr 25, 2019 at 13:16

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.
• You are right, but I think it is too weak. There exist $\mathrm{\mathbf{F}}$ and $\mathrm{\mathbf{G}}$ such that $d^{\mathrm{\mathbf{F}}, \mathrm{\mathbf{G}}}(l)=1$ even though they are computational indistinguishable. Nov 19, 2018 at 5:48