# T1: Two Important Distances

## Two Distances

There are two very important distances, i.e., total variation distance and Hellinger distance. Let \(P=\{p_i\}_{i\in[n]}\), \(Q=\{q_i\}_{i\in[n]}\) be two probability distributions supported on \([n]\). A natural way is to use the \(L_1\) norm to represent the distance between the probability vectors \(P\) and \(Q\).

We use \(\textcolor{blue}{\Delta_{TV}(P, Q) = \frac{1}{2} \| P - Q\| _1= \frac{1}{2} \sum_{i\in[n]} \lvert p_i - q_i \rvert}\) to denote the total variation distance.

Notice that \(\sqrt{P}=(\sqrt{p_1},\sqrt{p_2},\ldots,\sqrt{p_n})\) is a unit vector according to \(\ell_2\) norm, we define Hellliger distance as follows.

\[\textcolor{blue}{h(P,Q) = \frac{1}{\sqrt{2}}\|\sqrt{P}-\sqrt{Q}\|_2}\]By the above definitions, they use norms, so they are metric, which means that they satisfy the triangle inequality.

It is useful to know the following equality.

\(\textcolor{black}{ h(P,Q) = \frac{1}{\sqrt{2}} \|\sqrt{P} - \sqrt{Q} \|_2 = \sqrt{\frac{1}{2} \sum_x (\sqrt{p_x}-\sqrt{q}_x)^2}}\) \(\textcolor{blue}{=1 -\sum_x \sqrt{p_x q_x} \ (1)}\)

## Cut-and-Paste

Recall that in the fooling set, we know if the input \((x,y)\) and \((x', y')\) have the same transcript in a deterministic communication protocol, then \((x',y)\) and \((x,y')\) must have the same transcript. When applying this into Hellinger distance, we have the following lemma.

\(\textbf{Lemma 1}\). Let \(\mathcal{\Pi}\) be a randomized priviate coins protocol and \(\Pi_{x,y}\) denote the transcript on input \(x,y\). Then, \(h^2(\Pi_{x,y}, \Pi_{x',y'}) = h^2(\Pi_{x',y}, \Pi_{x,y'}).\)

\(\textbf{Proof}\). The idea is simple. Using inequality (1), we only need to show that for any transcript \(\mathcal{T}\), we have

\[\mathbb{P}[\Pi(x,y)=\mathcal{T}]\mathbb{P}[\Pi(x',y')=\mathcal{T}] = \mathbb{P}[\Pi(x',y)=\mathcal{T}]\mathbb{P}[\Pi(x,y')=\mathcal{T}] \ (2)\]We use the property of a rectangle. We use \(\mathcal{T}\) to denote a transcript of a protocol \(\Pi\) and let \(\textup{Rect}_{\mathcal{T}} = S_{\mathcal{T}}\times T_{\mathcal{T}}\) . Let \(R_A, R_B\) denote the private coins for Alice and Bob. Then,

\(\mathbb{P}_{R_A,R_B}[\Pi(x,y,R_A,R_B)=\mathcal{T}] \\= \mathbb{P}_{R_A,R_B}[((x,R_A),(y,R_B)) \in \textup{Rect}_{\mathcal{T}} ]\\=\mathbb{P}_{R_A,R_B}[(x,R_A) \in S_{\mathcal{T}},(y,R_B)\in T_{\mathcal{T}} ] \\=\mathbb{P}_{R_A}[(x,R_A) \in S_{\mathcal{T}}] \cdot \mathbb{P}_{R_B}[(y,R_B) \in S_{\mathcal{T}}]\).

The last line is because they are private coins. Thus, we can prove (2).