A Generalized Cover's Problem

Abstract

Generalizing a problem posed by Cover, we propose an adversarial game in which a permutation is incrementally constructed in a setting of partial information. As in the secretary problem, this permutation is exposed in stages via the successive components of its Lehmer code. Extending Cover's result, which constitutes the case $n=2$, we establish that a random permutation of $n$ adversarially constructed real numbers can be reconstructed with better-than-random probability, provided that certain among the numbers it permutes are made visible during the process.

9 pages