Hostname: page-component-7b7567c8c-2rsb6 Total loading time: 0 Render date: 2026-11-12T07:01:11.190Z Has data issue: false hasContentIssue false
  • English
  • Français

Online Selection of Alternating Subsequences from a Random Sample

Part of:Combinatorial probability

Published online by Cambridge University Press:  14 July 2016

Alessandro Arlotto,
Robert W. Chen,
Lawrence A. Shepp and
J. Michael Steele
Alessandro Arlotto*
Affiliation:
University of Pennsylvania
Robert W. Chen*
Affiliation:
University of Miami
Lawrence A. Shepp*
Affiliation:
University of Pennsylvania
J. Michael Steele*
Affiliation:
University of Pennsylvania
*
∗ Postal address: Wharton School, Department of Operations and Information Management, Huntsman Hall 527.2, University of Pennsylvania, Philadelphia, PA 19104, USA. Email address: alear@wharton.upenn.edu
∗∗ Postal address: Department of Mathematics, University of Miami, Coral Gables, FL 33124, USA. Email address: chen@math.miami.edu
∗∗∗ Postal address: Wharton School, Department of Statistics, Huntsman Hall 462, University of Pennsylvania, Philadelphia, PA 19104, USA. Email address: shepp@wharton.upenn.edu
∗∗∗∗ Postal address: Wharton School, Department of Statistics, Huntsman Hall 447, University of Pennsylvania, Philadelphia, PA 19104, USA. Email address: steele@wharton.upenn.edu
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We consider sequential selection of an alternating subsequence from a sequence of independent, identically distributed, continuous random variables, and we determine the exact asymptotic behavior of an optimal sequentially selected subsequence. Moreover, we find (in a sense we make precise) that a person who is constrained to make sequential selections does only about 12 percent worse than a person who can make selections with full knowledge of the random sequence.

Keywords

Bellman equationonline selectionsequential selectionprophet inequalityalternating subsequence

MSC classification

Secondary:60C05: Combinatorial probability90C40: Markov and semi-Markov decision processes90C27: Combinatorial optimization90C39: Dynamic programming

Information

Type
Research Papers
Information
Journal of Applied Probability , Volume 48 , Issue 4 , December 2011, pp. 1114 - 1132
Copyright
Copyright © Applied Probability Trust 2011 

References

Bertsekas, D. P. and Shreve, S. E. (1978). Stochastic Optimal Control (Math. Sci. Eng. 139). Academic Press, New York.Google Scholar
Bruss, F. T. and Delbaen, F. (2001). Optimal rules for the sequential selection of monotone subsequences of maximum expected length. Stoch. Process. Appl. 96, 313–342.Google Scholar
Bruss, F. T. and Delbaen, F. (2004). A central limit theorem for the optimal selection process for monotone subsequences of maximum expected length. Stoch. Process. Appl. 114, 287–311.Google Scholar
Gnedin, A. V. (1999). Sequential selection of an increasing subsequence from a sample of random size. J. Appl. Prob. 36, 1074–1085.Google Scholar
Gnedin, A. V. (2000). Sequential selection of an increasing subsequence from a random sample with geometrically distributed sample-size. In Game Theory, Optimal Stopping, Probability and Statistics (IMS Lecture Notes Monogr. Ser. 35), Institute of Mathematical Statistics, Beachwood, OH, pp. 101–109.Google Scholar
Houdré, C. and Restrepo, R. (2010). A probabilistic approach to the asymptotics of the length of the longest alternating subsequence. Electron. J. Combinatorics 17, 19pp.Google Scholar
Samuels, S. M. and Steele, J. M. (1981). Optimal sequential selection of a monotone sequence from a random sample. Ann. Prob. 9, 937–947.Google Scholar
Stanley, R. P. (2007). Increasing and decreasing subsequences and their variants. In International Congress of Mathematicians, Vol. I, European Mathematical Society, Zürich, pp. 545–579.Google Scholar
Stanley, R. P. (2008). Longest alternating subsequences of permutations. Michigan Math. J. 57, 675–687.Google Scholar
Stanley, R. P. (2010). A survey of alternating permutations. In Combinatorics and Graphs (Contemp. Math. 531), American Mathematical Society, Providence, RI, pp. 165–96.Google Scholar
Widom, H. (2006). On the limiting distribution for the length of the longest alternating sequence in a random permutation. Electron. J. Combinatorics 13, 7pp.Google Scholar