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 Connect in order to contact the contributor
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

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, ⟨10.46298/dmtcs.3534⟩. ⟨hal-01184782⟩

Share

Metrics

Record views

120

Files downloads

415