I'm trying to find a closed form solution to the following probability given two random values $a$ and $b$:


$P(a \mod{p} < b \mod{p}~|~a \mod{q} > b \mod{q},~p \lt q)$


Ideas?



Modular Inequality
I think one can hack out an expression, although it's not particularly beautiful. 


I'm assuming that by "counting measure" you mean that a and b are independent and are, say, uniform in the set $\{0,1,2,...pq-1\}$ (one could replace $pq-1$ by $\text{lcm}(p,q)-1$ or whatever). 


Let $g=\text{gcd}(p,q)$. Suppose we are told $a \mod g$. Conditional on that value, there are then $p/g$ possibilities for $a \mod p$, and there are $q/g$ possibilities for $a \mod q$; the two are independent, and both are uniform on their possible values.


We have $P(a \mod g = b \mod g)=\frac1g$, and $P(a \mod g < b \mod g)=P(a \mod g > b \mod g)
= \frac{1}{2}(1-\frac1g)$.


Consider these three cases separately.


(1) Suppose $a\mod g=b\mod g$. Conditional on this:


$P(a\mod p = b\mod p)=\frac{g}{p}$


$P(a\mod p < b\mod p)=P(a\mod p> b\mod q)=\frac12(1-\frac{g}{p})$.


Similarly for the values mod $q$.


(2) Suppose $a\mod g < b\mod g$. One finds that the possible values for $a\mod p$ and
for $b\mod p$ interleave with one another, starting at the low end with a possible 
value for $a\mod p$ and ending at the top with a possible value for $b\mod p$.


For example, consider $p=18$ and $q=21$ so $g=3$. Suppose $a\mod 3 = 1$ and $b\mod 3=2$.
Then the possible values of $a\mod 18$ are $1,4,7,10,13,16$ and the possible values of $b\mod 18$ are $2,5,8,11,14,17$.


As a result, conditional on $ \{ a \mod g < b \mod g \} $ one obtains:


$P(a \mod p < b\mod p)=\frac12(1+\frac{g}{p})$


$P(a \mod p > b\mod p)=\frac12(1-\frac{g}{p})$


and similarly for the values $\mod q$.


(You can think of this as reproducing the result from (1) above, but replacing every "=" outcome by a "<" outcome.)


(3) The case $a\mod g > b\mod g$ is symmetric with case (2) above.




---


One can put all this together to get the full joint distribution for the ordering of 
$a$ and $b \mod p$ and $q$ (there are nine possibilities in total).


Among other things you would obtain 


$P(a \mod p < b \mod p,~~a \mod q > b \mod q)=$


$\frac1g\frac12(1-\frac{g}{p})\frac12(1-\frac{g}{q}) 
~+~ \frac12(1-\frac1g)\frac12(1-\frac{g}{p})\frac12(1+\frac{g}{q})
~+~ \frac12(1-\frac1g)\frac12(1+\frac{g}{p})\frac12(1-\frac{g}{q})$


which of course you can simplify a little. In particular cases, eg where $g=1$ or where $g=p$, the expression simplifies a lot, of course.


To get the conditional probability you originally asked for, divide through by
$P(a\mod q > b\mod q)$ which is $\frac12(1-\frac1q)$.


