authored by Premmi and Beguène
Summary of results with respect to Total Variation Distance
You can read Part 1 of the story here and Part 2 here.
For proofs of all results enumerated in this post refer to Part 3.
Total Variation Distance
In probability theory, the total variation distance is a distance measure for probability distributions. It is also called statistical distance, statistical difference or variational distance.
Definition
The total variation distance between two probability distributions \mathcal{P_0 \text{ and } P_1} on a countable set of real numbers \mathcal{S} is defined by,
\mathcal{\big\|P_0 - P_1\big\|}_{TV} = \underset{\mathcal{A} \,\subset\, \mathcal{S}}{\text{max}} \mathcal{\big|P_0(A) - P_1(A) \big|} .Informally, it is the largest possible difference in probabilities assigned to the same event by two distributions on the countable set of real numbers \mathcal{S}.
Total Variation Distance is a metric
Since total variation distance is a distance function, it satisfies the following conditions:
- \mathcal{\big\|P_0 - P_1\big\|}_{TV} \geq 0.
- \mathcal{\big\|P_0 - P_1\big\|}_{TV} = 0 if and only if \mathcal{P_0 = P_1}.
- It is symmetric : \mathcal{\big\|P_0 - P_1\big\|}_{TV} = \mathcal{\big\|P_1 - P_0\big\|}_{TV}.
- It satisfies the triangle inequality : \mathcal{\big\|P_0 - P_1\big\|}_{TV} \leq \mathcal{\big\|P_0 - P_2\big\|}_{TV} + \mathcal{\big\|P_2 - P_1\big\|}_{TV}, where \mathcal{P_2} is a probability distribution on the same countable set of real numbers \mathcal{S}.
Total Variation Distance is half of \mathcal{L_1} distance.
If \mathcal{S} is a countable (i.e., finite or countably infinite) set of real numbers,
\mathcal{\big\|P_0 - P_1\big\|}_{TV} = \frac{1}{2} \mathcal{\big\|P_0 - P_1\big\|}_1i.e., the total variation distance between \mathcal{P_0 \text{ and } P_1} is half the \mathcal{L_1} distance between \mathcal{P_0 \text{ and } P_1}.
By definition of \mathcal{L_1} norm,
\mathcal{\big\|P_0 - P_1\big\|}_1 = \sum_{\mathcal{s \in S}} \big|\mathcal{P_0(s) - P_1(s)}\big|We have already proved in Part 3 that if \mathcal{S} is a countable set of real numbers, then,
\mathcal{\big\|P_0 - P_1\big\|}_{TV} = \frac{1}{2} \sum_{\mathcal{s \in S}} \big|\mathcal{P_0(s) - P_1(s)}\big|Distinguishing Advantage and Distinguishing Distance
For a deep intuitive understanding of advantage refer to this and this.
As a quick recap,
\begin{equation*}
\begin{split}
\text{Advantage of adversary with respect to challenger} & = \text{Probability that the adversary wins } - \text{Probability that the challenger wins } \\
& = \text{Probability that the adversary wins } - \text{Probability that the adversary loses } \\
\end{split}
\end{equation*} Let us assume that the adversary uses a function, \mathcal{D : S \rightarrow \{0, 1\}}, to distinguish between the two probability distributions \mathcal{P_0 \text{ and } P_1} on the countable set of real numbers \mathcal{S} i.e., \mathcal{D} is a distinguisher function that takes as input a real number \mathcal{s} from the set \mathcal{S} and outputs either a \mathcal{0 \text{ or } 1}.
Mathematically, we can view \mathcal{D} as a special kind of function of a random variable that instead of mapping the set \mathcal{S} of real numbers to another set of real numbers, maps it to either of two values \mathcal{0 \text{ or } 1}. So, \mathcal{D(P_0)} is a random variable that maps the real number \mathcal{s \in S}, where \mathcal{s} is drawn from the probability distribution of \mathcal{P_0}, to either a \mathcal{0 \text{ or } 1}. Similarly \mathcal{D(P_1)}, takes as input \mathcal{s \in S}, where \mathcal{s} is drawn from the probability distribution of \mathcal{P_1} and outputs either a \mathcal{0 \text{ or } 1}.
\begin{equation*}
\begin{split}
\textit{Distinguishing Advantage} & = \big|\text{Advantage of adversary with respect to challenger}\big| \\
& = \big|P(\text{Adversary wins}) - P(\text{Adversary loses})\big| \\
& = \frac{1}{2} \times \Big\{\big|P[\mathcal{D(P_0) = 0}] + P[\mathcal{D(P_1) = 1}] - P[\mathcal{D(P_0) = 1}] - P[\mathcal{D(P_1) = 0}]\big|\Big\} \\
& = \frac{1}{2} \times \Big\{\big|P[\mathcal{D(P_0) = 0}] - P[\mathcal{D(P_1) = 0}] + P[\mathcal{D(P_1) = 1}] - P[\mathcal{D(P_0) = 1}]\big|\Big\} \\
& = \frac{1}{2} \times \Big\{\big|1 - P[\mathcal{D(P_0) = 1}] - 1 + P[\mathcal{D(P_1) = 1}] + P[\mathcal{D(P_1) = 1}] - P[\mathcal{D(P_0) = 1}]\big|\Big\} \\
& = \frac{1}{2} \times \Big\{2 \times \big|P[\mathcal{D(P_1) = 1}] - P[\mathcal{D(P_0) = 1}]\big|\Big\} \\
& = \big|P[\mathcal{D(P_1) = 1}] - P[\mathcal{D(P_0) = 1}]\big| \\
& = \big|P[\mathcal{D(P_0) = 1}] - P[\mathcal{D(P_1) = 1}]\big| \\
\end{split}
\end{equation*} If distributions \mathcal{P_0 \text{ and } P_1} are distinguishable by the adversary, then the probability that \mathcal{D} outputs \mathcal{1} on getting \mathcal{s \in S} drawn from \mathcal{P_0} as its input will be significantly different than the probability that \mathcal{D} outputs \mathcal{1} on getting \mathcal{s \in S} drawn from \mathcal{P_1} as its input. Hence to calculate the distinguishing advantage we only need the absolute difference between P[\mathcal{D(P_0) = 1}] \text{ and } P[\mathcal{D(P_1) = 1}] since we only care about the magnitude of their difference.
Alternate notation for deriving Distinguishing Advantage
Sometimes an alternate notation is used in deriving distinguishing advantage. We will briefly describe this notation and derive distinguishing advantage in terms of it.
Let \mathcal{W_0} be the event that the adversary (or equivalently the distinguisher \mathcal{D}) outputs \mathcal{1} when given as input \mathcal{s \in S} drawn from distribution \mathcal{P_0}. Hence,
P[\mathcal{W_0}] = P[\mathcal{D} \text{ outputs 1 | } \mathcal{s \in S} \text{ drawn from } \mathcal{P_0} \text{ as input}]. So,
P[\mathcal{W_0}] = P[\mathcal{D(P_0) = 1}]Similarly, let
\begin{equation*}
\begin{split}
P[\mathcal{W_0'}] & = P[\mathcal{D(P_0) = 0}], \\
P[\mathcal{W_1}] & = P[\mathcal{D(P_1) = 1}] \text{ and} \\
P[\mathcal{W_1'}] & = P[\mathcal{D(P_1) = 0}]
\end{split}
\end{equation*} By the axiom of probability,
\begin{equation*}
\begin{split}
P[\mathcal{W_0}] + P[\mathcal{W_0'}] & = 1 \text{ and} \\
P[\mathcal{W_1}] + P[\mathcal{W_1'}] & = 1 \\
\end{split}
\end{equation*} \begin{equation*}
\begin{split}
\textit{Distinguishing Advantage} & = \big|\text{Advantage of adversary with respect to challenger}\big| \\
& = \big|P(\text{Adversary wins}) - P(\text{Adversary loses})\big| \\
& = \frac{1}{2} \times \Big\{\big|P[\mathcal{W_0'}] + P[\mathcal{W_1}] - P[\mathcal{W_0}] - P[\mathcal{W_1'}]\big|\Big\} \\
& = \frac{1}{2} \times \Big\{\big|P[\mathcal{W_0'}] - P[\mathcal{W_1'}] + P[\mathcal{W_1}] - P[\mathcal{W_0}]\big|\Big\} \\
& = \frac{1}{2} \times \Big\{\big|1 - P[\mathcal{W_0}] - 1 + P[\mathcal{W_1}] + P[\mathcal{W_1}] - P[\mathcal{W_0}]\big|\Big\} \\
&\hspace{0.5 cm} \text{(substituting equation (8a) in the above equation)}\\
& = \frac{1}{2} \times \Big\{2 \times \big|P[\mathcal{W_1}] - P[\mathcal{W_0}]\big|\Big\} \\
& = \big|P[\mathcal{W_1}] - P[\mathcal{W_0}] \big| \\
& = \big|P[\mathcal{W_0}] - P[\mathcal{W_1}] \big| \\
\end{split}
\end{equation*} Hence,
\big|P[\mathcal{D(P_0) = 1}] - P[\mathcal{D(P_1) = 1}]\big| = \big|P[\mathcal{W_0}] - P[\mathcal{W_1}] \big|For a given challenger \mathcal{C} and a given adversary \mathcal{A}, the advantage of adversary \mathcal{A} with respect to challenger \mathcal{C} is denoted by \text{Adv}\mathcal{[A, C]} and is defined as,
\text{Adv}\mathcal{[A, C]} = \big|P[\mathcal{W_0}] - P[\mathcal{W_1}] \big|where \mathcal{W_0} is the event that the adversary \mathcal{A} outputs \mathcal{1} when given as input \mathcal{s \in S} (where \mathcal{S} is a countable set of real numbers) drawn from distribution \mathcal{P_0} and \mathcal{W_1} is the event that the adversary \mathcal{A} outputs \mathcal{1} when given as input \mathcal{s \in S} drawn from distribution \mathcal{P_1}.
Bias
For an intuitive understanding of bias please refer here and here.
Bias is defined as the measure of the absolute difference between probabilities of an event occurring in a given distribution and the same event occurring in a uniform distribution.
Suppose the probability that the adversary wins is \mathcal{\frac{1}{2} + \epsilon^\prime}. Then the probability that it loses is \mathcal{1 - (\frac{1}{2} + \epsilon^\prime) = \frac{1}{2} - \epsilon^\prime}.
\begin{equation*}
\begin{split}
\textit{Distinguishing Advantage, } \epsilon & = \big|\text{Advantage of adversary with respect to challenger}\big| \\
& = \big|P(\text{Adversary wins}) - P(\text{Adversary loses})\big| \\
& = \Bigg|\bigg(\mathcal{\frac{1}{2} + \epsilon^\prime}\bigg) - \bigg(\mathcal{\frac{1}{2} - \epsilon^\prime}\bigg) \Bigg| \\
& = 2 \times \epsilon^\prime \\
& = 2 \times \textit{Bias}
\end{split}
\end{equation*} Hence,
\textit{Bias} = \frac{1}{2} \times \textit{Distinguishing Advantage}Definition of Distinguishing Advantage
We will define distinguishing advantage of \mathcal{D}, as follows:
A distinguisher is a function \mathcal{D : S \rightarrow \{0, 1\}} where \mathcal{S} is a countable set of real numbers. If \mathcal{P_0 \text{ and } P_1} are probability distributions on \mathcal{S}, the advantage of \mathcal{D} in distinguishing between \mathcal{P_0 \text{ and } P_1} is called distinguishing advantage of \mathcal{D}. It is denoted by \text{Adv}_D(\mathcal{P_0, P_1}) and is defined as,
\text{Adv}_D(\mathcal{P_0, P_1}) = \big|P[\mathcal{D(P_0) = 1}] - P[\mathcal{D(P_1) = 1}]\big|.The distinguishing advantage of \mathcal{D} is also denoted by \mathcal{\epsilon}.
The \mathcal{L_1} distance between the probability distributions \mathcal{p_{D(P_0)} \text{ and } p_{D(P_1)}} is given by,
\begin{equation*}
\begin{split}
\mathcal{\big\|p_{D(P_0)} - p_{D(P_1)}\big\|}_1 & = \mathcal{ \sum_{x \,\in\, \{0, 1\}} \big|p_{D(P_0)}(x) - p_{D(P_1)} (x)\big|} \\
& = \mathcal{2 \times \big|P[\mathcal{D(P_0) = 1}] - P[\mathcal{D(P_1) = 1}]\big|} \\
& = 2 \times \text{Adv}_D(\mathcal{P_0, P_1}) \\
\end{split}
\end{equation*} Since,
\mathcal{\big\|p_{D(P_0)} - p_{D(P_1)}\big\|}_{TV} = \mathcal{\frac{1}{2} \big\|p_{D(P_0)} - p_{D(P_1)}\big\|}_1Therefore,
\mathcal{\big\|p_{D(P_0)} - p_{D(P_1)}\big\|}_{TV} = \mathcal{\big|P[\mathcal{D(P_0) = 1}] - P[\mathcal{D(P_1) = 1}]\big|}=\text{Adv}_D(\mathcal{P_0, P_1})i.e., distinguishing advantage of \mathcal{D} equals the total variation distance between the distributions \mathcal{p_{D(P_0)} \text{ and } p_{D(P_1)}}.
\mathcal{\big\|p_{D(P_0)} - p_{D(P_1)}\big\|}_{TV} is the total variation distance between distributions \mathcal{p_{D(P_0)} \text{ and } p_{D(P_1)}} and also the distinguishing distance between distributions \mathcal{P_0 \text{ and } P_1} with respect to the distinguisher \mathcal{D}.
Definition of Distinguishing Distance
We define the distinguishing distance as follows:
A distinguisher is a function \mathcal{D : S \rightarrow \{0, 1\}} where \mathcal{S} is a countable set of real numbers. If \mathcal{P_0 \text{ and } P_1} are probability distributions on \mathcal{S}, the distinguishing distance between \mathcal{P_0 \text{ and } P_1} is denoted by \mathcal{\big\|P_0 - P_1\big\|}_D and is defined as,
\mathcal{\big\|P_0 - P_1\big\|}_D = \mathcal{\big|P[\mathcal{D(P_0) = 1}] - P[\mathcal{D(P_1) = 1}]\big|}Also,
\begin{equation*}
\begin{split}
\text{Adv}_{D}(\mathcal{P_0, P_1}) & = \mathcal{\big\|p_{D(P_0)} - p_{D(P_1)}\big\|}_{TV} \\
&= \mathcal{\big|P[\mathcal{D(P_0) = 1}] - P[\mathcal{D(P_1) = 1}]\big|}\\
& = \mathcal{\big\|P_0 - P_1\big\|}_D \\
& = 2 \times \textit{Bias}
\end{split}
\end{equation*}The above equation implies that the distinguishing advantage of \mathcal{D} in distinguishing between two distributions \mathcal{P_0 \text{ and } P_1} is equal to the distinguishing distance between the distributions \mathcal{P_0 \text{ and } P_1} which is also equal to the total variation distance between the distributions \mathcal{p_{D(P_0)} \text{ and } p_{D(P_1)}}.
For any distinguisher \mathcal{D},
\mathcal{\big\|P_0 - P_1\big\|}_D \leq \mathcal{\big\|P_0 - P_1\big\|}_{TV}.\mathcal{\big\|P_0 - P_1\big\|}_D = \mathcal{\big\|P_0 - P_1\big\|}_{TV} if an adversary using a distinguisher \mathcal{D} to distinguish between two distributions has unbounded resources (computing power and time).
Since \text{Adv}_{D}(\mathcal{P_0, P_1}) = \mathcal{\big\|P_0 - P_1\big\|}_D, \text{Adv}_{D}(\mathcal{P_0, P_1}) \leq \mathcal{\big\|P_0 - P_1\big\|}_{TV}.
Four Equivalent Definitions of Total Variation Distance Between Two Distributions
If \mathcal{P_0 \text{ and } P_1} are two probability distributions on a countable set of real numbers \mathcal{S}, then the total variation distance between them is defined in four equivalent ways as follows:
- \mathcal{\big\|P_0 - P_1\big\|}_{TV} = \underset{\mathcal{B} \,\subset\, \mathcal{S}}{\text{max}} \mathcal{\big|P_0(B) - P_1(B) \big|},
where the maximum is taken over all the subsets \mathcal{B \text{ of } S}.
We have already proved that both the sets \mathcal{A = \{ s \in S : P_0(s) \geq P_1(s)\} \text{ and } A^c = \{ s \in S : P_1(s) > P_0(s)\}} maximize \mathcal{\big|P_0(B) - P_1(B) \big|}. - \mathcal{\big\|P_0 - P_1\big\|}_{TV} = \frac{1}{2} \mathcal{\big\|P_0 - P_1\big\|}_1 = \frac{1}{2}\underset{\mathcal{s \in S}}{\sum} \mathcal{\big|P_0(s) - P_1(s) \big|}.
- \mathcal{\big\|P_0 - P_1\big\|}_{TV} = \underset{\mathcal{D : S \rightarrow \{0, 1\}}}{\text{max}} \mathcal{\big|P[\mathcal{D(P_0) = 1}] - P[\mathcal{D(P_1) = 1}]\big|},
where \mathcal{D(\cdot)} is a distinguisher function that distinguishes between \mathcal{P_0 \text{ and } P_1}. \mathcal{D}(P_0) means \mathcal{D} takes as input \mathcal{s \in S}, where \mathcal{s} is drawn from the distribution \mathcal{P_0} and outputs either 0 or 1. Similarly for \mathcal{D}(P_1). - \mathcal{\big\|P_0 - P_1\big\|}_{TV} = \underset{\mathcal{A : S \rightarrow \{0, 1\}}}{\text{max}} \mathcal{\big|P[\mathcal{W_0}] - P[\mathcal{W_1}]\big|},
where \mathcal{W_0} is the event that the adversary \mathcal{A} outputs \mathcal{1} when given as input \mathcal{s \in S} drawn from \mathcal{P_0} and \mathcal{W_1} is the event that the adversary \mathcal{A} outputs \mathcal{1} when given as input \mathcal{s \in S} drawn from \mathcal{P_1}.
Total Variation Distance Between Two Random Variables
The total variation distance between two random variables is the total variation distance between their corresponding distributions.
Four Equivalent Definitions of Total Variation Distance Between Two Random Variables
If X \text{ and } Y are two random variables taking values from a countable set of real numbers \mathcal{R}, then the total variation distance between them is defined in four equivalent ways as follows:
- \big\|X - Y\big\|_{TV} = \underset{\mathcal{R'} \,\subset\, \mathcal{R}}{\text{max}} \big|P(X \in \mathcal{R'}) - P(Y \in \mathcal{R'}) \big|.
- \big\|X - Y\big\|_{TV} = \frac{1}{2} \big\|X - Y\big\|_1 = \frac{1}{2}\underset{\mathcal{r \in R}}{\sum} \big|P(X = r) - P(Y = r) \big|.
- \big\|X - Y\big\|_{TV} = \underset{\mathcal{D : R \rightarrow \{0, 1\}}}{\text{max}} \big|P[\mathcal{D}(X) = 1] - P[\mathcal{D}(Y) = 1]\big|,
where \mathcal{D(\cdot)} is a distinguisher function that distinguishes between the probability distributions of X \text{ and } Y. \mathcal{D}(X) means \mathcal{D} takes as input \mathcal{r \in R}, where \mathcal{r} is drawn from the distribution of X and outputs either 0 or 1. Similarly for \mathcal{D}(Y). - \big\|X - Y\big\|_{TV} = \underset{\mathcal{A : R \rightarrow \{0, 1\}}}{\text{max}} \mathcal{\big|P[\mathcal{W_0}] - P[\mathcal{W_1}]\big|},
where \mathcal{W_0} is the event that the adversary \mathcal{A} outputs \mathcal{1} when given as input \mathcal{r \in R} drawn from the distribution of X and \mathcal{W_1} is the event that the adversary \mathcal{A} outputs \mathcal{1} when given as input \mathcal{r \in R} drawn from the distribution of Y.
Total Variation Distance between functions of two random variables
If \mathcal{S \text{ and } T} are countable sets of real numbers and X \text{ and } Y are random variables with support \mathcal{S}, then for any function, \mathcal{f : S \rightarrow T} ,\big\|f(X) - f(Y)\big\|_{TV} \leq \big\|X - Y\big\|_{TV}.
Through a simple game played between an adversary and challenger, we will reinforce our understanding of all the concepts enumerated above. This understanding will form the basis for doing security proofs in cryptography i.e., for mathematically reasoning about the security of cryptographic systems.