Modular Inequality

Question

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?

Answer 1

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