# Constant time estimation of ranking statistics by analytic combinatorics

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).
Keywords :
Document type :
Conference papers

Cited literature [7 references]

https://hal.archives-ouvertes.fr/hal-00567091
Contributor : Pierre Nicodeme <>
Submitted on : Friday, February 18, 2011 - 10:53:21 AM
Last modification on : Tuesday, April 21, 2020 - 1:10:04 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⟩

Record views
{"ft_lang_label":"__label__en","ft_lang_prob":0.8968014,"math_prob":0.82114303,"size":1258,"snap":"2020-34-2020-40","text_gpt3_token_len":306,"char_repetition_ratio":0.1108453,"word_repetition_ratio":0.0,"special_character_ratio":0.2607313,"punctuation_ratio":0.10902256,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9779869,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2020-08-13T09:42:02Z\",\"WARC-Record-ID\":\"<urn:uuid:e8898fc0-cb35-434c-a356-5d8193a0c716>\",\"Content-Length\":\"52013\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:62c46796-03ce-401e-819c-072744e5b5cb>\",\"WARC-Concurrent-To\":\"<urn:uuid:cd8402a2-ff67-4702-a5b6-e476df83c4eb>\",\"WARC-IP-Address\":\"193.48.96.10\",\"WARC-Target-URI\":\"https://hal.archives-ouvertes.fr/hal-00567091\",\"WARC-Payload-Digest\":\"sha1:3EF2DF7AOUAE54VIUEHNQWMZ56L4DHZV\",\"WARC-Block-Digest\":\"sha1:KNJ3HGBD7ST5IFE6LHUPOBX37KTXM7IV\",\"WARC-Identified-Payload-Type\":\"application/xhtml+xml\",\"warc_filename\":\"/cc_download/warc_2020/CC-MAIN-2020-34/CC-MAIN-2020-34_segments_1596439738964.20_warc_CC-MAIN-20200813073451-20200813103451-00583.warc.gz\"}"}