On the number of readings of random nonequiprobable files under stable sorting
Diskretnaya Matematika, Tome 8 (1996) no. 2, pp. 14-30
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.
@article{DM_1996_8_2_a1,
author = {V. A. Vatutin and V. G. Mikhailov},
title = {On the number of readings of random nonequiprobable files under stable sorting},
journal = {Diskretnaya Matematika},
pages = {14--30},
publisher = {mathdoc},
volume = {8},
number = {2},
year = {1996},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/DM_1996_8_2_a1/}
}
TY - JOUR AU - V. A. Vatutin AU - V. G. Mikhailov TI - On the number of readings of random nonequiprobable files under stable sorting JO - Diskretnaya Matematika PY - 1996 SP - 14 EP - 30 VL - 8 IS - 2 PB - mathdoc UR - http://geodesic.mathdoc.fr/item/DM_1996_8_2_a1/ LA - ru ID - DM_1996_8_2_a1 ER -
V. A. Vatutin; V. G. Mikhailov. On the number of readings of random nonequiprobable files under stable sorting. Diskretnaya Matematika, Tome 8 (1996) no. 2, pp. 14-30. http://geodesic.mathdoc.fr/item/DM_1996_8_2_a1/