Stochastic dominance between (products of) binomials Suppose $p \leq q \leq 1/2$, and $n,m\geq 1$ two integers. Let $X\sim \mathrm{Bin}(n,p)$, $Y\sim \mathrm{Bin}(m,p)$ and $X'\sim \mathrm{Bin}(n,q)$, $Y'\sim \mathrm{Bin}(m,q)$ be independent.

Is it true that
$$
\forall t\in \mathbb{R}, \Pr[ XY + (n-X)(m-Y) > t] \geq \Pr[ X'Y' + (n-X')(m-Y') > t]
$$ ?

Note/Update: I think the $>t$ above should both be $\geq t$, for the usual definition of stochastic dominance (shouldn't make a difference...)
Put differently:

Does the r.v. $Z = XY + (n-X)(m-Y)$ stochastically dominate the r.v. $Z'=X'Y' + (n-X')(m-Y')$?

It seems so to me, as $X,Y$ are "less balanced" than their counterparts $X',Y'$, but I am not sure how to formally show it.$^{(\dagger)}$ I tried to come up with a coupling of $Z,Z'$ such that $Z\geq Z'$ w.p. one, but failed. More generally, I don't know of any  way to show stochastic dominance, besides (1) coming up with a coupling, or (2) finding or comparing the CDFs explicitly.
${(\dagger)}$ Based on some experimental plots, this looks like it does hold (e.g., see below).

 A: I am searching counter examples in exact arithmetic using Julia's rational numbers:
using Distributions

xpdf(d::Binomial,k) = binomial(d.n, k)*d.p^k*(1 - d.p)^(d.n - k)

f(x,y) = x*y + (1-x)*(1-y)
   
while true

    p = big(rand(1:250)//rand(500:1000))
    q = big(rand(1:250)//rand(500:1000))
    p, q = minmax(p, q) # p <= q <= 0.5 

    m, n = rand(2:10), rand(2:10)
    r =  big(rand(1:250)//rand(500:1000))
    a = sum((f(i//m, j//n)>r)*xpdf(Binomial(m, p), i)*xpdf(Binomial(n, p), j) for i in 0:m, j in 0:n)
    b = sum((f(i//m, j//n)>r)*xpdf(Binomial(m, q), i)*xpdf(Binomial(n, q), j) for i in 0:m, j in 0:n)
    if a < b 
        @show n, m, r, p, q
    end
end

Output:
(n, m, r, p, q) = (2, 8, 4//99, 242//999, 181//709)
(n, m, r, p, q) = (9, 3, 9//239, 242//859, 124//401)
(n, m, r, p, q) = (2, 9, 2//801, 88//945, 249//562)
(n, m, r, p, q) = (2, 9, 13//102, 95//481, 241//725)
(n, m, r, p, q) = (10, 3, 9//229, 201//970, 191//505)
(n, m, r, p, q) = (7, 2, 113//442, 29//91, 225//538)
(n, m, r, p, q) = (10, 2, 51//826, 137//891, 106//549)
(n, m, r, p, q) = (2, 10, 7//191, 153//859, 60//169)
...

A: The conjecture is false, as shown by mschauer. (At least if we allow $m\neq n$; the case $m=n$ is still unclear to me.) Below is the simplest counterexample I could find in hindsight.

Following mschauer's answer, here is the smallest counterexample I could find: $n=1,m=4$.
For $n=1$, we have
$$
\Pr[Z=0] = p(1-p)^m + p^m(1-p)
$$
and, for $m\geq 4$, this is not a monotone function of $p$ on $[0,1/2]$. So the stochastic dominance, which would require $\Pr_p[Z\geq t]$ to be a non-increasing function of $p$ for every fixed $t$, cannot hold.

In particular, one can explicitly compute the cdf as a function of p. I am plotting it below to show that the CDFs are not monotone as a function of $p$ (this should be a discrete plot, piecewise linear; I am joining the points only for visualization's sake, to show that the relative order between the CDFs changes between 0 and 1).

