Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: A probabilistic approach to the asymptotics of the length of the longest alternating subsequence. | A probabilistic approach to the asymptotics of the length of the longest alternating subsequence Christian Houdre Ricardo Restrepo Submitted May 10 2010 Accepted Nov 22 2010 Published Dec 10 2010 Mathematics Subject Classification 60C05 60F05 60G15 60G17 05A16 Abstract Let LAn r be the length of the longest alternating subsequence of a uniform random permutation T E n . Classical probabilistic arguments are used to rederive the asymptotic mean variance and limiting law of LAn t . Our methodology is robust enough to tackle similar problems for finite alphabet random words or even Markovian sequences in which case our results are mainly original. A sketch of how some cases of pattern restricted permutations can also be tackled with probabilistic methods is finally presented. Keywords Longest alternating subsequence random permutations random words m-dependence central limit theorem law of the iterated logarithm. 1 Introduction Let a a1 a2 . an be a sequence of length n whose elements belong to a totally ordered set A. Given an increasing set of indices GIRd we say that the subsequence a a 2 . a m is alternating if a 1 a i2 ag3 agm. The length of the longest alternating subsequence is then defined as LAn a max m a has an alternating subsequence of length m . We revisit here the problem of finding the asymptotic behavior in mean variance and limiting law of the length of the longest alternating subsequence in the context of random permutations and random words. For random permutations these problems have seen complete solutions with contributions independently given in alphabetical order by Georgia Institute of Technology School of Mathematics Atlanta Georgia 30332 USA houdre@math.gatech.edu. Supported in part by the NSA grant H98230-09-1-0017. Georgia Institute of Technology School of Mathematics Atlanta Georgia 30332 USA re-strepo@math.gatech.edu. Wniversidad de Antioquia Departamento de Matematicas Medellin Colombia. THE ELECTRONIC JOURNAL OF COMBINATORICS 17 2010 .
