Increasing subsequences of random walks
2017
From a given sequence of numbers (Si) of length n, we consider the longest weakly increasing subsequence, namely i1 < i2 < < im with Sik Sik+1 and m maximal. The Erd} os-Szekeres Theorem states that there is either a weakly increasing or a weakly decreasing subsequence of length p n. When the elements Si are i.i.d. uniform random variables, Vershik and Kerov, and Logan and Shepp proved that with high probability the longest increasing sequence has length
- Correction
- Cite
- Save
- Machine Reading By IdeaReader
11
References
0
Citations
NaN
KQI