0
$\begingroup$

I have two $n \times n$ matrices $P$ and $Q$. They are given as follows:

$$P = \begin{bmatrix}p_{11}&p_{12}&........&p_{1n}\\p_{21}&p_{22}&........&p_{2n}\\...&...&........&...\\...&...&........&...\\p_{n1}&p_{n2}&........&p_{nn}\end{bmatrix}$$

$$Q = \begin{bmatrix}q_{11}&q_{12}&........&q_{1n}\\q_{21}&q_{22}&........&q_{2n}\\...&...&........&...\\...&...&........&...\\q_{n1}&q_{n2}&........&q_{nn}\end{bmatrix}$$

Now, I know that the Total Variation Distance between $P$ and $Q$ is at most $\delta$, i.e., $d_{TV}(P,Q) \leq \delta$. Is there any way I can relate this $\delta$ to the difference between each entry, for example $(p_{11} - q_{11})$, or $(p_{12} - q_{12})$, and so on?

$\endgroup$
2
  • $\begingroup$ Can you define the total variation distance that you are using here? (The one I have in mind is $d_{\rm TV}(P, Q) = \frac{1}{2} \sum_{i,j} |P_{ij} - Q_{ij}|$, but perhaps yours is different.) $\endgroup$
    – Drew Brady
    Jul 7, 2020 at 4:10
  • $\begingroup$ $d_{TV}(P,Q) = \frac{1}{2}||P-Q||_1$. It's the same as your definition $\endgroup$
    – Bikas
    Jul 7, 2020 at 4:11

1 Answer 1

1
$\begingroup$

No. In general, the best you can say is that $|p_{ij} - q_{ij}| \leq 2\delta$ for all $i,j$. This is clearly tight: take $P = 2\delta e_i e_j^T$ and $Q = 0$.

(Note: this is a consequence of the general fact that a $\ell_1$ norm implies a very pessimistic bound on the $\ell_\infty$ norm.)

$\endgroup$
3
  • 1
    $\begingroup$ That's what I was thinking. Thank you! $\endgroup$
    – Bikas
    Jul 7, 2020 at 4:14
  • $\begingroup$ Can you give me any source for the claim that you made in the Note $\endgroup$
    – Bikas
    Jul 7, 2020 at 4:15
  • $\begingroup$ No real reference. You have for a general vector $x \in \mathbb{R}^n$: $\|x\|_\infty \leq \|x\|_1 \leq n \|x\|_\infty$, by definition. $\endgroup$
    – Drew Brady
    Jul 7, 2020 at 4:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .