Probability edge in matching contain element from two disjoints subsets $\mathbb{P}(\exists \{i,j\} \in M, i \in S_1 \text{ and } j \in S_2) \geq 1/2$

Question

Let $n$ be an even perfect square. First generate a random sample $S$ without replacement choosing $2 \sqrt{n}$ numbers from $[n]$. $$S = \{s_1,...,s_{2\sqrt{n}}\}.$$ Then split $S$ in half. So we get two subsets: $$S_1 = \{s_1,...,s_{\sqrt{n}}\}, ~~S_2 = \{s_{1+\sqrt{n}},..., s_{2\sqrt{n}}\}.$$

Next, generate a perfect matching $M$ on $n$ (a partition into $n/2$ disjoints pairs) $$M = \{\{m_1,m_2\},...\{m_{n-1},m_{n}\}\}.$$

Everything follows a uniform distribution.

Prove that: \begin{align}\mathbb{P}(\exists \{i,j\} \in M, i \in S_1 \text{ and } j \in S_2) \geq 1/2.~~~~~~~~(1)\end{align}

What I have tried:

$$\mathbb{P}(m_1 \in S_1) = \mathbb{P}(m_1 = s_1) + \dotsm + \mathbb{P}(m_1 = s_{\sqrt{n}}) = \frac{1}{n} + \dotsm + \frac{1}{n} = \frac{\sqrt{n}}{n}.$$

The probability that $m_1 \in S_1$ and $m_2 \in S_2$ is given by the product of the probability of these two events. If we consider all the possible $n/2$ disjoint pairs of the perfect matching $M$ I get this expression

\begin{align*} ?(\exists \{i,j\} \in M, i \in S_1 \text{ and } j \in S_2) = \left(\frac{\sqrt{n}}{n}\right)^2 \frac{n}{2} = \frac{1}{2}, \end{align*}

that I think it is the Expectation $(? = \mathbb{E})$ of the event I'm looking for and not the Probability $(? = \mathbb{P})$. I'm also not sure about how to get $\geq 1/2$ as well.

Any help on how to prove $(1)$ would be much appreciated.

(Maybe I'm missing some combinatorial aspect of this problem?)

PS: If someone doesn't believe $(1)$ is true I can post a python code to simulate this experiment (At first I was not believing in $(1)$ so I convinced my self with a simulation :)

Answer 1

Here's how to make your attempted calculation precise. Once the perfect matching, $M$, has been chosen, define a sequence of indicator random variables $X_1,X_2,\dots,X_{n/2}$, where $X_i$ is equal to $1$ if the $i^\text{th}$ pair contains one element from $S_1$ and the other from $S_2$, for each $i\in \{1,\dots,n/2\}$. Otherwise, $X_i$ equals zero. Then $$ P(X_i=1)=\frac{\sqrt n\cdot \sqrt{n}}{n\cdot (n-1)/2}\ge \frac{n}{ n\cdot n/2}=\frac{2}n $$ Now, let $X$ be the total number of matchings with ones item from $S_1$ and the other from $S_2$, so $X=X_1+\dots+X_{n/2}$. Linearity of expectation implies $$ E[X]=\frac{n}{2}\cdot P(X_i=1)=\frac{n}2\cdot \frac2n=1 $$ However, what you want to show is $P(X>0)\ge \frac12$, so you need to relate $P(X>0)$ to $E[X]$. For this, we can use what is known as the second moment method: $$ P(X>0)\ge \frac{(E X)^2}{E[X^2]}=\frac{(E X)^2}{(E X)^2+\text{Var }X}=\frac{1}{1+\text{Var } X}. $$ Therefore, all you need is to show that $\text{Var }X\le 1$. You can prove this in three steps, the details of which I leave to you:

1. $\text{Var} X=\sum_{i=1}^{n/2} \text{Var }X_i+2\sum_{i<j}\text{Cov}(X_i,X_j).$

2. Show that $\text{Var } X_i\le \frac2n$.

3. Show that $\text{Cov}(X_i,X_j)\le 0$. This boils down to proving $$P(X_i=1\text{ and }X_j=1)\le P(X_i=1)\cdot P(X_j=1).$$ Intuitively, if the $i^\text{th}$ pair is "good" (meaning one from $S_1$, the other from $S_2$), then this decreases the probability the $j^\text{th}$ pair is good, since there are fewer elements of $S_1$ and $S_2$ available.