Geodesic
Asymptotics of the occupancy scheme in a random environment and its applications to tries
Discrete mathematics & theoretical computer science, Tome 19 (2017-2018) no. 1

Voir la notice de l'article provenant de la source Episciences

Consider $ m $ copies of an irreducible, aperiodic Markov chain $ Y $ taking values in a finite state space. The asymptotics as $ m $ tends to infinity, of the first time from which on the trajectories of the $ m $ copies differ, have been studied by Szpankowski (1991) in the setting of tries. We use a different approach and model the $ m $ trajectories by a variant of the occupancy scheme, where we consider a nested sequence of boxes. This approach will enable us to extend the result to the case when the transition probabilities are random. We moreover use the same techniques to study the asymptotics as $ m $ tends to infinity of the time up to which we have observed all the possible trajectories of $ Y $ in random and nonrandom scenery. 
@article{DMTCS_2017_19_1_a21,
     author = {Businger, Silvia},
     title = {Asymptotics of the occupancy scheme in a random environment and its applications to tries},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {19},
     number = {1},
     year = {2017-2018},
     doi = {10.23638/DMTCS-19-1-22},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-1-22/}
}
TY  - JOUR
AU  - Businger, Silvia
TI  - Asymptotics of the occupancy scheme in a random environment and its applications to tries
JO  - Discrete mathematics & theoretical computer science
PY  - 2017-2018
VL  - 19
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-1-22/
DO  - 10.23638/DMTCS-19-1-22
LA  - en
ID  - DMTCS_2017_19_1_a21
ER  - 
%0 Journal Article
%A Businger, Silvia
%T Asymptotics of the occupancy scheme in a random environment and its applications to tries
%J Discrete mathematics & theoretical computer science
%D 2017-2018
%V 19
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-1-22/
%R 10.23638/DMTCS-19-1-22
%G en
%F DMTCS_2017_19_1_a21
Businger, Silvia. Asymptotics of the occupancy scheme in a random environment and its applications to tries. Discrete mathematics & theoretical computer science, Tome 19 (2017-2018) no. 1. doi: 10.23638/DMTCS-19-1-22

Cité par Sources :