0
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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}$$

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Clement C. Nov 5 '17 at 21:42
  • $\begingroup$ 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? $\endgroup$ – EvaD Nov 5 '17 at 21:51
  • $\begingroup$ By "common" I meant "common to $X$ and $Y$" (as in the usual English use of the word, not any mathematical one). @EvaD $\endgroup$ – Clement C. Nov 5 '17 at 21:55
  • $\begingroup$ 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 $\endgroup$ – Clement C. Nov 5 '17 at 21:59
  • $\begingroup$ @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}$. $\endgroup$ – Clement C. Nov 5 '17 at 22:03
0
$\begingroup$

(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$.

$\endgroup$

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.