Average number of elements of a subset S of a matrix A after inducing the rows and columns of m randomly selected elements from subset S

Question

Let $A_{N{\times}N}$ be an $N{\times}N$ matrix and $\mathcal{S_{k}}$ be a subset of elements in $A$ such that exactly $k$ elements from every row and column in $A$ are in $\mathcal{S_{k}}$. Thus, $\mathcal{S_k}$ has cardinality $N{\cdot}k$, with $k \in \{1,2,..,N\}$.

\begin{equation*} A_{N,N} = \begin{pmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,N} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,N} \\ \vdots & \vdots & \ddots & \vdots \\ a_{N,1} & a_{N,2} & \cdots & a_{N,N} \end{pmatrix} \end{equation*}

For instance, consider $A_{8{\times}8}$ as described below. Let subset $S_{2}$ of the matrix $A_{8{\times}8}$ be given by the elements in bold in $A_{8{\times}8}$. Note that $S$ can be any subset having as its elements exactly $k=2$ elements per column and row of $A_{8{\times}8}$.

\begin{equation*} A_{8,8} = \begin{pmatrix} \mathbf{a_{1,1}} & a_{1,2} & a_{1,3} & a_{1,4} & a_{1,5} & a_{1,6} & a_{1,7} & \mathbf{a_{1,8}} \\ \mathbf{a_{2,1}} & \mathbf{a_{2,2}} & a_{2,3} & a_{2,4} & a_{2,5} & a_{2,6} & a_{2,7} & a_{2,8} \\ a_{3,1} & \mathbf{a_{3,2}} & \mathbf{a_{3,3}} & a_{3,4} & a_{3,5} & a_{3,6} & a_{3,7} & a_{3,8} \\ a_{4,1} & a_{4,2} & \mathbf{a_{4,3}} & \mathbf{a_{4,4}} & a_{4,5} & a_{4,6} & a_{4,7} & a_{4,8} \\ a_{5,1} & a_{5,2} & a_{5,3} & \mathbf{a_{5,4}} & \mathbf{a_{5,5}} & a_{5,6} & a_{5,7} & a_{5,8} \\ a_{6,1} & a_{6,2} & a_{6,3} & a_{6,4} & \mathbf{a_{6,5}} & \mathbf{a_{6,6}} & a_{6,7} & a_{6,8} \\ a_{7,1} & a_{7,2} & a_{7,3} & a_{7,4} & a_{7,5} & \mathbf{a_{7,6}} & \mathbf{a_{7,7}} & a_{7,8} \\ a_{8,1} & a_{8,2} & a_{8,3} & a_{8,4} & a_{8,5} & a_{8,6} & \mathbf{a_{8,7}} & \mathbf{a_{8,8}} \end{pmatrix} \end{equation*}

Now, select randomly $m$ elements from $\mathcal{S_{k}}$ with replacement. Then, we create an induced matrix with just the rows and columns of $A_{N{\times}N}$ corresponding to the selected elements from $\mathcal{S_{k}}$. For instance, if after selecting $m$ elements with replacement, the uniquely selected elements from $S_{2}$ are the following 5 elements: $a_{1,1},a_{3,2},a_{3,3},a_{6,6},a_{8,8}$, then the resultant matrix is

\begin{equation*} A_{r} = \begin{pmatrix} \mathbf{a_{1,1}} & a_{1,2} & a_{1,3} & a_{1,6} & \mathbf{a_{1,8}} \\ a_{3,1} & \mathbf{a_{3,2}} & \mathbf{a_{3,3}} & a_{3,6} & a_{3,8} \\ a_{6,1} & a_{6,2} & a_{6,3} & \mathbf{a_{6,6}} & a_{6,8} \\ a_{8,1} & a_{8,2} & a_{8,3} & a_{8,6} & \mathbf{a_{8,8}} \end{pmatrix} \end{equation*}

Let $X$ be the number of elements in $\mathcal{S_{k}}$ of the resultant matrix ($A_{r}$). For the given example, $x=6$.

My Question: How we can calculate the average of $X$ for given $m,N,k$ ($E[X](N,k,m))$?

I have already calculated the average number of columns $E(C)$ when $m$ elements are randomly selected with replacement from $\mathcal{S_{k}}$. Note that for this case $E(C)$ is equal to the average number of rows $E(R)$ and can be calculated as:

$E[C](N,m)=N*P_{chosen}$, where $P_{chosen}=1-(1-(1/N))^m)$ is the probability that a column of the original matrix is selected at least once. Thus, $A_{r}$ is a $E[C] \times E[R]$ matrix.

Thank you for any help!

---

An alternative phrasing: Write $I_N = \{1, 2, \cdots, N\}$. Let $S \in I_N \times I_N$ be a subset such that $|S \cap (\{i\} \times I_N)| = |S \cap (I_N \times \{i\})| = 2$. Note that $|S| = 2N$.

Then for given $0 \leq m \leq 2k$, what is the distribution of $|p_1(M)| |p_2(M_m)|$, where $M_m$ ranges uniformly over the set of $m$-element subsets of $S$, and $p_1, p_2$ are the projection functions?

Answer 1

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