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$
7
  • 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
    Commented May 10, 2020 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
    Commented May 10, 2020 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$ Commented May 10, 2020 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$ Commented May 10, 2020 at 2:11
  • 1
    $\begingroup$ It seems to me that it would be clearer to phrase this without the matrix. $\endgroup$
    – user44191
    Commented May 10, 2020 at 14:57

1 Answer 1

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

$\endgroup$
4
  • $\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$ Commented May 10, 2020 at 13:27
  • 1
    $\begingroup$ @CarlosA.AstudilloTrujillo: Yes. Selection with replacement is similar - added it now $\endgroup$ Commented May 10, 2020 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$ Commented May 10, 2020 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$ Commented May 10, 2020 at 15:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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