Hostname: page-component-74656f9884-kv2lp Total loading time: 0 Render date: 2026-11-06T09:33:50.696Z Has data issue: false hasContentIssue false
  • English
  • Français

A Note on Sequential Selection from Permutations

Published online by Cambridge University Press:  01 January 2000

ALEXANDER V. GNEDIN
ALEXANDER V. GNEDIN
Affiliation:
Institute of Mathematical Stochastics, University of Göttingen, Lotzestrasse 13, 37083 Göttingen, Germany (e-mail: gnedin@math.uni-goettingen.de)
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.

The maximum expected length of an increasing subsequence which can be selected by a non-anticipating policy from a random permutation of 1, …, n is known to be asymptotic to √2n. We give a new proof of this fact and demonstrate a policy which achieves this value.

Information

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 9 , Issue 1 , January 2000 , pp. 13 - 17
Copyright
2000 Cambridge University Press