Skip to Main content Skip to Navigation
Conference papers

Random permutations and their discrepancy process

Abstract : Let $\sigma$ be a random permutation chosen uniformly over the symmetric group $\mathfrak{S}_n$. We study a new "process-valued" statistic of $\sigma$, 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} = \mathrm{card} \{1 \leq i \leq p : \sigma_i \leq q \}$ for $0 \leq p,q \leq 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^{\infty}_{s,t}$ of covariance: $\mathbb{E}[X^{\infty}_{s,t}X^{\infty}_{s',t'}] = (min(s,s')-ss')(min(t,t')-tt')$.
Complete list of metadata

Cited literature [9 references]  Display  Hide  Download

https://hal.inria.fr/hal-01184782
Contributor : Coordination Episciences Iam <>
Submitted on : Monday, August 17, 2015 - 4:59:29 PM
Last modification on : Thursday, March 5, 2020 - 6:31:07 PM
Long-term archiving on: : Wednesday, November 18, 2015 - 12:16:21 PM

File

dmAH0131.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01184782, version 1

Collections

Citation

Guillaume Chapuy. Random permutations and their discrepancy process. 2007 Conference on Analysis of Algorithms, AofA 07, 2007, Juan les Pins, France. pp.457-470. ⟨hal-01184782⟩

Share

Metrics

Record views

198

Files downloads

561