2
$\begingroup$

Problem specification

Suppose we have a matrix $A$ of size $(n, m)$ with elements $A_{i,j}$ with $i \in [0, n)$ and $j \in [0, m)$. Now, we partition the matrix randomly into $n$ vectors this way: for each $j$, we let $\pi_j(i) \in [0, n)$ (= a random permutation of row indices) and then the $n$ vectors $v$ indexed by $i$ will be $v_i = [A_{\pi_0(i), 0},\ A_{\pi_1(i), 1},\ A_{\pi_2(i), 2},\ ...,\ A_{\pi_m(i), m}]$.

Here's my crude visualization of those vectors $v_i$. enter image description here

Let us also assume that $A$ always contains the same, distinct elements (imagine whole numbers from $0$ to $n \times m - 1$ for example).

What I'm interested in is that, given an integer $K$ and the matrix size $n$ and $m$, if we split the same matrix $A$ into $n$ vectors $v_i$ $K$ times, and after each partitioning of $A$ add all of those vectors $v_i$ into a single set (which will contain $n \times K$ elements at the end), what is the expected amount of duplicate vectors in the set ?

My insights

I've acquainted myself with the basic combinatorics, but this is a problem currently beyond my reach (and before you ask, no, this is not a school homework puzzle, but a problem arisen from my investigation of student task distributions in a research project, detes irrelevant).

I've observed that the total amount of different partitions into $v_i$ is, hopefully, $n^m \cdot (n-1)^m \cdot (n-2)^m\ ...\ 1^m$, or $(n!)^m$, and every vector $v_i$ has the same probability of occuring, that is, $\frac{1}{n^m}$, but otherwise, the fact that the individual vectors within a single partition are highly dependent on one another is just... perplexing to me. I'm unsure if I can use this answer about duplicate counts to just claim that the answer to my problem is simply $Kn - n^m + \sum_{i=0}^{n^m - 1} (1 - \frac{1}{n^m})^{Kn}$ because the vectors are definitely not independently generated.

I will appretiate anything you'll be able to add to the topic, thank you very much.

EDIT (duplicate count definition):

I let the "amount of duplicates" be $\sum_{C \in equivalence\_partition} (|C| - 1)$, so, e.g. if we had a set $\{0, 0, 0, 1, 1, 2, 3\}$, the sum would yield sum for zeroes + sum for ones + sum for twos + sum for threes = $(3-1) + (2-1) + (1-1) + (1-1) = 2 + 1 + 0 + 0 = 3$.

The equivalence relation on the set of all $v_i$ after $K$ samples is trivial.

$\endgroup$
4
  • $\begingroup$ if the same vector appears three times does that count as $1$? $\endgroup$
    – Asinomás
    Apr 27, 2021 at 19:36
  • $\begingroup$ @HereToRelax Sorry for late response. I haven't properly defined the notion of "amount of duplicates", so I will add that to my question. $\endgroup$ Apr 27, 2021 at 21:31
  • $\begingroup$ With that definition of duplicate it becomes a bit more tricky but the idea is similar. $\endgroup$
    – Asinomás
    Apr 27, 2021 at 21:55
  • $\begingroup$ @HereToRelax I'm currently grasping your answer. Give me a few minutes :D $\endgroup$ Apr 27, 2021 at 21:57

1 Answer 1

1
$\begingroup$

For each of the $n^m$ vectors what is the expected duplication count?

Suppose the vector $v$ contains $A_{i,1}$. Then the vector that contains $A_{i,1}$ in each of the partitions is $v$ with probability $\frac{1}{n^{m-1}}$. It follows the probability that the vector $v$ appears exactly $s$ times is $\binom{K}{s}(1-\frac{1}{n^{m-1}})^{K-s}(\frac{1}{n^{m-1}})^s$. Hence the expected "duplication count" for each vector is $\sum\limits_{s=2}^K (s-1)\binom{K}{s}(1-\frac{1}{n^{m-1}})^{K-s}(\frac{1}{n^{m-1}})^s$.

From the principle of linearity of expectation, it follows that the total expected duplication count is:

$n^m\sum\limits_{s=2}^K \binom{K}{s}(s-1)(1-\frac{1}{n^{m-1}})^{K-s}(\frac{1}{n^{m-1}})^s$.

$\endgroup$
14
  • $\begingroup$ Basically the important hint is: In each partition there is only one vector that contains $A_{1,j}$ for each $j$. and every possible vector has the same probability. $\endgroup$
    – Asinomás
    Apr 27, 2021 at 19:49
  • 1
    $\begingroup$ I realized I used $i$ twice for different things. So I added an $s$ variable. $\endgroup$
    – Asinomás
    Apr 27, 2021 at 22:11
  • $\begingroup$ I believe there might have been a misunderstandment. Are you sure we're looking for full duplicate vectors, like $[0, 1, 5, 3] = [0, 1, 5, 3]$, and not only the duplicates of individual members of $A$? If that was not clear from the question, sorry, I'll add more info. If you did in fact understand this and your answer encorporates this fact, then let me know. So e.g.: {[0, 1, 2], [0, 3, 2], [2, 3, 4], [0, 3, 2]} has two duplicate vectors [0, 3, 2]. $\endgroup$ Apr 27, 2021 at 22:13
  • $\begingroup$ I am looking for full duplicate vectors. Each partition gives us $n$ vectors, and each of these vectors contains one of the values in the first column, right? $\endgroup$
    – Asinomás
    Apr 27, 2021 at 22:15
  • $\begingroup$ Each partition gives us $n$ vectors, yes, and each of those $n$ vectors contains exactly one value from the first column, just like in the picture. $\endgroup$ Apr 27, 2021 at 22:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .