Given two discrete random variables $X$ and $Y$. Compute $Pr(X-Y<=0)$. Given two independent discrete random variables $X$ and $Y$ that follow the same distribution: Each can take $n^2$ different positive values each with probability $\frac{1}{n^2}$.
I am interested in the probability that $X-Y\leq 0$: $Pr(X-Y\leq 0)$. I know that one can do this by defining $Z:=X-Y$ and computing the distribution of $Z$: $Pr(Z=z)$.
But in this case I will have to go over all possible $z$ and find out how many ways there are to construct $z$, e.g. if $z=5$ and $X$ and $Y$ can take values from ${\lbrace1, ..., 10\rbrace}$ than I have to go over all possible combination on how to construct $5$, so $10-5, 9-4, 8-3, 7-2, 6-1$, since I do not know the exact values $X$ and $Y$ can take (only that there are $n^2$ many) this seems rather unpractical.
Is there a smart way how to do this? Since $X$ and $Y$ have the same distribution maybe something like $Pr(Z=z)=$(number of ways to construct $z$)$(\frac{1}{n^2})^2$. But how do I get the number of ways how to construct $z$?
 A: If the variables aren't independent, there isn't a fixed answer -- it depends on how $X$ and $Y$ are related. Some examples: You could have $X$ and $Y$ linked so that $X=Y$ always; then the probability is $1$. If the distribution is each of $\{1,2,\dots,n^2\}$ with equal probability (for example), then you could have $X=n^2+1-Y$, where the probability is $1/2$.
However, if they're independent, there is a fixed answer. It's better not to think about it in terms of $Z=X-Y$ and instead to think in terms of $\operatorname{Pr}[X\leq Y]$ -- the latter quantity is not really dependent on the possible values of $X$ and $Y$, only their ordering, so you can let $X$ and $Y$ take each $a_i$ with $a_1<a_2<\cdots<a_{n^2}$ with probability $1/n^2$, and the question is just the probability that, if $X=a_i$ and $Y=a_j$, $i\leq j$. Can you calculate this directly?
A: Hint: fix $X=x$ (which happens with probability $P[X=x]$, then compute the probability that $Y\geq x$ given $X=x$. Using that, compute $P[X=x \wedge Y\geq x]$. If $X$ and $Y$ are uniform and independent, this should be a simple task. Then sum it over all choices of $X$.
