2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ I don't quite understand this question—for example, is it a question about a particular matrix $A$, or about any matrix?—but this seems to be an elementary probability question, not a research-level question, and so does not belong on MO. If you want to clarify it for MO, or ask it again on MSE, I encourage you to TeX it so that it will be easier to read. $\endgroup$ – LSpice May 10 at 0:43
  • 1
    $\begingroup$ Welcome to MO. It's good to have an example, but eventually the question is really unclear. It might be that the question would eventually fit MO, but I currently can't quite follow. Use crisper definitions and state a more precise question. $\endgroup$ – Amir Sagiv May 10 at 0:46
  • 1
    $\begingroup$ Thank you @LSpice for your comments and suggestions. I rephrased the problem, detailed it better, and used LaTex. I don't know if it fits better here or on MSE. $\endgroup$ – Carlos A. Astudillo Trujillo May 10 at 2:10
  • 1
    $\begingroup$ Thank you @AmirSagiv. I tried to explain better the problem. Please help me to define if it fits better here or on MSE. $\endgroup$ – Carlos A. Astudillo Trujillo May 10 at 2:11
  • 1
    $\begingroup$ It seems to me that it would be clearer to phrase this without the matrix. $\endgroup$ – user44191 May 10 at 14:57
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you @Max for your answer. It seems that in your solution $m$ is the number of unique selected elements, is it right? $\endgroup$ – Carlos A. Astudillo Trujillo May 10 at 13:27
  • 1
    $\begingroup$ @CarlosA.AstudilloTrujillo: Yes. Selection with replacement is similar - added it now $\endgroup$ – Max Alekseyev May 10 at 13:43
  • $\begingroup$ Another option to answer my initial question is just to consider $m$ as $m^{′}$ in your formula without replacement and calculate $m{′}=N{\cdot}k\left(1−B_{0}(n,p)\right)$, where $B_{r}(n,p)$ is the binomial distribution with parameters $n=m$ (as defined in the initial question), $p=\frac{1}{N{\cdot}k}$ and $r$ is the number of times an element in $S_k$ is selected. Thus, $1−B_{0}(n,p)$ is the probability that an element of $S_{k}$ is selected at least once in $n$ trials. $\endgroup$ – Carlos A. Astudillo Trujillo May 10 at 14:30
  • 1
    $\begingroup$ I tested your solution of selection with replacement and it is more accurate than my previous suggestion of considering $m^{'}$ and selection without replacement. Thank you again. $\endgroup$ – Carlos A. Astudillo Trujillo May 10 at 15:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.