Constant time estimation of ranking statistics by analytic combinatorics

Cyril Banderier 1 Pierre Nicodeme 2, 3
3 AMIB - Algorithms and Models for Integrative Biology
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, Polytechnique - X, CNRS - Centre National de la Recherche Scientifique : UMR8623
Abstract : We consider i.i.d. increments (or jumps) X_i that are integers in [-c,...,+d], the partial sums S_j, and the discrete walks (j,S_j) with 1 <= j <= n. Late conditioning by a return of the walk to zero at time n provides discrete bridges that we note B_j with 1<= j <= n. We give in this extended abstract the asymptotic law in the central domain of the height max_{1<= j <= n}B_j of the bridges as n tends to infinity. As expected, this law converges to the Rayleigh law which is the law of the maximum of a standard Brownian bridge. In the case where c=1 (only one negative jump), we provide a full expansion of the asymptotic limit which improves upon the rate of convergence O(log(n)/sqrt(n)) given by Borisov (78) for lattice jumps; this applies in particular to the case where X_i is in {-1,+d}, in which case the expansion is expressible as a function of n, d and of the height of the bridge. Applying this expansion for X_i in {-1,d/c} gives an excellent approximation of the case X_i in {-d,+c} and provides in constant time an indicator used in ranking statistics; this indicator can be used for medical diagnosis and bioinformatics analysis (see Keller et al. (2007)) who compute it in time O(n min(c,d)) by use of dynamical programming).
Type de document :
Communication dans un congrès
Statistical Methods for Post-Genomic Data, Jan 2011, Paris, France. no page numbering, 2011
Liste complète des métadonnées

Littérature citée [7 références]  Voir  Masquer  Télécharger

https://hal.archives-ouvertes.fr/hal-00567091
Contributeur : Pierre Nicodeme <>
Soumis le : vendredi 18 février 2011 - 10:53:21
Dernière modification le : jeudi 9 février 2017 - 15:13:05

Fichier

smpgd11.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00567091, version 1

Citation

Cyril Banderier, Pierre Nicodeme. Constant time estimation of ranking statistics by analytic combinatorics. Statistical Methods for Post-Genomic Data, Jan 2011, Paris, France. no page numbering, 2011. 〈hal-00567091〉

Partager

Métriques

Consultations de
la notice

389

Téléchargements du document

134