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
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 metadatas

Cited literature [7 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-00567091
Contributor : Pierre Nicodeme <>
Submitted on : Friday, February 18, 2011 - 10:53:21 AM
Last modification on : Wednesday, March 27, 2019 - 4:41:29 PM

File

smpgd11.pdf
Files produced by the author(s)

Identifiers

  • 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. ⟨hal-00567091⟩

Share

Metrics

Record views

609

Files downloads

154