Return to Answer

Suppose that we selected $m$ random elements of $S_k$. An element $s$ of $S_k$ appears in the induced matrix iff (i) there is a selected element in the row of $s$ in $A$; and (ii) there is a selected element in the column of $s$ in $A$. Call such an element $s$ lucky, and so $X$ is the number of lucky elements.

Under selection without replacement, the probability $P$ of a fixed element $s\in S_k$ to be lucky equals $$P = 1 - \frac{2\binom{Nk-k}{m} - \binom{Nk-(2k-1)}{m}}{\binom{Nk}{m}},$$ where $\binom{Nk-k}{m}/\binom{Nk}{m}$ is the probability that nothing is selected from the row of $s$ in $A$, and $\binom{Nk-(2k-1)}{m}/\binom{Nk}{m}$ is the probability that nothing is selected from neither the row nor the column of $s$ in $A$.

Similarly, under selection with replacement, we have $$P = 1 - \frac{2(Nk-k)^m - (Nk-(2k-1))^m}{Nk^m}.$$

Then $$E[X](m,N,k) = Nk\cdot P.$$

Suppose that we selected $m$ random elements of $S_k$. An element $s$ of $S_k$ appears in the induced matrix iff (i) there is a selected element in the row of $s$ in $A$; and (ii) there is a selected element in the column of $s$ in $A$. Call such an element $s$ lucky, and so $X$ is the number of lucky elements.

Under selection without replacement, the probability $P$ of a fixed element $s\in S_k$ to be lucky equals $$P = 1 - \frac{2\binom{Nk-k}{m} - \binom{Nk-(2k-1)}{m}}{\binom{Nk}{m}},$$ where $\binom{Nk-k}{m}/\binom{Nk}{m}$ is the probability that nothing is selected from the row of $s$ in $A$, and $\binom{Nk-(2k-1)}{m}/\binom{Nk}{m}$ is the probability that nothing is selected from neither the row nor the column of $s$ in $A$.

Similarly, under selection with replacement, we have $$P = 1 - \frac{2(Nk-k)^m - (Nk-(2k-1))^m}{(Nk)^m}.$$

Then $$E[X](m,N,k) = Nk\cdot P.$$

Suppose that we selected $m$ random elements of $S_k$. An element $s$ of $S_k$ appears in the induced matrix iff (i) there is a selected element in the row of $s$ in $A$; and (ii) there is a selected element in the column of $s$ in $A$. Call such an element $s$ lucky, and so $X$ is the number of lucky elements.

The probability of a fixed element $s\in S_k$ to be lucky equals $$P := 1 - \frac{2\binom{Nk-k}{m} - \binom{Nk-(2k-1)}{m}}{\binom{Nk}{m}},$$ where $\binom{Nk-k}{m}/\binom{Nk}{m}$ is the probability that nothing is selected from the row of $s$ in $A$, and $\binom{Nk-(2k-1)}{m}/\binom{Nk}{m}$ is the probability that nothing is selected from neither the row nor the column of $s$ in $A$.

Then $$E[X](m,N,k) = Nk\cdot P.$$

Suppose that we selected $m$ random elements of $S_k$. An element $s$ of $S_k$ appears in the induced matrix iff (i) there is a selected element in the row of $s$ in $A$; and (ii) there is a selected element in the column of $s$ in $A$. Call such an element $s$ lucky, and so $X$ is the number of lucky elements.

Under selection without replacement, the probability $P$ of a fixed element $s\in S_k$ to be lucky equals $$P = 1 - \frac{2\binom{Nk-k}{m} - \binom{Nk-(2k-1)}{m}}{\binom{Nk}{m}},$$ where $\binom{Nk-k}{m}/\binom{Nk}{m}$ is the probability that nothing is selected from the row of $s$ in $A$, and $\binom{Nk-(2k-1)}{m}/\binom{Nk}{m}$ is the probability that nothing is selected from neither the row nor the column of $s$ in $A$.

Similarly, under selection with replacement, we have $$P = 1 - \frac{2(Nk-k)^m - (Nk-(2k-1))^m}{Nk^m}.$$

Then $$E[X](m,N,k) = Nk\cdot P.$$

Consider a graph $G$ on the vertex set $S_k$, where there edges of two colors: black edges connect vertices from the same row of $A$, and red edges connect vertices from the same column of $A$. Clearly, each vertex is incident to $k-1$ black and $k-1$ red edges.

Suppose now that we selected $m$ random elements of $S_k$, that is $m$ vertices of $G$. A vertex $s$ of $S_k$ appears in the induced matrix iff (i) $s$ is selected; or (ii) there is a black edge connecting $s$ to a selected vertex and there is a red edge connecting $s$ to a selected vertex. Call such a vertex $s$ lucky, and let $q$ denote the number of lucky vertices. It is easy to see that $X=q$, and thus $$E[X](m,N,k) = E[q].$$

The probability of a fixed vertex to be lucky equals $$P := 1 - \frac{2\binom{Nk-k}{m} - \binom{Nk-(2k-1)}{m}}{\binom{Nk}{m}}.$$ Then $$E[X](m,N,k) = Nk\cdot P.$$

Suppose that we selected $m$ random elements of $S_k$. An element $s$ of $S_k$ appears in the induced matrix iff (i) there is a selected element in the row of $s$ in $A$; and (ii) there is a selected element in the column of $s$ in $A$. Call such an element $s$ lucky, and so $X$ is the number of lucky elements.

The probability of a fixed element $s\in S_k$ to be lucky equals $$P := 1 - \frac{2\binom{Nk-k}{m} - \binom{Nk-(2k-1)}{m}}{\binom{Nk}{m}},$$ where $\binom{Nk-k}{m}/\binom{Nk}{m}$ is the probability that nothing is selected from the row of $s$ in $A$, and $\binom{Nk-(2k-1)}{m}/\binom{Nk}{m}$ is the probability that nothing is selected from neither the row nor the column of $s$ in $A$.

Then $$E[X](m,N,k) = Nk\cdot P.$$