4
$\begingroup$

Can anyone explain why the $l_1$ distance has the property that probability distributions $P,Q$ with orthogonal support (meaning that the product $p_iq_i$ vanishes for each value of $i$) are at a maximal distance from each other? Consider $$ \|P-Q\|_1=\frac{1}{2}\sum_{i=1}^{N}|p_i-q_i|$$

$\endgroup$
3
$\begingroup$

Note that if $p_{i}q_{i} = 0\,\,\forall i$, then for all $i$ either $p_{i} = 0$, $q_{i} = 0$, or both are $0$.

Divide $\{i\} = \{1,\ldots,N\}$ into those $i$ for which these three different things happen: $\{N_{p_{i}}\} = \{i|p_{i} = 0\}$, $\{N_{q_{i}}\} = \{i|q_{i} = 0\}$, $\{N_{pq_{i}}\} = \{i|p_{i} = q_{i} = 0\}$.

Then \begin{equation} \begin{split} \|P-Q\|_{1} =& \frac{1}{2}\sum_{i=1}^{N}|p_{i}-q_{i}| \\ =& \frac{1}{2}\sum_{i\in N_{p_{i}}}|p_{i}-q_{i}| + \frac{1}{2}\sum_{i\in N_{q_{i}}}|p_{i}-q_{i}| + \frac{1}{2}\sum_{i\in N_{pq_{i}}}|p_{i}-q_{i}| \\ =& \frac{1}{2}\sum_{i\in N_{p_{i}}}|q_{i}| + \frac{1}{2}\sum_{i\in N_{q_{i}}}|p_{i}| + \frac{1}{2}\sum_{i\in N_{pq_{i}}}|0| \\ =& \frac{1}{2}\Big(\sum_{i \in \{N\}}q_{i} + \sum_{i \in \{N\}} p_{i}\Big) = 1, \end{split} \end{equation}

where the last line follows from the fact that $$ 1 = \sum_{i\in \{N\}}|q_{i}| = \sum_{i\in N_{p_{i}}}|q_{i}| + \sum_{i\in N_{q_{i}}}|q_{i}| + \sum_{i\in N_{pq_{i}}}|q_{i}| = \sum_{i\in N_{p_{i}}}|q_{i}| + 0 + 0 = \sum_{i\in N_{p_{i}}}|q_{i}|, $$ and likewise for $\sum_{i}p_{i}$. That is, we can add these other terms of $q_{i}$ ($p_{i}$) because they are $0$ by construction anyway.

This is the maximum value that $\|P-Q\|_{1}$ can take for any $P$ and $Q$, because $|p_{i} - q_{i}| \leq |p_{i}| + |-q_{i}| = p_{i} + q_{i}$ for any $p_{i},q_{i}$ imaginable, and as such:

$$ \|P-Q\|_{1} = \frac{1}{2}\sum_{i=1}^{N}|p_{i}-q_{i}| \leq \frac{1}{2}\big(\sum_{i=1}^{N}p_{i}+q_{i}\big) = \frac{1}{2}\sum_{i=1}^{N}p_{i} + \frac{1}{2}\sum_{i=1}^{N}q_{i} = \frac{1}{2}+\frac{1}{2} = 1 $$

$\endgroup$
5
  • $\begingroup$ can you please explain why the maximum value of $\|P-Q\|_1$ is 1? $\endgroup$
    – Sakh10
    Jan 28 at 10:56
  • 1
    $\begingroup$ Can I use minkowski inequality to show the maximum value equals to 1? $\endgroup$
    – Sakh10
    Jan 28 at 12:19
  • 2
    $\begingroup$ You can use the triangle inequality on each of the terms in the sum to show that it is bounded above by $1$. $\endgroup$
    – Rammus
    Jan 28 at 12:42
  • 1
    $\begingroup$ @Rammus thanks! I was just adding it to my answer too:) $\endgroup$
    – JSdJ
    Jan 28 at 12:43
  • 1
    $\begingroup$ @Sakh10 Please see the added text $\endgroup$
    – JSdJ
    Jan 28 at 12:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.