The question When should we expect Tracy-Widom? motivated me to post the following question, in which I have been interested for a while. Let $f(n)$ be a function from the positive integers to themselves. Given a permutation $w=a_1\cdots a_n\in S_n$, let $m=f(n)$ and let $L_f(w)$ be the length $k$ of the longest subsequence $b_1 \cdots b_k$ of $w$ satisfying $$ b_1<b_2<\cdots <b_{m+1}>b_{m+2}>b_{m+3}>\cdots>b_{2m+1}<b_{2m+2}< \cdots <b_{3m+1}>\cdots. $$ If we scale $L_f$ suitably then it should approach a limiting distribution $\Phi(t)$ as $n\to\infty$. For $f(n)=1$ it is known that $\Phi(t)$ is Gaussian. For $f(n)=n$ it is known that $\Phi(t)$ is the Tracy-Widom distribution. See for instance http://math.mit.edu/~rstan/papers/ids.pdf (Theorems 4 and 14). What happens in between these two extremes, e.g., $f(n)=\log n$ or $\sqrt{n}$? Do we always get either a Gaussian or Tracy-Widom distribution? If so, what is the crossover point? If not, what other distributions are possible?
$\begingroup$
$\endgroup$
4
asked Jun 25, 2015 at 4:23
-
$\begingroup$ In the interest of clarity, can you tell us what w is and what w and the a's have to do with L_f(w) ? Also, I am guessing that f(n) > n is an f that plays no role in this problem. Or can it? $\endgroup$– The Masked AvengerCommented Jun 25, 2015 at 5:59
-
$\begingroup$ @TheMaskedAvenger: I have added the fact that $w=a_1\cdots a_n$. The case $f(n)>n$ is equivalent to $f(n)=n$. $\endgroup$– Richard StanleyCommented Jun 25, 2015 at 7:41
-
$\begingroup$ A trivial observation: there's some strange parity here. The Tracy widom distribution is biased toward one side, whereas the Gaussian is symmetric about the mean. This is evident here since for small $m$, we basically have reflection symmetry. So I would expect the transition to occur when $m\gg n/2$. $\endgroup$– Alex R.Commented Jun 25, 2015 at 17:50
-
$\begingroup$ In particle systems or random matrices the phase transition from Gaussian to Tracy-Widom is known, it is given by Baik-Ben Arous-Peche distribution (or maybe in this case GOE Tracy-Widom which is a particular case) $\endgroup$– Leonid PetrovCommented Nov 25, 2016 at 3:04
Add a comment
|