On the asymptotic behaviour of the probability of existence of equivalent tuples with nontrivial structure in a random sequence
Владимир Гаврилович Михайлов · Discrete Mathematics and Applications · 2008
In a long enough sequence of discrete random variables, as a rule, an s -tuple exists of nontrivial structure, that is, a tuple with at least one repeated symbol. We consider the case where the sequence consists of n + s – 1 independent random variables taking the values 1, …, N with equal probabilities. It is shown that as n → ∞, ns 3 N –2 → 0 the probability of that in the sequence s -tuples exist with the same nontrivial structure is equal to 1 – (1 + n/N ) s e –sn/N (1 + o (1)).