On a probabilistic approach to the estimation of reliability of the Hellman method

The evaluation of the reliability of the Hellman method reduces to estimating the mean value of a random number $\xi(m, t, N)$ of different elements of the set $X$ in a table containing $m$ records of $t$ iterations of function $F : X \to X$. We suggest a probabilistic model, within which estimates of the deviation of the mean value of $\xi(m, t, N)/(mt)$ from its approximation are obtained. The properties of the $F$ function that significantly affect the reliability of the method are revealed. The estimation of the mean value of $\xi(m, t, N)$ is carried out using the appropriate Galton–Watson process.