# Effect of partitioning the realizations of random variables on the total variation distance?

Let $X$ and $Y$ be two random variables with joint pmf $p(x,y)=p(x)\cdot p(y|x)$ and $X$ has uniform distribution. Also assume that the following relation is satisfied: \begin{align} \lVert p(y|x)-p(y)\rVert_1\leq a. \end{align} where $\lVert\cdot\rVert_1$ is the total variation distance. Now, suppose that we group uniformly and independently each two realizations of $X$. We define new random variable $X^\prime$ as $$X^\prime=x^\prime\leftrightarrow X=\{x_1\text{or}~x_2\}.$$ Thus, we have $$p(y|x^\prime)=\frac{1}{2}p(y|x_1)+\frac{1}{2}p(y|x_2).$$ It is clear that distribution of $p(y|x^\prime)$ is closer to $p(y)$. Indeed, triangle inequality shows the following: \begin{align} \lVert p(y|x^\prime)-p(y)\rVert_1&=\lVert \frac{1}{2}p(y|x_1)+\frac{1}{2}p(y|x_2)-p(y)\rVert_1\\ &\leq\frac{1}{2}\lVert p(y|x_1)-p(y)\rVert_1+\frac{1}{2}\lVert p(y|x_2)-p(y)\rVert_1\\ &\leq a \end{align} Now, the question is that how much the grouping could decrease the total variation amount? For example, we can show that grouping random variables results in total variation of $\frac{a}{2}$?

To clarify the question, consider the following joint pmf $p(x,y)$:

$$\begin{matrix} &y_1&y_2&y_3&y_4\\ x_1&.2&.3&.4&.1\\ x_2&.1&.6&.1&.2\\ x_3&.5&.05&.25&.2\\ x_4&.2&.05&.25&.5 \end{matrix}$$

For this pmf, we have: \begin{align} \lVert p(y,x)-p(y)p(x)\rVert_1=\sum_{x,y}\frac{1}{4}\lvert p(y|x)-p(y)\rvert=0.525. \end{align}

Now consider $x^\prime_1=\{x_1,x_2\}$ and $x^\prime_2=\{x_3,x_4\}$. Then, \begin{align} \lVert p(y,x^\prime)-p(y)p(x^\prime)\rVert_1=\sum_{x,y}\frac{1}{2}\lvert p(y|x^\prime)-p(y)\rvert=0.4. \end{align}

and considering $x^\prime_1=\{x_1,x_3\}$ and $x^\prime_2=\{x_2,x_4\}$, we have, \begin{align} \lVert p(y,x^\prime)-p(y)p(x^\prime)\rVert_1=\sum_{x,y}\frac{1}{2}\lvert p(y|x^\prime)-p(y)\rvert=0.35. \end{align}

So, the choice of group members affects the amount of total variation. Now the question is to analyze this effect.

• It depends on how you choose $x_1,x_2$, basically you are mixing two distributions, which does not necessarily lead to reduction of total variance. – Henry.L Apr 18 '17 at 10:46
• Yes. But there exists such a mixing. I want to know how much the total variation could decrease when we choose $x_1$ and $x_2$ in the best way. – Math_Y Apr 18 '17 at 11:13
• Can you complement your OP with an example where such a micing strictly reduce total variation and in what sense you mean "best"? – Henry.L Apr 18 '17 at 11:26