Longest alternating subsequence

In combinatorial mathematics, probability, and computer science, in the longest alternating subsequence problem, one wants to find a subsequence of a given sequence in which the elements are in alternating order, and in which the sequence is as long as possible.

Formally, if ${\displaystyle \mathbf {x} =\{x_{1},x_{2},\ldots ,x_{n}\}}$ is a sequence of distinct real numbers, then the subsequence ${\displaystyle \{x_{i_{1}},x_{i_{2}},\ldots ,x_{i_{k}}\}}$ is alternating ^[1] (or zigzag or down-up) if

${\displaystyle x_{i_{1}}>x_{i_{2}}<x_{i_{3}}>\cdots x_{i_{k}}\qquad {\text{and}}\qquad 1\leq i_{1}<i_{2}<\cdots <i_{k}\leq n.}$

Similarly, ${\displaystyle \mathbf {x} }$ is reverse alternating (or up-down) if

${\displaystyle x_{i_{1}}<x_{i_{2}}>x_{i_{3}}<\cdots x_{i_{k}}\qquad {\text{and}}\qquad 1\leq i_{1}<i_{2}<\cdots <i_{k}\leq n.}$

Note that every sequence of length 1 is both alternating and reverse alternating.

Let ${\displaystyle {\rm {as}}_{n}(\mathbf {x} )}$ denote the length (number of terms) of the longest alternating subsequence of ${\displaystyle \mathbf {x} }$. For example, if we consider some of the permutations of the integers 1,2,3,4,5, we have that

• ${\displaystyle {\rm {as}}_{5}(5,4,3,2,1)=2}$, because there are alternating subsequences of length 2, (for example 5,4 or 5,2 or 3,1), but all subsequences of length 3 are not alternating;
• ${\displaystyle {\rm {as}}_{5}(1,2,3,4,5)=1}$, because all subsequences of length 2 are not alternating. (actually, they are reverse alternating);
• ${\displaystyle {\rm {as}}_{5}(5,1,3,4,2)=4,}$ because 5,1,3,2 and 5,1,4,2 and 5,3,4,2 are all alternating, and there is no alternating subsequence with more elements;
• ${\displaystyle {\rm {as}}_{5}(4,3,5,1,2)=5,}$ because 4,3,5,1,2 is itself alternating.

Efficient algorithms

In a sequence of distinct elements, the subsequence of local extrema (elements larger than both adjacent elements, or smaller than both adjacent elements) forms a canonical longest alternating sequence. ^[2] As a consequence, the longest alternating subsequence of a sequence of ${\displaystyle n}$ elements can be found in time ${\displaystyle O(n)}$. In sequences that allow repetitions, the same method can be applied after first replacing each run of repeated elements by a single copy of that element.^{[ citation needed ]}

Distributional results

If ${\displaystyle \mathbf {x} }$ is a random permutation of the integers ${\displaystyle 1,2,\ldots ,n}$ and ${\displaystyle A_{n}\equiv {\rm {as}}_{n}(\mathbf {x} )}$, then it is possible to show ^{[3] [4] [5]} that

${\displaystyle E[A_{n}]={\frac {2n}{3}}+{\frac {1}{6}}\qquad {\text{and}}\qquad \operatorname {Var} [A_{n}]={\frac {8n}{45}}-{\frac {13}{180}}.}$

Moreover, as ${\displaystyle n\rightarrow \infty }$, the random variable ${\displaystyle A_{n}}$, appropriately centered and scaled, converges to a standard normal distribution.

Online algorithms

The longest alternating subsequence problem has also been studied in the setting of online algorithms, in which the elements of ${\displaystyle \mathbf {x} }$ are presented in an online fashion, and a decision maker needs to decide whether to include or exclude each element at the time it is first presented, without any knowledge of the elements that will be presented in the future, and without the possibility of recalling on preceding observations.

Given a sequence ${\displaystyle X_{1},X_{2},\ldots ,X_{n}}$ of independent random variables with common continuous distribution ${\displaystyle F}$, it is possible to construct a selection procedure that maximizes the expected number of alternating selections. Such expected values can be tightly estimated, and it equals ${\displaystyle (2-{\sqrt {2}})n+O(1)}$. ^[6]

As ${\displaystyle n\rightarrow \infty }$, the optimal number of online alternating selections appropriately centered and scaled converges to a normal distribution. ^[7]

See also

• Alternating permutation
• Permutation pattern and pattern avoidance
• Counting local maxima and/or local minima in a given sequence
• Turning point tests for testing statistical independence of ${\displaystyle n}$ observations
• Number of alternating runs
• Longest increasing subsequence
• Longest common subsequence

References

1. Stanley, Richard P. (2011), Enumerative Combinatorics, Volume I, second edition, Cambridge University Press
2. Romik, Dan (2011), "Local extrema in random permutations and the structure of longest alternating subsequences", 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), Discrete Math. Theor. Comput. Sci. Proc., vol. AO, Assoc. Discrete Math. Theor. Comput. Sci., Nancy, pp. 825–834, MR   2820763
3. Widom, Harold (2006), "On the limiting distribution for the length of the longest alternating sequence in a random permutation", Electron. J. Combin., 13: Research Paper 25, 7, doi: 10.37236/1051
4. Stanley, Richard P. (2008), "Longest alternating subsequences of permutations", Michigan Math. J., 57: 675–687, arXiv: math/0511419 , doi:10.1307/mmj/1220879431
5. Houdré, Christian; Restrepo, Ricardo (2010), "A probabilistic approach to the asymptotics of the length of the longest alternating subsequence", Electron. J. Combin., 17: Research Paper 168, 19, arXiv: 1005.1893 , doi:10.37236/440
6. Arlotto, Alessandro; Chen, Robert W.; Shepp, Lawrence A.; Steele, J. Michael (2011), "Online selection of alternating subsequences from a random sample", J. Appl. Probab., 48 (4): 1114–1132, arXiv: 1105.1558 , doi:10.1239/jap/1324046022
7. Arlotto, Alessandro; Steele, J. Michael (2014), "Optimal online selection of an alternating subsequence: a central limit theorem", Adv. Appl. Probab., 46 (2): 536–559, doi: 10.1239/aap/1401369706