In the secretary problem we are faced with an online sequence of
elements with values. Upon seeing an element we have to make an
irrevocable take-it-or-leave-it decision. The goal is to
maximize the probability of picking the element of maximum
value. The most classic version of the problem is that in
which the elements arrive in random order and their values are
arbitrary. However, by varying the available information, new
interesting problems arise. Also the case in which the
arrival order is adversarial instead of random leads to
interesting variants that have been considered in the
literature.

In this paper we study both the random order and adversarial
order secretary problems with an additional twist. The values
are arbitrary, but before starting the online sequence we
sample each element with a fixed probability p. The sampled
elements become our information or history set and the game is
played over the remaining elements. We call these problems the
random order secretary problem with p-sampling (ROSp for short)
and the adversarial order secretary problem with p-sampling
(AOSp for short). Our main result is to obtain best possible
algorithms for both problems and all values of p. As p grows
to 1 the obtained guarantees converge to the optimal
guarantees in the full information case. In the adversarial
order setting, the best possible algorithm turns out to be a
simple fixed threshold algorithm in which the optimal
threshold is a function of p only. In the random order setting
we prove that the best possible algorithm is characterized
by a fixed sequence of time thresholds, dictating at which
point in time we should start accepting a value that is both
a maximum of the online sequence and has a given ranking
within the sampled elements.