About the Moments of the Generalized Ulam Problem
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913848263442432 |
|---|---|
| author | Hossein, Samen Starr, Shannon |
| author_facet | Hossein, Samen Starr, Shannon |
| contents | Given $π\in S_n$, let $Z_{n,k}(π)=\sum_{1\leq i_1<\dots<i_k\leq n} \mathbf{1}(\{ π_{i_1}<\dots<π_{i_k}\}$ denote the number of increasing subsequences of length $k$. Consider the "generalized Ulam problem," studying the distribution of $Z_{n,k}$ for general $k$ and $n$. For the 2nd moment, Ross Pinsky initiated a combinatorial study by considering a pair of subsequences $i^{(r)}_1<\dots<i^{(r)}_k$ for $r \in \{1,2\}$, and conditioning on the size of the intersection $j = |\{i_1^{(1)},\dots,i^{(1)}_k\} \cap \{i^{(2)}_1,\dots,i^{(2)}_k\}|$. We obtain the exact large deviation rate function for $\mathbf{E}[Z_{n,k} Z_{n,\ell}]$ in the asymptotic regime $k\sim κn^{1/2}$, $\ell \sim λn^{1/2}$ as $n \to \infty$, for $κ,λ\in (0,\infty)$. This uses multivariate generating function techniques, as found in the textbook of Pemantle and Wilson. The requisite generating function enumerates pairs of up-right paths in $d=2$, which both end at $(k,\ell)$ with a given number of intersections. We also evaluate the analogous generating function for pairs of $(+\boldsymbol{i},+\boldsymbol{j},+\boldsymbol{k})$ paths in $d=3$, which both end at $(k,\ell,m)$, which has some utility in calculating the 3rd moment. Finally, we consider a simpler problem involving partitions instead of permutations, where all moments are calculable and the replica symmetric ansatz can be stated if not proved. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_05860 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | About the Moments of the Generalized Ulam Problem Hossein, Samen Starr, Shannon Combinatorics Mathematical Physics Probability 60F10, 05A15, 82D30 Given $π\in S_n$, let $Z_{n,k}(π)=\sum_{1\leq i_1<\dots<i_k\leq n} \mathbf{1}(\{ π_{i_1}<\dots<π_{i_k}\}$ denote the number of increasing subsequences of length $k$. Consider the "generalized Ulam problem," studying the distribution of $Z_{n,k}$ for general $k$ and $n$. For the 2nd moment, Ross Pinsky initiated a combinatorial study by considering a pair of subsequences $i^{(r)}_1<\dots<i^{(r)}_k$ for $r \in \{1,2\}$, and conditioning on the size of the intersection $j = |\{i_1^{(1)},\dots,i^{(1)}_k\} \cap \{i^{(2)}_1,\dots,i^{(2)}_k\}|$. We obtain the exact large deviation rate function for $\mathbf{E}[Z_{n,k} Z_{n,\ell}]$ in the asymptotic regime $k\sim κn^{1/2}$, $\ell \sim λn^{1/2}$ as $n \to \infty$, for $κ,λ\in (0,\infty)$. This uses multivariate generating function techniques, as found in the textbook of Pemantle and Wilson. The requisite generating function enumerates pairs of up-right paths in $d=2$, which both end at $(k,\ell)$ with a given number of intersections. We also evaluate the analogous generating function for pairs of $(+\boldsymbol{i},+\boldsymbol{j},+\boldsymbol{k})$ paths in $d=3$, which both end at $(k,\ell,m)$, which has some utility in calculating the 3rd moment. Finally, we consider a simpler problem involving partitions instead of permutations, where all moments are calculable and the replica symmetric ansatz can be stated if not proved. |
| title | About the Moments of the Generalized Ulam Problem |
| topic | Combinatorics Mathematical Physics Probability 60F10, 05A15, 82D30 |
| url | https://arxiv.org/abs/2404.05860 |