1
$\begingroup$

Let $A = \{1, 2,\dots, n\}$, and let $X$ and $Y$ be two random variables on the same space, taking values in $A$, and distributions given by: $P(X = i) = p_i$, and $P(Y = i) = q_i$, for any $i\in\{1,2,\dots,n\}$.

What is the maximum possible value of $P(X = Y)$?

Basically, we have to choose a good joint distribution of $X$ and $Y$, such that the sum of diagonal entries in the joint distribution table/matrix is maximized. For $n = 2$, this is easy to do, and I get the answer $(1 - |p_1 - q_1|)$. But even for $n = 3$, I am not able to do much. A solution/strategy for general n would be appreciated.

Improve this question
$\endgroup$
3
  • 4
    $\begingroup$ Let the probability $X=Y=i$ be $\min(p_i,q_i)$. $\endgroup$
    – Douglas Zare
    Commented Jun 13, 2013 at 5:53
  • $\begingroup$ Douglas' nice solution is incomplete as you need to show there is a way to fill in the rest of the table with non-negative entries. Let $\tau$ be the sum of $\max(p_i,q_i)-\min(p_i,q_i)$. For $(i,j)$ such that $p_i\gt q_i$ and $q_j\gt q_i$, set the $(i,j)$ entry to $(p_i-q_i)(q_j-q_i)/\tau$. (If that doesn't work, I've misstated it. Something like that definitely works.) $\endgroup$
    – Brendan McKay
    Commented Jun 13, 2013 at 6:42
  • 3
    $\begingroup$ This is called the total variation distance. $\endgroup$
    – Ori Gurel-Gurevich
    Commented Jun 13, 2013 at 6:54

2 Answers 2

Reset to default
2
$\begingroup$

A slightly complicated, but sometimes illuminating way to see this and fill details from Douglas Zare comment is to look at the prescribed laws for $X$ and $Y$ as sand piles. A joint law of a couple $(X,Y)$ can be seen as a "transport plan" : each probability of an elementary event $(X=i, Y=j)$ is interpreted as the amount of mass the plan says you move from $i$ to $j$.

Now, maximizing the probability of the event $X=Y$ is equivalent to transporting the mass from the distribution given by $(p_i)$ to the one given by $(q_i)$ in a way that maximizes the amount of mass that does not move in the process.

The solution is then obvious: let as much as you can in its initial position (this is $\min(p_i,q_i)$ for each $i$), take out everything that is in excess from the first distribution, and distribute it in any way where you need it so as to realize the distribution $(q_i)$ at the end.

Improve this answer
$\endgroup$
1
$\begingroup$

Let $C = \Pr(X=Y)$. Then $$\Pr(C)=\sum_i \Pr(X=i \cap Y=i) \leq \sum_i \min(p_i,q_i).$$ Now let's construct a joining of $X$ and $Y$ for which $\Pr(C)= \sum_i \min(p_i,q_i)$.

Put $c= \sum_i \min(p_i,q_i)$. Assume $c \in ]0,1[$ and consider four independent random variables $\epsilon$, $V$, $X'$ and $Y'$ whose laws are given by:

  • $\Pr(\epsilon=1)=1-\Pr(\epsilon=0)=c$

  • $\Pr(V=i) = \dfrac{\min(p_i,q_i)}{c}$

  • $\Pr(X'=i)= \dfrac{p_i - c \Pr(V=i)}{1-c}$

  • $\Pr(Y'=i)= \dfrac{q_i - c \Pr(V=i)}{1-c}$

Set $$X=\begin{cases} V & \text{if }\epsilon=1 \\\ X' & \text{if } \epsilon=0 \end{cases}$$ and $$Y=\begin{cases} V & \text{if }\epsilon=1 \\\ Y' & \text{if } \epsilon=0 \end{cases}.$$

Then check.

Improve this answer
$\endgroup$

You must log in to answer this question.

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