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$ 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 :)
 A: 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:

*

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


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


*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.
