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).

| cite | improve this answer | |
  • $\begingroup$ 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. $\endgroup$ – Jeff Dec 1 '17 at 8:14
  • $\begingroup$ 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. $\endgroup$ – Iosif Pinelis Dec 1 '17 at 18:37

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.