hal-00567091, version 1
Constant time estimation of ranking statistics by analytic combinatorics
Cyril Banderier 1Pierre Nicodeme 2, 3
Statistical Methods for Post-Genomic Data (2011) no page numbering
Résumé : 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).
- 1 : Laboratoire d'informatique de Paris-nord (LIPN)
- CNRS : UMR7030 – Université Paris XIII - Paris Nord
- 2 : Laboratoire d'informatique de l'école polytechnique (LIX)
- CNRS : UMR7161 – Polytechnique - X
- 3 : AMIB (INRIA Saclay - Ile de France)
- INRIA – Polytechnique - X – CNRS : UMR7161 – Université Paris XI - Paris Sud – CNRS : UMR8623
- Domaine : Informatique/Mathématique discrète
- Mots-clés : ranking statictics – analytic combinatorics – Rayleigh function
- hal-00567091, version 1
- http://hal.archives-ouvertes.fr/hal-00567091
- oai:hal.archives-ouvertes.fr:hal-00567091
- Contributeur : Pierre Nicodeme
- Soumis le : Vendredi 18 Février 2011, 10:53:21
- Dernière modification le : Vendredi 18 Février 2011, 14:09:48






Documents associés
Exporter