Hostname: page-component-cd9895bd7-7cvxr Total loading time: 0 Render date: 2024-12-23T22:56:52.729Z 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: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

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.

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

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)