On estimation of the probability of absence of collisions of some random mappings |
| |
Authors: | R Gilchrist I N Kovalenko |
| |
Affiliation: | (1) Research Center STORM, North London University, Great Britain;(2) Cybernetics Institute, National Academy of Sciences of Ukraine, Kiev, Ukraine |
| |
Abstract: | Let X and Y be finite sets and φ: (X,Y) →Y be a mapping. Consider a random mapping i → φ(xi,yi), where xi are arbitrarily chosen from the set X, whereas (yi) is a random sample from Y without replacement. A two-sided bound is derived for the probability of absence of collisions
of this mapping. A case of mapping, defined as φ(x, y)=x+ y modulo n, is considered in particular. The results may be used in the selection of identification codes.
Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 132–137, January–February, 2000. |
| |
Keywords: | random mapping collision identification code |
本文献已被 SpringerLink 等数据库收录! |
|