Random permutations and their discrepancy process
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 c...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2007-01-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/3534/pdf |
| _version_ | 1827324047791226880 |
|---|---|
| author | Guillaume Chapuy |
| author_facet | Guillaume Chapuy |
| author_sort | Guillaume Chapuy |
| collection | DOAJ |
| description | 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')$. |
| first_indexed | 2024-04-25T02:03:40Z |
| format | Article |
| id | doaj.art-1dcc12afa4d04d02ab748e6792cbd0b8 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T02:03:40Z |
| publishDate | 2007-01-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-1dcc12afa4d04d02ab748e6792cbd0b82024-03-07T14:34:52ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502007-01-01DMTCS Proceedings vol. AH,...Proceedings10.46298/dmtcs.35343534Random permutations and their discrepancy processGuillaume Chapuy0Laboratoire d'informatique de l'École polytechnique [Palaiseau]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')$.https://dmtcs.episciences.org/3534/pdfweak convergencebivariate brownian bridgerandom permutations[info.info-ds] computer science [cs]/data structures and algorithms [cs.ds][info.info-dm] computer science [cs]/discrete mathematics [cs.dm][math.math-co] mathematics [math]/combinatorics [math.co][info.info-cg] computer science [cs]/computational geometry [cs.cg] |
| spellingShingle | Guillaume Chapuy Random permutations and their discrepancy process Discrete Mathematics & Theoretical Computer Science weak convergence bivariate brownian bridge random permutations [info.info-ds] computer science [cs]/data structures and algorithms [cs.ds] [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] [math.math-co] mathematics [math]/combinatorics [math.co] [info.info-cg] computer science [cs]/computational geometry [cs.cg] |
| title | Random permutations and their discrepancy process |
| title_full | Random permutations and their discrepancy process |
| title_fullStr | Random permutations and their discrepancy process |
| title_full_unstemmed | Random permutations and their discrepancy process |
| title_short | Random permutations and their discrepancy process |
| title_sort | random permutations and their discrepancy process |
| topic | weak convergence bivariate brownian bridge random permutations [info.info-ds] computer science [cs]/data structures and algorithms [cs.ds] [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] [math.math-co] mathematics [math]/combinatorics [math.co] [info.info-cg] computer science [cs]/computational geometry [cs.cg] |
| url | https://dmtcs.episciences.org/3534/pdf |
| work_keys_str_mv | AT guillaumechapuy randompermutationsandtheirdiscrepancyprocess |