Another way to see this would be to try and upper bound the distinguishing advantage for any distinguisher and relate that to the statistical distance.

Edit:

Since the following answer is really good, I will just give ideas without proofs.

Was supposed to be :

Since @Mikero's answer is really good...

What happens when you answer late and do not proof-read: self-Facepalm and hides in shame for bragging about my answer

Let $(X, Y)$ be two random variables on the set $\mathcal{X}$. We denote by $\Delta^D(X;Y)$ the distinguishing advantage of a distinguisher $D$ with binary output and by $\delta(X,Y)$ by the maximum distinguishing advantage for $(X,Y)$.(i.e the advantage of one optimal distinguisher).

We need to do two things:

• Give an "explicit description" of a deterministic distinguisher $\mathcal{D}$ that has advantage $\delta(X;Y)$
• show that $\delta(X;Y) = \Delta(X;Y)$
• The conclusion will be the implication in the question

First we show an explicit optimal deterministic distinguisher

For $X$ with distribution $Pr_X[x], x \in \mathcal{X}$ and $Y$ with distribution $Pr_Y[x]$, intuitively an optimal deterministic distinguisher $\mathcal{D}(\cdot)$ would do the following:

• $\mathcal{D}(x) = 0$ if $Pr_X[x] \geq Pr_Y[x]$
• $\mathcal{D}(x) = 1$, otherwise

Let $\mathcal{X}^* = \{x: Pr_X[x] \geq Pr_Y[x]\}$, we can show that $\Delta^{\mathcal{D}}(X,Y) = Pr[Y \in \mathcal{X}^*] - Pr[Y \in \mathcal{X}^*]$.

One can show that $\Delta^{\mathcal{D}}(X;y) = Pr[Y \in \mathcal{X}^*] - Pr[Y \in \mathcal{X}^*] = \delta(X;Y)$

Second, we relate the distinguishing advantage to the statistical distance

We have the following $\forall D, \Delta^D(X;Y) \leq \delta(X;Y)$ by defition, and on the other hand $\delta(X;Y) = \Delta(X;Y)$ therefore we have the following $$\forall D, \Delta^D(X;Y) \leq \Delta(X,Y)$$.

In conclusion the statistical distance gives an upper bound on the performance of any distinguisher, probabilistic included.