How to define the statistical distance between two probabilistic algorithms?

Question

Let $$ \begin{aligned} F_{i} \colon \{\, 0,1 \,\}^* \times \{\, 0,1 \,\}^* &\to \{\, 0,1 \,\}^* \\ (k, x) &\mapsto y \\ \end{aligned} $$ for $i \in \{\, 1,2 \,\}$. As we known, for every oracle algorithm $\mathcal{D}$ the distance between $F_{1}$ and $F_{2}$ with respect to $\mathcal{A}$ is defined as

$$\mathrm{Dist}_{\mathcal{D}}^{F_{1}, F_{2}}(l) = \left\vert \Pr \left[ k \gets \{\, 0,1 \,\}^l, \mathcal{D}^{F_{1}(k, \cdot)}(1^l) = 1 \right] - \Pr \left[ k \gets \{\, 0,1 \,\}^l, \mathcal{D}^{F_{2}(k, \cdot)}(1^l) = 1 \right] \right\vert$$

I think it is meaningful to consider the computational indistinguishability of two probabilistic algorithms. Let $A_{1}$ and $A_{2}$ be two probabilistic algorithms. Formally, for $i \in \{\, 1,2 \,\}$, $$ \begin{aligned} A_{i} \colon S_{l} \times \{\, 0,1 \,\}^* &\to \{\, 0,1 \,\}^* \\ (\alpha, x) &\mapsto y \\ \end{aligned} $$ Thus, $A_{i}(x) = A_{i}(\alpha, x)$ where $\alpha$ is uniformly chosen in $S_{l}$. We can still define the computational distance between $A_{1}$ and $A_{2}$, $$\mathrm{Dist}_{\mathcal{D}}^{A_{1}, A_{2}}(l) = \left\vert \Pr \left[ \mathcal{D}^{A_{1}(\cdot)}(1^l) = 1 \right] - \Pr \left[ \mathcal{D}^{A_{2}(\cdot)}(1^l) = 1 \right] \right\vert$$

We know that the statistical distance between two functions is $$2\mathrm{Dist}^{F_{1}, F_{2}}(l) = \sum_{f}\left\vert \Pr\left[ k \gets \{\, 0,1 \,\}^l, F_{1}(k, \cdot) = f(\cdot) \right] - \Pr \left[ k \gets \{\, 0,1 \,\}^l, F_{2}(k, \cdot) = f(\cdot) \right] \right\vert$$ However, I have no ideal how to define the statistical distance between two probabilistic algorithms.

Answer 1

In general, total variation distance—which is the specific metric you're talking about, one of many that might be called ‘statistical distance’—of two random variables $P$ and $Q$ is defined by $$\sup_A |\Pr[A(P)] - \Pr[A(Q)]|,$$ taken over all random decision algorithms $A$. For the computational version, we simply restrict $A$ to be, say, a cost-limited algorithm that examines only $q$ parts of the variable—if it is a bit string, examines only $q$ bits; if it is a function, queries it at only $q$ points.

If the support is finite, the total variation distance coincides with $$\frac 1 2 \sum_x |\Pr[P = x] - \Pr[Q = x]|,$$ taken over the common support of $P$ and $Q$.

This notion is the same whether $P$ and $Q$ are supported on coin flips, integers, functions, perfectly normal beasts, sets, Riemannian manifolds, probabilistic algorithms, or bit strings (for some of these, to be meaningful, you may have to replace ‘random decision algorithm’ by ‘measurable function’).

Once you set down what a decision algorithm can do with a probabilistic algorithm, the answer will fall out. The usual notion formalizing probabilistic algorithms, as you observe, is just a deterministic function with parameters for all the coin flips it needs—of course, on some inputs and coin flips the algorithm may diverge, which we formally represent by ‘returning’ $\bot$. As such, it's not substantively different from your keyed functions.