1
$\begingroup$

I have two $A\times B$ arrays, where each element of a particular array stores a single integer selected uniformly and without replacement from a multiset (specific to each array) containing $k = A\times B$ copies of each integer over the range $[1, V]$. To clarify the "specific to each array" point, filling the first array with all $k=A\times B$ copies of the integer $1$ will not effect the probability of assigning a $1$ to a cell in the second array.

(Please notice the change to the above process of assigning random integers to array cells)

Provided the above random filling process, if I overlay the two arrays, what is the expectation and associated probability distribution for the number of identical overlapping elements?

  • 0
    @dtldarek The $V$ I'm imagining is small, ~6-10 or so, but I agree that sampling with replacement shouldn't matter in the limit of large $V$.2012-12-16

2 Answers 2

0

Obviously $V\geq k$, or else you would run out before filling the first array. Since the array labels themselves don't matter, assuming that $M$ and $N$ (the matrices) have been filled, relabel the first element of $M$ to be $0$, the next $1$, and so on, changing the equivalently labeled element in $N$, if one exists. label the $V-k$ elements that were not assigned with the rest of the numbers in the range $\{k,\dots,V-1\}$. Now there is only one matrix $N$, and I want to calculate ${\bf E}[X]$, where $X=|\{n\in\{0,\dots,k-1\}:n=N(n)\}|$. Now there are ${V\choose k}k!$ ways of selecting a subset (with ordering) on the matrix $N$ (ignoring the ordering on the $V-k$ elements that weren't chosen), and the number of these that place number $0$ where it should go is ${V-1\choose k-1}(k-1)!$, so that the probability that $0$ is in the right place is $\left[{V-1\choose k-1}(k-1)!\right]\Big/\left[{V\choose k}k!\right]=\frac1V$ and the same for $1$, $2$, etc. (the events are independent, since you never need to place the same number twice) so that and the total number of events is distributed binomially: $X\sim B\Big(k,\frac1V\!\Big)\Rightarrow{\bf E}[X]=\frac kV.$

Edit: It appears I have misunderstood the initial setup. The above analysis is for the numbers $\{1,\dots,V\}$ placed without replacement into array $M$, and the process repeated (with a new set) for $N$. If the set is instead the set $\{1_1,1_2,\dots,1_k,2_1,\dots,V_k\}$ containing $k$ copies of each number in the range $[1,V]$, then the process is a bit different, as there is a lot more correlation between the different numbers, and a lot more ways for a number to be repeated. I'm going to cheat and give up on that version, and instead use a model where the numbers are all independently chosen uniformly in the range $\{1,\dots,V\}$. This is the special case when the multiplicity of each element $k$ is much greater than the expected number of uses of that number $k/V$. It will give the exact answer for $V=1$, though, which is trivial.

The probability that the first element of $M$ is the same as $N$ is $1/V$, and each event is independent, so the total is the sum of $k$ of these and you get the same binomial distribution listed above. (This is curious, because in the context above, $V\geq k$, so it was predicting maybe 1 overlap in the whole grid. Now $V$ is possibly much less than $k$, but the formula is the same and correctly predicts $X=k$ with probability 1 if $V=1$.)

  • 0
    @MarioCarneiro You pick elements from a _multi_set, so $V = 1$ is enough and then both arrays will be filled with ones (or so I understood).2012-12-17
0

Let $W = [1,1,\ldots,1, 2,2,\ldots,2,3,\ldots,4,\ldots,V, V,\ldots,V]$ where there is $k = A\times B$ copies of each number. Let $W_1$ and $W_2$ be two independent random permutations of $W$, then we would like to know

$\mathbb{E}|\{i \in \{1,2,\ldots,k\} : W_1(i)=W_2(i)\}|$

However,

$\{i \in \{1,2,\ldots,k\} : W_1(i)=W_2(i)\} = \bigcup_{j = 1}^{k}\{i \in \{j\} : W_1(i) = W_2(i)\}$

Set $X_j = |\{i \in \{j\} : W_1(i) = W_2(i)\}|$ and then

$\mathbb{E}X = \mathbb{E}\sum_{j=1}^{k}X_j = \sum_{j=1}^{k}\mathbb{E}X_j = k\frac{V}{V^2} = \frac{k}{V}.$