  For many online problems, it is known that the uniform arrival order enables
the design of algorithms with much better performance guarantees than under
worst-case. The quintessential example is the secretary problem. If the
sequence of elements is presented in uniformly random order there is an
algorithm that picks the maximum value with probability 1/e, whereas no
non-trivial performance guarantee is possible if the elements arrive in
worst-case order. This work initiates an investigation into relaxations of the
random-ordering hypothesis in online algorithms, by focusing on the secretary
problems. We present two sets of properties of distributions over permutations
as sufficient conditions, called the block-independence property and
uniform-induced-ordering property. We show these two are asymptotically
equivalent by borrowing some techniques from the approximation theory.
Moreover, we show they both imply the existence of secretary algorithms with
constant probability of correct selection, approaching the optimal constant 1/e
in the limit. We substantiate our idea by providing several constructions of
distributions that satisfy block-independence. We also show that {\Theta}(log
log n) is the minimum entropy of any permutation distribution that permits
constant probability of correct selection in the secretary problem with n
elements. While our block-independence condition is sufficient for constant
probability of correct selection, it is not necessary; however, we present
complexity-theoretic evidence that no simple necessary and sufficient criterion
exists. Finally, we explore the extent to which the performance guarantees of
other algorithms are preserved when one relaxes the uniform random ordering
assumption, obtaining a positive result for Kleinberg's multiple-choice
secretary algorithm and a negative result for the weighted bipartite matching
algorithm of Korula and Pal.
