On the number of readings of random nonequiprobable files under stable sorting
Diskretnaya Matematika, Tome 8 (1996) no. 2, pp. 14-30
Citer cet article
Voir la notice de l'article provenant de la source Math-Net.Ru
Let a random file $\cal F$ consist of labels $F_1,\ldots,F_n$ which are independent random elements of an alphabet $A=\{A_1,\ldots,A_N\}$ having one and the same (not necessarily uniform) distribution. We study the random variable $\zeta$, the number of readings of $\cal F$, or, what is the same, the number of ascending segments in the permutation which provides the stable sorting of $\cal F$. Sufficient conditions are given for the random variable $\zeta$ to be asymptotically normal as $n,N\to\infty$. This paper is closely related to the paper [1] which studies the case of stable sorting of files consisting of labels uniformly distributed over the set of all words of length $n$ over the alphabet $A$.This work is supported by the Russian Foundation for Basic Researches, Grant 93–011–1441.