計算元組上兩個分佈之間的統計距離
讓 $ X $ 表示一種分佈。讓 $ f,g, \text{ and } h $ 表示三個函式。如果我們有結果： $ g(X) $ 在可忽略不計的統計距離內 $ h(X) $ . 是否可以證明
$$ (f(X),g(X)) \text{ is within negligible statistical distance of } (f(X),h(X)) $$
我為這個問題苦苦掙扎了很長時間。歡迎任何提示。
不，您無法證明這一點，因為它通常不是正確的。考慮以下反例。
讓 $ X $ 是一個分佈 $ {0,1} $ 和$$ \Pr_{b\gets X}[b=0] = \Pr_{b\gets X}[b=1]=\frac{1}{2}. $$ 讓 $ f,g,h : {0,1} \to {0,1} $ 定義為$$ f : b \mapsto b,\quad g : b \mapsto b, \quad \text{and} \quad h : b \mapsto b\oplus 1. $$
分佈之間的統計距離 $ g(X) $ 和 $ h(X) $ 為零，因此可以忽略不計。
$$ \begin{align}&\frac{1}{2} \sum_{b\in {0,1}} \left|\Pr_{b’\gets X}[g(b’)=b] - \Pr_{b’\gets X}[h(b’)=b]\right|\ =&\frac{1}{2} \sum_{b\in {0,1}} \left|\Pr_{b’\gets X}[b’=b] - \Pr_{b’\gets X}[b’\oplus 1=b]\right|\ =&\frac{1}{2} \sum_{b\in {0,1}} \left|\frac{1}{2} - \frac{1}{2}\right| = 0 \end{align} $$
但是，兩個發行版的支持$$ (f(X),g(X)) \in {(0,0),(1,1)}\quad \text{and} \quad (f(X),h(X)) \in {(0,1),(1,0)} $$完全不相交，因此它們的統計距離為 $ 1 $ 這是不可忽略的。