On estimation of the probability of absence of collisions of some random mappings (Q1592011)

Let \(X\) and \(Y\) be finite sets and \(\varphi: X\times Y\to Y\) be a mapping, which is typically assumed to be a bijection with respect to \(y\). For a fixed subset \(\{x_1,\dots, x_k\}\subset X\), the authors obtain two-side bounds for the probability that \(\varphi(x_i, y_i)= \varphi(x_j, y_j)\) for \(1\leq i\neq j\leq k\), where \(\{y_1,\dots, y_k\}\) is a random sample from \(Y\) without replacement. A case of mapping \(\varphi(x, y)= x+y\) modulo \(n\) is considered in particular. The results may be used in the selection of identification codes, where \(x_i\) represents the code chosen by the subscriber and \(y_i\) is the code assigned by the system, so that \(\varphi(x_i, y_i)\) represents the identification code for subscriber \(i\).