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')$.
Keywords :
Type de document :
Communication dans un congrès
Jacquet, Philippe. 2007 Conference on Analysis of Algorithms, AofA 07, 2007, Juan les Pins, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07), pp.457-470, 2007, DMTCS Proceedings
Domaine :

Littérature citée [9 références]

https://hal.inria.fr/hal-01184782
Contributeur : Coordination Episciences Iam <>
Soumis le : lundi 17 août 2015 - 16:59:29
Dernière modification le : mercredi 23 janvier 2019 - 10:29:09
Document(s) archivé(s) le : mercredi 18 novembre 2015 - 12:16:21

Fichier

dmAH0131.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

• HAL Id : hal-01184782, version 1

Citation

Guillaume Chapuy. Random permutations and their discrepancy process. Jacquet, Philippe. 2007 Conference on Analysis of Algorithms, AofA 07, 2007, Juan les Pins, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07), pp.457-470, 2007, DMTCS Proceedings. 〈hal-01184782〉

Métriques

Consultations de la notice

164

Téléchargements de fichiers