HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

Constant time estimation of ranking statistics by analytic combinatorics

Cyril Banderier 1 Pierre Nicodème 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
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).
Document type :
Conference papers
Complete list of metadata

Cited literature [7 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-00567091
Contributor : Pierre Nicodeme Connect in order to contact the contributor
Submitted on : Friday, February 18, 2011 - 10:53:21 AM
Last modification on : Thursday, July 8, 2021 - 3:48:43 AM

File

smpgd11.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00567091, version 1

Citation

Cyril Banderier, Pierre Nicodème. Constant time estimation of ranking statistics by analytic combinatorics. Statistical Methods for Post-Genomic Data, Jan 2011, Paris, France. no page numbering. ⟨hal-00567091⟩

Share

Metrics

Record views

323

Files downloads

60