On estimation of the probability of absence of collisions of some random mappings
type: Item
instance of: scholarly article
title: On estimation of the probability of absence of collisions of some random mappings
zbMATH Open document ID: 0971.68050
DOI: 10.1007/BF02733305
published in: Cybernetics and Systems Analysis
publication date: 2001-10-30T00:00:00Z
review text: 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\).
Mathematics Subject Classification ID: 68P30
Mathematics Subject Classification ID: 60C05
Mathematics Subject Classification ID: 94A62
zbMATH DE Number: 1551500
zbMATH Keywords: identification codes
author: Robert Gilchrist
author: I. M. Kovalenko
reviewed by: Ilya S. Molchanov
MaRDI profile type: Publication
cites work: Estimation of the number of ``good'' permutations with applications to cryptography
cites work: Q4769064
description: scientific article; zbMATH DE number 1551500