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{equation} \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} \end{equation}
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.
