Reminder: This post contains 2207 words
· 7 min read
· by Xianbin
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).