The principal investigator will study the random permutations of {1, 2, ....,n}. During the planning period, she proposes to: 1) Look for closed form expressions for lower moment of Xn(k) and bounds for more difficult higher moments. 2) Do computer intensive simulation studies which will give empirical descriptions of distributional shape and properties of Xn(k). 3) Develop algorithms for the study of Xn(k) which fall within the framework of (2) above. 4) Develop theoretical approaches to find an asymptotic distributions for Xn(k). In the context of the above objectives, the principal investigator will consider the following scheme: a) select a permutation at random (for n fixed) b) consider all the increasing subsequences in this permutation c) select an increasing subsequence, say 1n, at random. Let k be the length, i.e. k = ?1n!. d) What is the distribution of k?
