I would like to derive an upper bound on $\mathsf{Pr}\{(\frac{X}{n}-\frac{1}{2})^2 \leq (\frac{Y}{n}-\frac{1}{2})^2\}$ where $X,Y$ are independent and $X\sim$ Bin($n,p$) where $p\neq \frac{1}{2}$, and $Y\sim$ Bin($n,\frac{1}{2}$). Intuitively, when $n$ is large, the left hand side is non-negative and the right hand side nears zero, so the probability should be vanishing with $n$.
And here is my attempt:
For simplicity we denote $X'=(\frac{X}{n}-\frac{1}{2})^2,Y'=(\frac{Y}{n}-\frac{1}{2})^2$, using Chernoff Bound we have $\mathsf{Pr}\{X' \leq Y'\}\leq \inf_{t>0}\mathsf{E}[e^{t(Y'-\mathsf{E}[Y'])}]\mathsf{E}[e^{t(-X'+\mathsf{E}[X'])}]/e^{t\alpha}$ where $\alpha = \mathsf{E}[X']-\mathsf{E}[Y']$.
By some calculation we can conclude $\alpha = \frac{n-1}{n}(p^2+\frac{1}{4})$, and by Hoeffding's Lemma, since $X',Y'\in [0,\frac{1}{4}]$ we have $\mathsf{E}[e^{t(Y'-\mathsf{E}[Y'])}]\mathsf{E}[e^{t(-X'+\mathsf{E}[X'])}] \leq e^{\frac{t^2}{64}}$, so $\mathsf{Pr}\{X' \leq Y'\}\leq \inf_{t>0}\{e^{\frac{t^2}{64}-t(\frac{n-1}{n})(p^2+\frac{1}{4})}\}=\exp\{-16(\frac{n-1}{n})^2(p^2+\frac{1}{4})^2\}$ which is not vanishing with $n$. I guess the step using Hoeffding's Lemma makes the bound too loose, but I'm not sure how to improve it.
Since by the reverse triangle inequality $\left|x-\frac n2 \right|\geq n\left|p-\frac 12 \right| - \left| x-np\right|$, we have the inclusion of events $$\begin{align}\left(\left| X-\frac{n}2\right|\leq \left| Y-\frac{n}2\right| \right) &\subset \left(\left| X-np\right|+ \left| Y-\frac{n}2\right| \geq n\left|p-\frac 12 \right| \right)\\ &\subset \left(\left| X-np\right| \geq \frac n2\left|p-\frac 12 \right|\right) \cup \left(\left| Y-\frac{n}2\right|\geq \frac n2\left|p-\frac 12 \right| \right) \end{align}$$ Hence $$\begin{align}P\left(\left| X-\frac{n}2\right|\leq \left| Y-\frac{n}2\right| \right) &\leq P\left(\left| X-np\right| \geq \frac n2\left|p-\frac 12 \right|\right) + P\left(\left| Y-\frac{n}2\right|\geq \frac n2\left|p-\frac 12 \right| \right) \end{align}$$
Hoeffding's bound applied to each summand yields $$P\left(\left| X-\frac{n}2\right|\leq \left| Y-\frac{n}2\right| \right)\leq 4\exp\left(-\frac n2\left(p-\frac 12 \right)^2\right)$$
Note that independence of $X$ and $Y$ was not used.