# Expected overlap of two arrays when the cells in each array are assigned a bounded random integer

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?

-
What do you mean by "allow for rotation"? Given two specific arrays, how would you calculate the number of overlapping elements, including rotation? Also, rectangular arrays can be turned upside down, and square arrays have four orientations. Did you mean that, or just the transpose for squares? – Mario Carneiro Dec 16 '12 at 22:15
@Mario Carneiro Imagine we write the arrays down, each on one side of two sheets of paper, and then overlay them by pressing together the sides on which they are printed. I will clarify the question. – Mike Dec 16 '12 at 22:18
@Mario Carneiro I've removed the bit about rotation to help focus the question. I've already made a substantial change to the filling process, so I think I'll stop there. – Mike Dec 16 '12 at 22:27
Is the "without replacement" condition essential? My intuition is that it shouldn't matter very much (at least with big $V$), and with replacement it is $\frac{k}{V}$ (associated probability distribution is just binomial distribution). – dtldarek Dec 16 '12 at 22:45
@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$. – Mike Dec 16 '12 at 23:25

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

-
Nice! Do you think a probability distribution for the number of matching symbols would be challenging to calculate? +1 as soon as I get on an actual computer and can register for the site. – Mike Dec 16 '12 at 23:29
Actually, this is the sum of $k$ independent Bernoulli-distributed variables, so it is binomially distributed as $B(k,1/V)$. – Mario Carneiro Dec 16 '12 at 23:33
@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). – dtldarek Dec 17 '12 at 8:30

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

-