# Relationship between X and Y if both are uniformly distributed over the same range

For independent X and Y, each uniformly distributed on (1,2,...,n) how would I go about calculating $P(X=Y)$ and $P(X<Y)$? Do I draw an n by n matrix and visually analyze it?

The solution talks about using symmetry, but I am not sure how to approach this. What is the relationship between X and Y given they are distributed over the same range?

Since they are independent, you have, for every $1\leq i,j\leq n$, $$\Pr[ X=i, Y=j ] = \Pr[ X=i ]\Pr[ Y=j ] = \frac{1}{n}\cdot\frac{1}{n} = \frac{1}{n^2}\,,$$ where we used the fact that they are both uniformly distributed.

Now, by the law of total probability the probability that $X=Y$ is equal to: $$\Pr[ X = Y ] = \sum_{i=1}^n \Pr[ X = i, Y =i ] = n\cdot \frac{1}{n^2} = \boxed{\frac{1}{n}}\,.$$

Note that this generalizes to other distributions than uniform. If $X,Y$ are independent with common distribution $p$ over $\{1,\dots,n\}$, then the same argument gives $$\Pr[ X = Y ] = \sum_{i=1}^n \Pr[ X = i, Y =i ] = \sum_{i=1}^n p(i)^2 = \lVert p\rVert_2^2\,,$$ which is the squared $\ell_2$ norm of the probability distribution $p$ (minimized for the uniform distribution) and is commonly referred to as the collision probability.

For the probability that $X<Y$, you can use the same approach (law of total probability): \begin{align} \Pr[X<Y] &= \sum_{i=1}^{n} \Pr[X=i, Y>i] = \sum_{i=1}^{n} \Pr[X=i]\cdot\Pr[Y>i] = \sum_{i=1}^{n} \frac{1}{n}\cdot \frac{n-i}{n} \\&= \sum_{i=1}^{n} \frac{1}{n}\cdot \frac{n-i}{n} = 1- \frac{1}{n^2}\sum_{i=1}^{n}i = 1-\frac{n(n+1)}{2n^2} = \boxed{\frac{n-1}{2n}} \end{align}

• As a sanity check: when $n=1$, $\Pr[X<Y]=0$. When $n\to\infty$, $\Pr[X<Y]\to \frac{1}{2}$. And when $n=2$, you find $\Pr[X<Y]=\frac{1}{4}$ as expected (since the 4 events $(1,1),(2,2), (1,2)$, and $(2,1)$ are equiprobable, but $X<Y$ in only one of them). – Clement C. Nov 5 '17 at 21:42
• Did not study 'common distribution', so I do not really know the difference between uniform and common. Also we did not study the Law of total probability, so I am just trying to understand what P(X=Y) means in terms of X and Y? I think it is the sum of probabilities of all the pairs like (1,1), (2,2) etc. But how do I go from having n such pairs to the answer which is $1/n$ especially since I do not know what the probability of any such pair is? – EvaD Nov 5 '17 at 21:51
• By "common" I meant "common to $X$ and $Y$" (as in the usual English use of the word, not any mathematical one). @EvaD – Clement C. Nov 5 '17 at 21:55
• As for the second question: The event $\{X=Y\}$ corresponds to the disjoint union of the $n$ events $\{X=Y=i\}$, for $1\leq i\leq n$: $$\{X=Y\} = \bigcup_{i=1}^n \{X=Y=i\}$$ Since these events are disjoint, you have by the axioms of probability that $$\Pr[X=Y] = \Pr[\bigcup_{i=1}^n \{X=Y=i\}] = \sum_{i=1}^n \Pr[ \{X=Y=i\} ]$$ (which is basically the law of total probability: fancy name, but simple notion). Now, by independence $\Pr[ \{X=Y=i\} ] = \Pr[ \{X=i\} ]\Pr[ \{Y=i\} ]$ and since $X,Y$ are uniform you get $1/n^2$. So $\sum_{i=1}^n \frac{1}{n^2} = \frac{1}{n}$. @EvaD – Clement C. Nov 5 '17 at 21:59
• @EvaD So to answer you last point "especially since I do not know what the probability of any such pair is": well, you do. By independence of $X,Y$ and the fact that $X,Y$ are both uniformly distribution, each pair has probability $\frac{1}{n}\cdot \frac{1}{n} = \frac{1}{n^2}$. – Clement C. Nov 5 '17 at 22:03

(You asked how symmetry is used.)

Yes, consider the $n\times n$ table of $p_{x,y}=P(X=x,Y=y)=P(X=x)P(Y=y)= n^{-2}.$ This table has the same entry everywhere, so $P(X=Y)$ is just $n^{-2}$ times the number of elements $(n)$ on the diagonal where $x=y$, while $P(X<Y)$ is just $n^{-2}$ times the number of elements ($\frac{(n-1)n}{2}$) in the triangular off-diagonal part where $x<y$.