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.


1 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.

  • $\begingroup$ Your answer make me understand it deeper. "of course, on some ... keyed functions", I don't get the point of this sentence. As your answer, the probabilistic algorithm is just one function with parameters for all the coin flips it needs. So $A_{i}$ is just a one-point distribution, right? Thus, the statistical distance between them is 1 iff $A_{1} = A_{2}$. Am I right? $\endgroup$
    – Blanco
    Apr 25, 2019 at 14:16
  • $\begingroup$ Consider a random algorithm that does rejection sampling. Rejection sampling returns an answer after any finite number of steps with some probability, but there exist sequences of coins under which rejection sampling never returns and keeps rejecting them for all eternity. That notion of diverging is what $\bot$ represents: if the coin always returns tails and the algorithm is waiting for heads, we represent that by saying $A(00000…, x) = \bot$. $\endgroup$ Apr 25, 2019 at 14:22
  • $\begingroup$ Not sure what you mean by ‘one-point distribution’. The statistical distance is 1 iff they agree except possibly on sets of measure zero. $\endgroup$ Apr 25, 2019 at 14:24
  • $\begingroup$ As you say, we always talk about the distance of two variables $P$ and $Q$. If $P, Q$ are functions, they are chosen from the function spaces (e.g. $\{ F_k \mid k \in \{0,1\}^* \}$. If $P,Q$ are probabilistic algorithms, $P$ is always $A_{1}$ which is a specific algorithm. It leads to that $P$ is a one-point distribution. In the other hand, when the distinguisher asks the access of $A_{1}$ the random input $\alpha$ is not same every time. But the distinguisher always ask the same one, in the case of functions. $\endgroup$
    – Blanco
    Apr 25, 2019 at 16:27
  • $\begingroup$ @TeamBright Well, it would be better to say that $P$ is the random function $x \mapsto A_1(C, x)$, where $C$ is a random variable representing the algorithm's coins. $\endgroup$ Apr 25, 2019 at 16:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.