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 \( {\mathbf {x}}=\{x_{1},x_{2},\ldots ,x_{n}\} \) is a sequence of distinct real numbers, then the subsequence \( \{x_{{i_{1}}},x_{{i_{2}}},\ldots ,x_{{i_{k}}}\} \) is alternating[1] (or zigzag or down-up)if
\( 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, \( \mathbf {x} \) is reverse alternating (or up-down) if
\( 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. \)
Let \( {{\rm {as}}}_{n}({\mathbf {x}}) \) denote the length (number of terms) of the longest alternating subsequence of \( \mathbf {x} \) . For example, if we consider some of the permutations of the integers 1,2,3,4,5, we have that
\( {{\rm {as}}}_{5}(1,2,3,4,5)=2; \) because any sequence of 2 distinct digits are (by definition) alternating. (for example 1,2 or 1,4 or 3,5)
\( {{\rm {as}}}_{5}(1,5,3,2,4)=4, \) because 1,5,3,4 and 1,5,2,4 and 1,3,2,4 are all alternating, and there is no alternating subsequence with more elements;
\( {{\rm {as}}}_{5}(5,3,4,1,2)=5, \) because 5,3,4,1,2 is itself alternating.
Efficient algorithms
The longest alternating subsequence problem is solvable in time } O(n), where n is the length of the original sequence.[citation needed]
Distributional results
If \( \mathbf {x} \) is a random permutation of the integers \( 1,2,\ldots ,n \) and \( A_{n}\equiv {{\rm {as}}}_{n}({\mathbf {x}}) \), then it is possible to show[2][3][4] that
\( 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 \( n\rightarrow \infty \), the random variable \( 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 x {\displaystyle \mathbf {x} } \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 \( X_{1},X_{2},\ldots ,X_{n} \) of independent random variables with common continuous distribution F {\displaystyle F} 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\( (2-{\sqrt {2}})n+O(1) \).[5]
As \( n\rightarrow \infty \), the optimal number of online alternating selections appropriately centered and scaled converges to a normal distribution.[6]
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 n {\displaystyle n} n observations
Number of alternating runs
Longest increasing subsequence
Longest common subsequence problem
References
Stanley, Richard P. (2011), Enumerative Combinatorics, Volume I, second edition, Cambridge University Press
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
Stanley, Richard P. (2008), "Longest alternating subsequences of permutations", Michigan Math. J., 57: 675–687, arXiv:math/0511419, doi:10.1307/mmj/1220879431
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
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
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
Undergraduate Texts in Mathematics
Graduate Studies in Mathematics
Hellenica World - Scientific Library
Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License
