Raw data: A cautionary tale
7 hours ago
Tuesday, August 10, 2010
Alternating sequences
Last week I heard a talk by Richard Stanley in which he mentioned a version of the following problem. Define an alternating sequence as one in which the differences between adjacent elements are alternatively positive and negative. So 1,2,3 and 3,2,1 are not alternating sequences but 1,4,2,5,3,6 is. Consider random permutations of 1,2,...,n. We ask as n goes to infinity what is the expected length of the longest alternating subsequence? Note the elements of a subsequence do not have to be adjacent in the original sequence. You can think of a subsequence as what is left after you delete some elements of a sequence.
Subscribe to:
Post Comments (Atom)
No alternating subsequence is longer than the "extremal subsequence" consisting of the ends of the sequence together with its extrema, where an extremum is an element that is either greater than both immediately adjacent elements or less than both. If n <= 2, then the entire sequence is the extremal subsequence, which is of length L(n) = n. If n >= 2, then L(n) satisfies the recurrence L(2) = 2 and L(n+1) = L(n) + 2/3. The latter can be shown by appending one more element to one end of a sequence of n elements; a new extremum appears with probability 2/3 at the position of the original end. The solution to the recurrence is L(n) = 2*(n+1)/3. QED
ReplyDeleteYes, this is correct. You don't actually need to use induction. It is pretty clear that an interior element is an extremum with probability 2/3. Since any of 3 adjacent elements is equally likely to be the middle (in magnitude) and the center element is an extremum unless it is the middle (in magnitude). So the expected number of interior extrema is (2/3)*(n-2). Add 2 for the ends and the result follows.
ReplyDeleteIn the brief time before digesting the answer I managed to have two different misinterpretations of the puzzle. I doubt these are mathematically interesting, but will list them here on the off chance that they are-
ReplyDelete1) Change 'subsequence' to 'contiguous subsequence'
2) Change 'subsequence' to 'equally-spaced subsequence'