# Lower Bound on Elements in Common After Relabeling

We have two lists of length $N$, $L_1$ and $L_2$. Each list consists of elements $\{1,\ldots,G\}$, where $G\ll N$. Denote the fraction of matching elements as $F(L_1,L_2)\equiv\frac{1}{N}\sum_k 1(L_1(k)=L_2(k))$.

Now fix the values of $L_1$, but allow permutations of the labels in $L_2$, e.g., $\{1,2,\ldots,8\}$ to $\{5,8,\ldots,3\}$. Define the maximal proportion matched across all permutations as $M(L_1,L_2)\equiv\arg\max_{P(G)} F(L_1,L_2(P(G))$.

Given $L_1$, and searching over $L_2$, what is the greatest lower bound on the maximal proportion $M$?

EDIT: As an example, suppose $L_1$ were {1,1,...,1} and $L_2$ were {2,2,...,2}. We would relabel 2 as 1 to get $L_2'$ as {1,1,...,1} and a match for every element. So, the problem can be understood as, given a list $L_1$, produce the adversarial list $L_2$ with the least number of matchings for the most favorable cipher (rearrangements of the alphabet $\{1,\ldots,G\}$).

If there is no closed-form solution, is there an algorithm to efficiently obtain this lower bound given $L_1$ and $G$, that is, one that does not require a search space that grows exponentially in $N$?

• "elements in common" seems to mean "same element in same position", since otherwise the permutation is without change. Is it ? Commented May 25, 2018 at 20:02
• We may interpret these words differently, so here's an example of what I mean: $L_1=\{1,2,1,2\}$ and $L_2=\{1,1,2,2\}$. $L_1(1)=L_2(1)$ and $L_1(4)=L_2(4)$, so $F(L_1,L_2)=\frac{1}{2}$. Also $M(L_1,L_2)=\frac{1}{2}$, and the lower bound is also $\frac{1}{2}$. Thanks! Commented May 25, 2018 at 20:06

Your lists are the same as words of length N from the alphabet $\{1,2,\cdots, G\}$.

Understanding "in common" as "matching (i.e. same value and same position)", then if $L_2$ has $m$ matchings and $q$ characters in common ( independently from the position) with $L_1$, then it is clear that $m \le q$, and that it is always possible to permute $L_2$ as to transform all $q$ into matchings.

As to the probability of having $m$ matchings or $q$ characters in common between two lists (words) of length $n$, I just replied to a similar question: although the probabilities given there is for not having any matching/common character, the Premise therein is what you need to start with. In fact, it is clear that the maximum of the matchings equals the characters that the two strings have in common, each repeated with the lowest repetition found in each string.
Then the minimum of such maximum of matching is just $0$ : the two words do not have any character in common , although derived from the same alphabet. And, assuming the characters have the same probability to appear, the probability of having that is: $$Q_{\,a} (G,N) = {1 \over {G^{\,2N} }}\sum\limits_{1\, \le \,\,k\, \le \,G} {\;\left( \matrix{ G \cr k \cr} \right)\left( {\,G - k} \right)^{\,N} } k!\left\{ \matrix{ N \cr k \cr} \right\}$$

And it seems that what you need is an asymptotic expansion of it for $N \to \infty$: is that right ?

• Yes, thank you for clarifying my vocabulary. You are correct that $q$ is a lower bound. However, $q$ is a very loose lower bound, particularly for $N>>G$. Surely tighter lower bounds can be obtained by conditioning on the distribution of letters in $L_1$? My scenario is the reverse of that you address. There $N<<G$. Commented May 25, 2018 at 20:36
• Not really: the scenario is quite the same. We are speaking (I suppose) about the characters having the same probability, so para. 3) in that answer is a basis. If you are looking for $G<<N$, it means you need an asymptotic expansion. Or are you looking just for an algorithm ? Commented May 25, 2018 at 21:04
• I do not see how your answer addresses potential reshuffling of the group labels. The count that is matched depends on the cipher we use, e.g., {1,2,...,G} or {1,5,...,8}. An asymptotic expansion may be required. If it helps I suspect, but cannot prove (so far), that the solution is $G/N$ as $N/G\to\infty$. An algorithm that doesn't require checking all $N$ choose $G$ permutations is also welcome if no such solution exists. Commented May 25, 2018 at 21:20
• @Wilbur: I expanded my answer: it seems that there might be a misunderstanding between us about the "..greatest lower bound on the maximal proportion..". Can you please clarify ? Commented May 25, 2018 at 21:41
• @Wilbur: Ah yes, it does clarify ! LABEL to me meant the position not the value of the character: So I suggest you rewrite your question, adding example as above to make clear what you mean. Commented May 26, 2018 at 0:17