DMTCS Proceedings, 2007 Conference on Analysis of Algorithms, AofA 07

Font Size:  Small  Medium  Large

Random permutations and their discrepancy process

Guillaume Chapuy


Let σ be a random permutation chosen uniformly over the symmetric group Sn. We study a new "process-valued" statistic of σ, which appears in the domain of computational biology to construct tests of similarity between ordered lists of genes. More precisely, we consider the following "partial sums": Y(n)p,q = card{1 ≤i ≤p : σi ≤q } for 0≤p,q≤n We show that a suitable normalization of Y(n) converges weakly to a bivariate tied down brownian bridge on [0,1]2, i.e. a continuous centered gaussian process X∞s,t of covariance: [X∞s,tX∞s',t'] = (min(s,s')-ss')(min(t,t')-tt')

Full Text: GZIP Compressed PostScript PostScript PDF

Valid XHTML 1.0 Transitional