# Linking error probability based on total variation

Consider probability measure $\mu_{XY}$ defined on $\mathbb{R}^d \times \{1,2,3\}$, and sub-probability measures $\mu_1$, $\mu_2$, and $\mu_3$ as $\mu_1(A):=P(X\in A, Y=0)$ and $\mu_2(A):=P(X\in A, Y=2)$ and $\mu_3(A):=P(X\in A, Y=3)$ for Borel sets $A$, so that $\mu:=\mu_1+\mu_2+\mu_3$ is the probability distribution of $X$. Let \begin{equation*} p:=P(Y\ne f(X)). \end{equation*} where $$f(x):= \left\{\begin{matrix} 1 & \mbox{if}~~ \rho_1(x) > \rho_2(x), \rho_3(x) \\ 2 & \mbox{if}~~ \rho_2(x) \ge \rho_1(x), \rho_2(x) > \rho_3(x) \\ 3 & \mbox{if}~~ \rho_3(x) \ge \rho_1(x), \rho_2(x) \:, \end{matrix}\right.$$ for all $x\in \mathbb{R}^d$ and for each $i=1,2,3$ the function $\rho_i$ is the density of $\mu_i$ with respect to the measure $\mu$. Can we write $p$ as a function of $\delta(\mu_1, \mu_2)$, $\delta(\mu_1, \mu_3)$, and $\delta(\mu_2, \mu_3)$, where $\delta(.,.)$ is the total variation?

For the case of having only two sub-probability measures, Proposition 4.2 of Levin'08 implies that $2p = 1- \delta(\mu_1, \mu_2)$.

The answer is no. E.g., let $(A_1,A_2,A_3)$ be any Borel partition of $\mathbb{R}^d$ such that $A_j\ne\emptyset$ for each $j$. Let $\nu$ be any measure on $\mathbb{R}^d$ such that $\nu(A_j)=1$ for each $j$. For each $i$ and $j$ in $\{1,2,3\}$, let the density of the measure $\mu_i(\cdot)=P(X\in \cdot,Y=i)$ with respect to $\nu$ equal the constant $\mu_{i,j}$ on the set $A_j$, where the $3\times3$ matrix $(\mu_{i,j})$ is
$$\frac1{10}\,\begin{bmatrix} 2 & 1 & 0 \\ 1 & 2 & 1 \\ 0 & 1 & 2 \\ \end{bmatrix}.$$ Then ($\mu_1+\mu_2+\mu_3$ is indeed a probability measure,) $\delta(\mu_1, \mu_2)=\frac1{10}(|2-1|+|1-2|+|0-1|)=\frac3{10}=\delta(\mu_2, \mu_3)$, $\delta(\mu_1, \mu_3)=\frac25$, $f(x)=j$ if $x\in A_j$ (the comparisons between the densities $\rho_i$ do not depend on the measure with respect to which the densities are taken -- as long as such densities exist), and $p=\frac25$ (in this case, the sum of the off-diagonal entries of the matrix).

Replacing here the previous matrix by $$\frac1{60}\,\begin{bmatrix} 21 & 7 & 0 \\ 9 & 13 & 0 \\ 0 & 7 & 3 \\ \end{bmatrix},$$ we get the same values of $\delta(\mu_1, \mu_2)$, $\delta(\mu_2, \mu_3)$, and $\delta(\mu_1, \mu_3)$, but $p=\frac{23}{60}\ne\frac25$.

So, $p$ is not a function of $\delta(\mu_1, \mu_2)$, $\delta(\mu_2, \mu_3)$, and $\delta(\mu_1, \mu_3)$.

Added: However, one always has the following lower bound on the misclassification probability $p$ in terms of the total variation norms $\delta(\mu_i,\mu_j)=\|\mu_i-\mu_j\|$: \begin{equation*} p\ge\frac12-\frac1{2(k-1)}\,\sum_{1\le i<j\le k}\|\mu_i-\mu_j\|. \tag{1} \end{equation*} Here we consider the more general setting, where $k\in\{2,3,\dots\}$, $Y$ takes values in the set $[k]:=\{1,\dots,k\}$, $f(x)=i$ if $x\in\bigcap_{j\in J_i}A_{ij}$, $J_i:=[k]\setminus\{i\}$, \begin{equation*} A_{ij}:=\begin{cases} \{x\colon\rho_i(x)>\rho_j(x)\}&\text{ if }i<j,\\ \{x\colon\rho_i(x)\ge\rho_j(x)\}&\text{ if }i>j, \end{cases} \end{equation*} so that $\bigcup_{i\in[k]}\bigcap_{j\in J_i}A_{ij}=\mathbb R^d$. Here everywhere $i$ and $j$ are in $[k]$.

Thus, \begin{multline*} 1-p=P(f(X)=Y)=\sum_{i\in[k]}P\Big(Y=i,X\in\bigcap_{j\in J_i}A_{ij}\Big) =\sum_{i\in[k]}\mu_i\Big(\bigcap_{j\in J_i}A_{ij}\Big) \\ \le\sum_{i\in[k]}\min_{j\in J_i}\mu_i(A_{ij}) \le\sum_{i\in[k]}\frac1{k-1}\sum_{j\in J_i}\mu_i(A_{ij}) =\frac1{k-1}\sum_{1\le i<j\le k}[\mu_i(A_{ij})+\mu_j(A_{ji})] \\ =\frac1{k-1}\sum_{1\le i<j\le k}\int(\rho_i\vee\rho_j)\,d\mu =\frac1{k-1}\sum_{1\le i<j\le k}\int\frac{\rho_i+\rho_j+|\rho_i-\rho_j|}{2}\,d\mu \\ =\frac1{k-1}\sum_{1\le i<j\le k}\frac{\|\mu_i\|+\|\mu_j\|+\|\mu_i-\mu_j\|}{2} =\frac12\,+\frac1{2(k-1)}\sum_{1\le i<j\le k}\|\mu_i-\mu_j\|; \end{multline*} here we used the fact that $\sum_i\mu_i=\mu$, a probability measure, so that $\sum_i\|\mu_i\|=1$. Thus, we have (1).

• But we can say $\Delta = \delta(\mu_1,\mu_2)+\delta(\mu_2,\mu_3)+\delta(\mu_1,\mu_3) \geq 1-2p$, right? To see that, let $a_{ij}$ be entry $(i,j)$ of your matrix, then $\Delta = 1-2p + \left(a_{11}+a_{22}+a_{33}+|a_{23}-a_{13}|+|a_{32}-a_{12}|+|a_{31}-a_{21}| \right)$, where the term inside $()$ is non-negative.
– Jeff
Dec 1, 2017 at 8:14
• Your bound on $p$ seems correct, even with $\Delta$ replaced by $\Delta/2$, and a more general result holds when $Y$ takes $k$ values, for any $k\ge2$. See the added material. Dec 1, 2017 at 18:37