Weighted games of best choice
Brant Jones





The game of best choice (also known as the secretary problem) is a model for sequential decision making with a long history and many variations.  The classical setup assumes that the sequence of candidate rankings are uniformly distributed.  Given a statistic on the symmetric group, one can instead weight each permutation according to an exponential function in the statistic.  We play the game of best choice on the Ewens and Mallows distributions that are obtained in this way from the number of left-to-right maxima and number of inversions in the permutation, respectively.  For each of these, we give the optimal strategy and probability of winning.  Moreover, we introduce a general class of permutation statistics that always produces games of best choice whose optimal strategies are positional, which simplifies their analysis considerably.



Department of Mathematics and Statistics, MSC 1911, James Madison University, Harrisonburg, VA 22807
mailto:jones3bc@jmu.edu
<http://educ.jmu.edu/j̃ones3bc/>





Weighted games of best choice
    Brant Jones
    December 30, 2023
=============================








§ INTRODUCTION


The game of best choice (or secretary problem) is a model for sequential
decision making, popularized in a Scientific American column of Martin Gardner
reprinted in <cit.>.  In the simplest variant, an interviewer evaluates N
candidates one by one.  After each interview, the interviewer ranks the
current candidate against all of the candidates interviewed so far, and decides
whether to accept the current candidate (ending the game) or to
reject the current candidate (in which case, they cannot be recalled
later).  The goal of the game is to hire the best candidate out of N.  It
turns out that the optimal strategy is to reject an initial set of candidates,
of size N/e when N is large, and use them as a training set by hiring the
next candidate who is better than all of them (or the last candidate if no
subsequent candidate is better).  The probability of hiring the best candidate
out of N with this strategy approaches 1/e.  This result has been
generalized in several directions by <cit.>; see also
<cit.> and <cit.> for historical surveys.  Recently,
researchers (e.g. <cit.>) have begun applying the best-choice
framework to online auctions where the “candidate rankings” are bids (that may
arrive and expire at different times) and the player must choose which bid to
accept, ending the auction.  

Most models assume that all N! interview rank orders are equally
likely, which we believe is mathematically expedient but unrealistic.  There
may exist extrinsic trends in the candidate pool due to changes in general
economic conditions over the period that the player is conducting the N
interviews.  Also, as the interviewer compares and ranks the candidates at each
step, they are forced to find distinctions that may simultaneously be used to
hone the pool by filtering out irrelevant candidates.  Overall, this intrinsic
learning about the candidate pool would tend to result in candidate ranks that are
improving over time rather than uniform.

Towards understanding such mechanisms, we are interested in how assumptions
about the distribution of interview rank orders change the optimal strategy and
probability of success in the game of best choice.  While many authors have
investigated a “full-information” version of the game in which the interviewer
observes values from a known distribution, only a few papers from the literature
(e.g.  <cit.>) have previously considered such nonuniform
rank distributions for the secretary problem.  Continuing work from
<cit.> and <cit.>, we establish in this paper a class of
weighted models that generalize the classical game in a natural way.

We model interview orderings as permutations.  The permutation π of
N is expressed in one-line notation as [π_1 π_2 ⋯π_N]
where the π_i consist of the elements 1, 2, …, N (so each element
appears exactly once).  In the best choice game, π_i is the rank of the
ith candidate interviewed in reality, where rank N is best and 1 is
worst.  What the interviewer sees at each step, however, are relative rankings.
For example, corresponding to the interview order π = [2516374], the interviewer
sees the sequence of permutations 1, 12, 231, 2314, 24153, 241536, 2516374
and must use only this information to determine when to accept a candidate,
ending the game.  The left-to-right maxima of π consist of the
elements π_j that are larger in value than all elements π_i lying to the
left.  It is never optimal to accept a candidate that is not a left-to-right
maximum because N is always a left-to-right maximum in any
permutation.  The inversions of π consist of pairs π_i > π_j where i <
j.

Now, let c: _N → be some statistic on the symmetric group of
permutations of size N.  Then we can weight the permutation π∈_N by
^c(π), where  is a positive real number, to obtain a discrete
probability distribution on _N.  Distributions of this form were introduced
by Mallows where c(π) represents some measure of distance from a fixed
permutation, typically the identity.  More recently, these distributions have
been used by researchers in combinatorics; see <cit.>
for example.  

The weighted game of best choice selects a permutation π∈_N
with probability proportional to ^c(π) and then proceeds just as in the
classical model:  relative rankings are presented to the interviewer
sequentially and the game is won if the best candidate is accepted.  When =
1, we recover the uniform distribution so our model includes the classical game
as a specialization.  Also, we remark that for a given statistic, c(π), the
probability of winning the weighted game of best choice under the non-uniform
distribution we defined is the same (up to rescaling by a constant involving
 and N) as the expected value of a random variable representing the
non-uniform payoff ^c(π) for the classical game played on a uniform
distribution.  So the weight can be interpreted as determining the underlying
probability distribution (with uniform payoff) or as determining a payoff (with
uniform probability).

In our first result, Theorem <ref>, we show that for a large class of
statistics the optimal strategy in the weighted game of best choice has the same
form as that for the classical game:  to reject an initial set of candidates and
accept the next left-to-right maximum thereafter.  We refer to this as a positional strategy because the strategy accepts or rejects a candidate (that
is a left-to-right maximum) based solely on its position, even though the full
history of relative rankings containing more refined information is available.  

Next, we present an analysis of the weighted game of best choice for two
specific statistics.  The first model uses the Ewens distribution where c(π)
is the number of left-to-right maxima in π.  Setting > 1 is a concise
way of obtaining candidate ranks that tend to be improving over time, consistent
with intrinsic learning.  The second model is based on what has become known as
the Mallows distribution where c(π) is the number of inversions in π.
Setting < 1 dampens the probability of (or imposes a cost for) experiencing
“disappointing pairs,” where an earlier candidate ranks higher than a later
candidate.  In terms of permutation patterns, the Mallows model weights each
permutation π by the number of 21-instances in π, which facilitates
comparison with results in <cit.> and <cit.> for the
321-avoiding model.  

Once we know by Theorem <ref> that some positional strategy is optimal
for each value of θ, we can define the strategy function
_̨N(θ): ℝ_>0→{0, 1, ⋯, N-1} for a weighted
game of best choice to be the number of candidates that we initially reject in
the optimal strategy for value θ.  In Corollary <ref>, we
describe this function precisely for the Ewens model.  As N becomes large, we
find that the optimal strategy depends on  with the optimal number of
initial rejections being k = N/e^1/.  Remarkably though, the probability
of success is always 1/e, independent of , neither better nor worse than
the classical case.

The Mallows model is more subtle.  When < 1 and N →∞, the
optimal strategy is to reject all but the last j = max(-1/(ln), 1)
candidates and select the next left-to-right maximum thereafter.  This
“right-justified” strategy succeeds with probability j ^j-1 (1-).
When > 1, the optimal strategy is “left-justified,” rejecting the first
k candidates for some k depending on  but independent of N.
Consequently, this shows that the classical model (as embedded in the Mallows
model) is highly unstable!  Even an infinitesimal change away from = 1,
where the asymptotic optimal strategy rejects about 37% of the candidates,
results in an optimal strategy that asymptotically rejects either 0% or
100% of the candidates.  This shows that “policy advice” derived from the
classical model (e.g. <cit.>) has limited durability, a point which does
not seem to have been appreciated in popular accounts of the secretary problem.
In the future, it would be interesting to find (or better understand
obstructions to) best choice models where the asymptotic optimal strategy varies
continuously with parameterizations of the underlying distribution.

We now outline the rest of the paper.  In Section <ref> we review the
form of the optimal strategy for games of best choice, and show in
Section <ref> that any sufficiently local statistic will generate a game
with an optimal strategy having the same form as the classical model.  In
Sections <ref> and <ref>, we obtain precise and asymptotic results
for the Ewens model.  The Mallows model is treated in Section <ref>.






§ STRATEGIES FOR THE WEIGHTED GAME OF BEST CHOICE


In this section, we give precise notation for the various strategies that can be
employed in the weighted game of best choice, and compute their probabilities of
winning.

Fix a discrete probability distribution on the symmetric group _N where
f(π) is the probability of the permutation π ∈ _N.  
In this work, we are primarily interested in probability distributions obtained
from weighting by some statistic c : _N → and a
positive real number θ via

    f(π) = θ^c(π)/∑_π∈_Nθ^c(π).

For example, we may take c(π) to be the number of left-to-right maxima in
π, obtaining the Ewens distribution; if c(π) is the number of
inversions then we obtain the Mallows distribution.
When θ = 1, we recover the complete uniform distribution.


Given a permutation π, define the ith prefix flattening, denoted
i, to be the unique permutation in _i having the same relative order
as the sequence of entries π_1, π_2, …, π_i.  For brevity, we also
refer to these permutations as prefixes of π.


The set of all possible prefixes from ⋃_i=1^N _i are partially
ordered by containment, where a permutation of smaller size occurs as the
prefix flattening of a permutation of larger size.  At the start of the game,
some π is chosen randomly with probability f(π).  During each move, the
ith prefix flattening of π is presented to the interviewer, and they must
use only this information to determine whether to accept or reject candidate
i.  Therefore, we can represent any strategy (including the optimal strategy)
as a complete list of the prefixes that will immediately trigger an acceptance
by the interviewer.  We refer to such a list as a strike set.  If, during
the game, a prefix flattening from π does not appear in the strike set then
the current candidate is rejected and the game continues.



Since the set of prefixes represent all possible positions in the
game, and cover relations in the containment partial order represent “reject”
moves by the interviewer, we can view this structure as a combinatorial game
tree that we refer to as prefix tree.  See Figure <ref> for a
small example.  The prefix tree can be solved to obtain the optimal strategy
via backwards induction as we will see below.


Given p ∈⋃_i=1^N _i, we say that π∈_N is p-prefixed if one of its prefix flattenings is p.  We say π∈_N is p-winnable if accepting the prefix flattening p would win
the game with interview order π.  Explicitly for p = p_1 p_2 ⋯ p_k, we have
that π is p-winnable if π is p-prefixed and π_k = N.  
For each prefix p, we define the strike probability (p) to be 

    𝖯[ win the game π under the strategy “accept prefix p” | π is p-prefixed ],

i.e. the probability of winning the game if the strike set contained p (and no other
prefixes of p) and we restricted the game to those interview rank orders π
having p as a prefix.  


Since each denominator of f(π) is just a normalizing constant, we may cancel
it obtaining the formula

    (p) = ( ∑_p-winnable π∈_Nθ^c(π))/( ∑_p-prefixed π∈_Nθ^c(π)).



We say that a prefix p is eligible if it ends in a left-to-right maximum or has size N.
A strike set is valid if it 


  * consists of prefixes that are eligible, and 

  * has no pair of elements such that one contains the other as a prefix, and 

  * every permutation in _N contains some element of the strike set as a prefix.


In Figure <ref> we have illustrated the prefix tree with ineligible
prefixes shown in gray and strike probabilities given below each eligible
prefix.  It follows immediately from the definitions that any strategy for the
weighted game of best choice can be represented by a valid strike set.  

Finally, we determine the optimal strategy in the form of a strike set.


Let ^(̧p) be the open probability of a win if we play optimally,
using any strike set consisting of prefixes that contain (but are not equal to)
p.  Similarly, let (p) be the closed probability of a win if
we play optimally, using any strike set consisting of prefixes that contain (and
may include) p.  That is,

    ^(̧p) = 𝖯[ win the game π under the best strategy available after rejecting p | π is p-prefixed ],


    (p) = 𝖯[ 4inwin the game π under the best strategy available after rejecting the largest proper prefix of p | π is p-prefixed],

We define each of these to be conditional probabilities,
restricting to those interview orders π having p as a prefix, with standard denominator ∑_p-prefixed π∈_Nθ^c(π).  


Then, it follows directly from the definitions that

    (p) = max((p), ^(̧p)).

This formula can be used to recursively determine (1), the globally
optimal probability of a win.  To also keep track of the optimal strategy, let
us say that a prefix p is positive if (p) ≥^(̧p) and negative otherwise.  


Suppose N = 4 as illustrated in Figure <ref> and θ = 1.  Consider the prefix p = 123, so the first three candidates have increasing ranks.  The best we can do after rejecting them is to accept the last candidate.  This succeeds in winning the game with probability ^(̧123) = 1/4.  If, by contrast, we were also allowed to accept the third candidate, then we should do so as our probability of winning becomes (123) = 3/4.



With the setup given above, a globally optimal strike set for a weighted game of
best choice consists of the subset A of positive prefixes that are minimal when
partially ordered by prefix-containment.  The probability of winning is 
⊕_p ∈ A(p) where we define a/b⊕c/d =
a+c/b+d and use the standard denominator for all strike probabilities.


We first explain how to determine all of the strike probabilities in the prefix
tree using the formulas.  The prefixes of size N are positive, which serves
as a base case for induction on the size of a prefix.  Given the probabilities
for prefixes of sizes greater than i, the ^(̧p) probabilities for each
prefix of size i can be obtained as ⊕_p-prefixed  q 
of size i+1(q), and then the (p) probabilities can be
determined from the max formula.  (The ⊕ operation represents the
probability of winning on a disjoint union of sample spaces.)  This process is
essentially a combinatorial version of “backwards induction.”

The positive prefixes p are locally optimal (for the collection of p-prefixed
π∈_N) by definition.  If a prefix p has no proper prefix flattenings
that are positive, then p must be part of the globally optimal strike set as well.



Consider the tree shown in Figure <ref> for N = 4 at = 1.  The
strike probabilities (p) are illustrated in the figure.  Since (123) =
3/4 ≥ 1/4 = ^(̧123), we have that 123 is a positive prefix.
Similarly, (12) = 6/12 ≥ 5/12 = ^(̧12) so 12 is also a positive
prefix.  On the other hand, (1) = 6/24 < 11/24 = ^(̧1) so 1 is a
negative prefix.  The optimal strike set consists of 12 (contributing
6/12), 213 (contributing 3/4), 3124 (contributing 1/1), and 3214
(contributing 1/1), together with the six prefixes of size 4 that aren't
already related to one of these, each contributing a strike probability of
0/1.  The optimal probability is the ⊕-sum of these contributions,
namely 11/24.








§ PREFIX EQUIVARIANCE AND POSITIONAL STRATEGIES


While any game of best choice has an optimal strike strategy, the classical game
(where f(π) = 1/N! uniformly) is optimized by a positional strategy in which
the player rejects the first k candidates and accepts the next left-to-right
maximum thereafter.  In this section, we give a concrete explanation for this
and generalize it to a class of weighted games.  The key idea is to use a
fundamental bijection in order to transport structure around the prefix tree.  


Let ^(̧p) be the open
subforest of prefixes containing (but not equal to) p, and let (p) be the
closed subtree of prefixes containing p, including p itself.  



Suppose that p = [12 ⋯ k] and let σ_q be the permutation action that
rearranges the prefix p to give some other prefix q of size k.  We can
extend this to an action on (p), denoted σ_q ·π, by
similarly permuting the first k entries and fixing the last m-k entries of
π, where m is the size of π∈(p).  Then σ_q is a
bijection from (p) to (q).



Suppose that the statistic c satisfies c(π) - c(σ_q ·π) = c(12
⋯ k) - c(q) for all prefixes q and all π∈(12 ⋯
k).  Here, k is the size of q.  Then, we say that c is a prefix
equivariant statistic.


This condition essentially says that the change in the statistic c(π) that
results from permuting the first k entries of π is the same as the change
that would result if we restricted c to k entries.  That is, the action of
permuting a prefix does not create or destroy any structure being counted by
c, beyond the entries of the prefix.  Hence, statistics that count
sufficiently local phenomena in permutations will be prefix equivariant.


It is straightforward to check that c(π) = # left-to-right maxima in π
and c(π) = # inversions in π are each prefix equivariant statistics.
Explicitly, if π = π_1 π_2 ⋯π_k | π_k+1π_k+2⋯π_m has the form of an increasing block of size k followed by an arbitrary
block, then we may observe that rearranging the first block may change the
number of left-to-right maxima within that block, but it cannot change the
left-to-right maximal status of any entry in the second block.  Similarly,
rearranging the first block may change the number of inversions within that
block, but it cannot add or remove an inversion pair where the smaller entry
lies in the second block.  On the other hand, c(π) = #321-instances in
π (i.e. triples of entries that are decreasing) is not prefix equivariant
because, for example, c(2468|1357) = 0 yet c(4268|1357) = 1 even though
c(2468) = 0 = c(4268).


The following results are illustrated in Figure <ref>.


Suppose c(π) is a prefix equivariant statistic.
For all prefixes q, the strike probabilities are
preserved under the restricted bijection σ_q: ^(̧12 ⋯ k)
→^(̧q), where k is the size of q.  If q is eligible then
these probabilities are also preserved under σ_q: (12 ⋯
k) →(q).

Consequently, for p ∈^(̧12 ⋯ k) (and additionally for p = [12 ⋯ k] if q is
eligible), we have that

    
  * the ^(̧p) probabilities are preserved by σ_q, and
    
  * the (p) probabilities are preserved by σ_q, and
    
  * if p and q are eligible, we have p is positive if and only if σ_q · p is positive.



Fix q to be any prefix of size k, and let p ∈(12 ⋯ k) with size m.  Then, 
(p) = ∑_p-winnable π∈_Nθ^c(π)/∑_p-prefixed π∈_Nθ^c(π).
Since the weights satisfy c(π) - c(σ_q ·π) = c(12 ⋯ k) -
c(q) for all π∈(12 ⋯ k), we have 

    (σ_q · p) = ∑_(σ_q · p)-winnable π∈_Nθ^c(π)/∑_(σ_q · p)-prefixed π∈_Nθ^c(π) = ∑_p-winnable π∈_Nθ^c(σ_q ·π)/∑_p-prefixed π∈_Nθ^c(σ_q ·π)

which is θ^c(q) - c(12 ⋯ k)/θ^c(q) - c(12 ⋯
k) S(p) unless q happens to be ineligible and p = [12 ⋯ k] in which case
σ_q · p = q and so (q) = 0.

The probability ^(̧p) is an ⊕-sum of strike probabilities, say
^(̧p) = (r_1) ⊕(r_2) ⊕⋯⊕(r_n),
for some prefixes r_i ∈⋃_j = m+1^N _j.
Then, 

    ^(̧σ_q · p) = (σ_q · r_1) ⊕(σ_q ·
    r_2) ⊕⋯⊕(σ_q · r_n)


    = θ^c(q) - c(12 ⋯ k)/θ^c(q) - c(12 ⋯
    k)(r_1) ⊕θ^c(q) - c(12 ⋯ k)/θ^c(q) - c(12
    ⋯ k)(r_2) ⊕⋯⊕θ^c(q) - c(12 ⋯ k)/θ^c(q) - c(12 ⋯ k)(r_n)

which is θ^c(q) - c(12 ⋯ k)/θ^c(q) - c(12 ⋯
k)^(̧p).

The other consequences now follow from applying the recursive formulas.


Thus, it suffices to restrict our attention to subtrees lying under increasing
prefixes.  To avoid clutter in the remainder of the results, we abuse notation
to let (p), ^(̧p), and (p) each refer to their numerators over
the standard denominator ∑_p-prefixed π∈_Nθ^c(π).  To ensure that this is valid, we avow that all of our
equalities will occur between quantities for which their implied denominators
agree.  


For the increasing prefixes p = [12 ⋯ (k-1)] and q = [12 ⋯ k], we have

    ^(̧p) = (q) + ^(̧q) ∑_nontrivial
    permutations
    r  of  q  having  p  as a prefix θ^c(r)-c(q),  and


    (p) = (q) ∑_nontrivial permutations
    r  of 
    q  having  p  as a prefix θ^c(r)-c(q).



There are k children of p in the prefix tree; they are distinguished by
their value in the last position.  The prefix q itself is an eligible child
so (q) is the optimal probability for the subtree rooted at q.  The subtrees
under each of the other k-1 children of p are isomorphic to ^(̧q) via
the bijection σ_r where r is a nontrivial permutation of q having
p as a prefix.  For each π∈_N that is won in ^(̧q), we have
θ^c(σ_r ·π) = θ^c(π)θ^c(r)-c(q) by prefix
equivariance, and the first result follows.

The second result is similar.  First, observe that none of the q-prefixed
π∈_N are p-winnable.  Each of the p-winnable permutations arises
by applying one of the σ_r to a q-winnable permutation π.  This
has the effect of placing the value N into position k-1, as desired.
Prefix equivariance produces a factor of θ^c(r)-c(q) for each choice
of σ_r.



For any increasing prefixes p = [12 ⋯ (k-1)] and q = [12 ⋯ k], we
have that if q is negative then p is negative.


Suppose q is negative so ^(̧q) > (q).  Then, by
Theorem <ref> we have

    ^(̧p) = (q) + ^(̧q) ∑_nontrivial permutations
    r  of  q  having  p  as a prefix θ^c(r)-c(q)


    > (q) ( 1 + ∑_nontrivial permutations
    r  of  q  having  p  as a prefix θ^c(r)-c(q)) =  (q) + (p)  ≥(p),

so p is negative as well.



For a weighted game of best choice defined using a prefix equivariant
statistic, the optimal strategy is positional.


By Corollary <ref>, there exists some k such that all of the increasing
prefixes with size less or equal to k are negative, and all of the increasing
prefixes with size greater than k are positive.  Applying the σ_q
isomorphisms, the same k also serves to separate positive and negative
eligible prefixes in the rest of the tree by Theorem <ref>.  Hence, the
optimal strike strategy coincides with the positional strategy that rejects the
first k candidates and accepts the next left-to-right maximum thereafter.



Knowing that the optimal strategy in a game of best choice is positional
simplifies the analysis considerably.  Rather than recursively traversing the
entire prefix tree to find the optimal strike set, which could conceivably be
any antichain, we know that the optimum must be one of the N strategies
obtained by rejecting k = 0, 1, 2, …, or N-1 candidates and accepting
the next maximum.  Then, one can write an equation to determine k.



It is interesting to compare the proof above at = 1 with arguments from the
literature on the classical secretary problem.  While numerous papers either
assume or claim that the optimal strategy is positional, few of them actually
provide or reference a complete proof.  As far as we can tell,
there are essentially two elementary arguments for the result.  One appears as
part of a “reminiscence” in <cit.> that develops a careful proof using
convexity, along different lines than ours, but has not been widely cited
(although Ron Graham is acknowledged in the postscript).  The other is a
conditioning argument, apparently originating in <cit.> (unpublished)
and very loosely summarized by <cit.>.  Once symmetry (as in
Theorem <ref>) is established, this argument compares the conditional
probabilities for winning if we accept the current candidate (“stay”) versus
if we consider eligible candidates later in the game (“go”).  The argument
claims that the “stay” probabilities are increasing, which can be verified
directly by counting. The argument also claims that the “go” probabilities are
decreasing, but counting is recursive in this case (corresponding to our
Theorem <ref>) and is complicated by the fact that “stay” and “go” are
not complementary probabilities.








§ PRECISE RESULTS FOR EWENS DISTRIBUTION


When we weight by c(π) = # left-to-right maxima in π, we obtain the
Ewens distribution.  In this section, we work out the optimal best choice
strategy for all N.


Let N be the polynomial in  defined by 

    N =  (+1)(+2) ⋯ (+(N-1)).



The following result justifies our “-analogue” notation.


We have

    N = ∑_π∈_Nθ^#left-to-right maxima in π.

Hence, the coefficients of  in N are Stirling numbers (of the type used to count permutations by number of cycles).


This is straightforward to prove using induction since we may extend each
permutation π of N-1 by placing one of the values 1, 2, …, N-1 in
the last position and arranging the complementary values according to π
(this does not create a new left-to-right maximum so contributes (N-1)
N-1 to N) or by simply appending the value N to the last
position of π (which does create a new left-to-right maximum, so
contributes N-1 to N).

The equivalence between the number of cycles and number of left-to-right maxima
(attributed to Rényi) is accomplished by writing the cycle notation for a
permutation using the maximum element in a cycle as the starting point and then
arranging the cycles with increasing maximum elements.  


We are primarily interested in 

    W(N,k) = ∑_k-winnable π∈_N^#left-to-right maxima in π.

Here, we say that π is k-winnable if it would be won by the
positional strategy that rejects the first k candidates and accepts the next
left-to-right maximum thereafter.  Some examples of these polynomials are given
in Figure <ref>.  Our next result provides a recursive description for them.


We have

    W(N,k) = (N-1) W(N-1,k) + (N-2)!/(k-1)!k

with initial conditions W(1, 0) = and W(N,N) = 0.


We have two cases for the k-winnable permutations π∈_N.

    
  * If the last position contains one of the values 1, 2, …, N-1,
        then it is not a left-to-right maximum and 
        we may view the complementary values as some k-winnable
        π∈_N-1.  Hence, these
        contribute (N-1) W(N-1,k) to W(N,k).
    
  * If the last position contains N then it is a left-to-right maximum
        and the value N-1 must lie in one of the first k positions in order
        for π to be k-winnable.  We can choose the rest of the values to
        place among the first k positions in N-2k-1 ways and
        then permute them, keeping track of the number of left-to-right maxima
        with k.  For each of these, we may also then permute the rest
        of the entries in positions k+1, k+2, …, N-1 in (N-k-1)! ways.
        All together, these contribute
        
    ^1 N-2k-1k (N-k-1)! = (N-2)!/(k-1)!k

        to W(N,k).

The initial conditions are immediate.




Now, let (N,k) = W(N,k+1) - W(N,k).  The zeros of these polynomials will determine
the intervals of  that produce games for which a given positional strategy is
optimal.  We begin by translating the recurrence.


We have

    (N,k) = (N-1) (N-1,k) + ^2 (N-2)!/k!k

with initial conditions (N,N-2) = (-(N-1))N-2.


By Theorem <ref>, we have

    (N,k) = W(N,k+1) - W(N,k) = (N-1) (W(N-1,k+1) - W(N-1,k))


    +  (N-2)! ( k+1/ k!  - k/(k-1)!)


    = (N-1) (N-1,k) + (N-2)!/k!k( ( + k) - k )

yielding the result.

The initial conditions follow by subtracting W(N,N-2) = (2N-3) N-2
from W(N,N-1) = N-1.


It turns out that we can solve this recurrence.


We have 

    (N,k) = c_1(N,k) ( (∑_i=k+1^N-11/i) - 1 ) k

for c_1(N,k) = ∏_j=k+1^N-1 j which is constant in .  Hence,  has only real roots.
Moreover, the only positive root of (N,k) occurs at

    = 1 / (∑_i=k+1^N-11/i).



We fix k and argue by induction on N.  When N = k-2, we apply the initial
condition in Corollary <ref> with c_1(N,N-2) = (N-1).

Now suppose the result holds for N-1.  Then, by Corollary <ref>

    (N,k) = (N-1) (  c_1 ( (∑_i=k+1^N-21/i) - 1 ) k) + ^2 (N-2)!/k!k


    = (  (N-1) c_1 ( (∑_i=k+1^N-21/i) - 1 ) + (N-2)!/k!) k


    = (N-1) c_1 ( ( (N-2)(N-3) ⋯ (k+1)/(N-1) c_1 + ∑_k+1 ≤ i ≤ N-2  ∏_k+1 ≤ j ≤ N-2 
     j ≠ i j /(N-2)(N-3) ⋯ (k+1))  - 1 ) k.

Now, if we let c_1 = (N-2)(N-3) ⋯ (k+1), we may rewrite the linear term as

    ( (N-2)(N-3) ⋯ (k+1)/(N-1)(N-2)(N-3) ⋯ (k+1) + (N-1)∑_k+1 ≤ i ≤ N-2  ∏_k+1 ≤ j ≤ N-2 
     j ≠ i j /(N-1)(N-2)(N-3) ⋯ (k+1))  - 1  = ( ∑_i=k+1^N-11/i) - 1

obtaining (N-1) c_1 ( ( ∑_i=k+1^N-11/i) - 1
) k as desired.



We have

    _̨N() =  
            0     if  0 < ≤(∑_i=1^N-11/i)^-1
    
            k     if (∑_i=k^N-11/i)^-1 < ≤(∑_i=k+1^N-11/i)^-1
    
            N-1     if  > N-1.



Since, for fixed N, the positive roots from Theorem <ref> are unique
and increasing in k, we find that the strategy function _̨N() is increasing as
well.


This completely determines the optimal strategy precisely for all N.  Some of
the cutoff values for  are illustrated in Figure <ref>.  We have
highlighted the optimal range including = 1 corresponding to the classical
uniform case.









§ ASYMPTOTIC RESULTS FOR EWENS DISTRIBUTION


To facilitate a comparison with the classical case, we can also solve
the Ewens model asymptotically.



 §.§ Optimal strategy

For fixed  and large N, the optimal k is given by solving

    ^-1 = ∑_i=k^N-11/i = ∑_i=k^N-11/i/(N-1)1/N-1

for k.  The latter is a Riemann sum approximation for the integral ∫_x^1
1/t dt where t = i/N-1 and x = k/N-1.  

Therefore, as N →∞ we obtain

    ^-1 = ∫_x^1 1/t dt = -ln x

which we can solve for x = 1/e^1/.  Thus, the optimal number of initial
rejections is approximately k = N/e^1/ for N sufficiently large.  A plot is
shown in Figure <ref>.





 §.§ Optimal probability of success

Reviewing the previous section, we find that we can solve W(N,k) explicitly.
Each W(N,k) polynomial is just a constant in  (that depends on N and
k) times the polynomial k.


For all N and k ≥ 1, we have

    W(N,k) = k(N-1)!/(k-1)!∑_i=k^N-11/i.

When k = 0, we have W(N,0) = (N-1)!.


This is straightforward to prove by induction from Theorem <ref>.


Since the optimal value of k satisfies = (∑_i=k^N-11/i)^-1 we can cancel it and the optimal probability W
simplifies to

    W(N,k)/N = k/(k-1)!(N-1)!/N.


When  is an integer, this is just a ratio of binomial coefficients, but for
arbitrary positive real  we use gamma functions (see e.g. <cit.>).  By iterating the
recurrence (z+1)=z(z) we obtain
N = (+N)/().
Hence,

    k/(k-1)!(N-1)!/N
    = (+k)/()(k-1)!()(N-1)!/(+N)
    = (+k)/(k)(N)/(+N).

Using lim_x →∞(x+)/(x) x^ = 1, we get

    lim_N →∞(+k)/(k)(N)/(+N)
    = lim_N →∞k^/N^ 
    = lim_N →∞(k/N)^  
    = (1/e^1/)^ = 1/e.

Remarkably, this probability of success is independent of .







§ RESULTS FOR MALLOWS DISTRIBUTION


We now turn to the Mallows distribution defined by c(π) = #inversions in
π.  We begin by working out the standard “-analogue” for this
statistic.


Let N be the polynomial in  defined by 1++^2+⋯+^N-1.
Let N be the polynomial in  defined by 

    N =  NN-1⋯1.




We have

    N = ∑_π∈_Nθ^#inversions in π.



This is straightforward to prove using induction since we may extend each
permutation π of N-1 by placing one of the values i = 1, 2, …, N
in the last position and arranging the complementary values according to π.
This creates N-i new inversions, so contributes NN-1 to N.


Let us redefine

    W(N,k) = ∑_k-winnable π∈_N^#inversions in π

for the Mallows distribution.  Our next result provides a recursive description
for these polynomials.


We have

    W(N,k) = N-1 W(N-1,k) + ^N-k-1kN-2

with initial conditions W(1, 0) = 1 and W(N,N) = 0.


We have two cases for the k-winnable permutations π∈_N.

    
  * If the last position contains one of the values i = 1, 2, …,
        N-1, then it contributes N-i to the inversion count and we may view
        the complementary values as some k-winnable π∈_N-1.  Hence, these contribute N-1 W(N-1,k) to W(N,k).
    
  * If the last position contains N then 
        the value N-1 must lie in one of the first k positions in order
        for π to be k-winnable.  
        These choices for the position of value N-1 contribute ^N-k-1k.
        For each of these, we choose a permutation of size N-2 to fill in the
        remaining positions, keeping track of the inversions with N-2.

The initial conditions are immediate.


We can solve this recurrence.


We have

    W(N,k) = ^N-k-1N-1∑_i=k^N-1k/i

for k > 0 and W(N,0) = ^N-1N-1.


This is straightforward to prove by induction on N from Theorem <ref>.


For this distribution, the precise transition probabilities for each N seem
to be inaccessible, being roots of polynomials (with complex solutions) that
use many repeated root extractions as opposed to the rational numbers we
obtained in the Ewens case.  However, we obtain some interesting asymptotic
results.  Figure <ref> shows a plot of the optimal success probability for
various values of < 1 based on the following theorem.




If < 1 then the optimal strategy as N becomes large is to reject the
first N-j candidates where j = max(-1/(ln), 1), and select the next
left-to-right maximum thereafter.  This strategy succeeds with probability j
^j-1 (1-).  If 1/e <  < 1, this probability of success simplifies to
e^-1( - 1/ln).


Rewriting the probability W(N,k)/N from Corollary <ref> gives

    ^N-k-1k/N∑_i=k^N-11/i =
    (1-) ^N-k-11-^k/1-^N∑_i=k^N-1 1 / 1-^i


    = ^N-^N-1-^N-k+^N-k-1/1 - ^N∑_i=k^N-1 1 /
    1-^i .


For fixed ∈ (0,1), as N becomes large, the fraction tends to
^N-k-1(1 - ) and the terms in the series become close to 1 so the
probability reduces to ^N-k-1(1-)(N-k).  This sequence converges to a
positive value if and only if the N-k sequence converges to a finite value.

So we let j = N-k obtaining lim_N →∞ W(N,k)/N
= j ^j-1 (1-).  Differentiating with respect to j and setting equal to
zero, we solve to obtain the optimal j = -1/(ln).  For < 1/e, we
have j < 1 but we cannot reject more than N-1 candidates so max appears
in the expression.


The case where > 1 is less interesting from our intrinsic learning
perspective but we sketch the behavior of these models for mathematical
completeness.  Taken together, the results also prove that the asymptotically
optimal strategy does not vary continuously with the parameter . 




Fix > 1 and an integer k ≥ 1.  Then,

    lim_N →∞W(N,k)/N = (-1) ^k - 1/^k+1∑_i=k^∞1/^i - 1.

In particular, we approach a single asymptotic distribution as N ∞
so the optimal strategy will be to reject some number of initial candidates
(not depending on N) and select the next left-to-right maximum thereafter.


Once again, consider 

    W(N,k)/N = ^N-^N-1-^N-k+^N-k-1/^N - 1∑_i=k^N-1 1 /^i - 1 .

For fixed > 1, as N becomes large, the fraction tends to
1-^-1-^-k+^-(k+1) = (1-^-1)(1 - ^-k) and the series
converges (e.g. by the integral test).  

Thus, every k-positional strategy has some nonzero probability in the limit
as N →∞.  As k becomes large, the series tends to zero,
being approximately ∑_i=k^∞ (1/)^i = ^-k/(1-^-1).
Therefore, the optimal asymptotic probability will occur for some fixed k
(depending on ).


Figure <ref> shows some plots (obtained numerically) of the optimal
success probabilities for various values of  and k.  For any particular
value of > 1, one can explicitly compute the probabilities in
Corollary <ref> and find the optimal strategy k.  For example, it
appears that k = 1 is optimal for all > 1.285 (approximately).  Although
the series always converges, finding a closed form for its limiting value
involves the “q-digamma function” which prevents us from obtaining a simple
description of the optimal strategy in general.  It also appears that the
maximal probability of success for these models occurs when ≈ 1.55
(for which k = 1 is the optimal strategy).  It would be interesting to
determine this maximum more precisely.






§ ACKNOWLEDGEMENTS


We thank Laura Taalman, John Webb, and Becky Wild for helpful discussions related to this
work.














ABNP16

[ABNP16]bouvel
Nicolas Auger, Mathilde Bouvel, Cyril Nicaud, and Carine Pivoteau,
  Analysis of algorithms for permutations biased by their number of
  records, Proceedings of the 27th International Conference on
  Probabilistic, Combinatorial and Asymptotic Methods for the
  Analysis of Algorithms—AofA'16, Jagiellonian Univ., Dep. Theor.
  Comput. Sci., Kraków, 2016, p. 12. 3817514

[ABT03]log-book
Richard Arratia, A. D. Barbour, and Simon Tavaré, Logarithmic
  combinatorial structures: a probabilistic approach, EMS Monographs in
  Mathematics, European Mathematical Society (EMS), Zürich, 2003.
  2032426

[BIKR08]kleinberg08
M. Babaioff, N. Immorlica, D. Kempe, and Kleinberg R., Online auctions
  and generalized secretary problems, SIGecom Exchange 7 (2008),
  1–11.

[CDE18]elizalde
Harry Crane, Stephen DeSalvo, and Sergi Elizalde, The probability of
  avoiding consecutive patterns in the Mallows distribution, Random
  Structures Algorithms 53 (2018), no. 3, 417–447. 3854041

[Fer89]ferguson
Thomas S. Ferguson, Who solved the secretary problem?, Statist. Sci.
  4 (1989), no. 3, 282–296, With comments and a rejoinder by the
  author. 1015277

[FJ19]fowlkes
Aaron Fowlkes and Brant Jones, Positional strategies in games of best
  choice, Involve 12 (2019), no. 4, 647–658. 3941603

[Fre83]freeman
P. R. Freeman, The secretary problem and its extensions: a review,
  Internat. Statist. Rev. 51 (1983), no. 2, 189–206.

[Gar95]gardner
Martin Gardner, New mathematical diversions, revised ed., MAA Spectrum,
  Mathematical Association of America, Washington, DC, 1995. 1335231

[GM66]gilbert–mosteller
John P. Gilbert and Frederick Mosteller, Recognizing the maximum of a
  sequence, J. Amer. Statist. Assoc. 61 (1966), 35–73. 0198637

[Jon19]jones18
Brant Jones, Avoiding patterns and making the best choice, Discrete
  Math. 342 (2019), no. 6, 1529–1545. 3922151

[Kad94]kadison
Richard V. Kadison, Strategies in the secretary problem, Exposition.
  Math. 12 (1994), no. 2, 125–144. 1274782

[OLBC10]NIST
Frank W. J. Olver, Daniel W. Lozier, Ronald F. Boisvert, and Charles W. Clark
  (eds.), NIST handbook of mathematical functions, U.S. Department of
  Commerce, National Institute of Standards and Technology, Washington, DC;
  Cambridge University Press, Cambridge, 2010, With 1 CD-ROM (Windows,
  Macintosh and UNIX). 2723248

[Pal58]palermo
R. Palermo, Addendum to a letter by Merrill R. Flood, Martin
  Gardner papers at Stanford University Archives (1958), series 1, box 5,
  folder 19.

[Pfe89]pfeifer
Dietmar Pfeifer, Extremal processes, secretary problems and the 1/e
  law, J. Appl. Probab. 26 (1989), no. 4, 722–733. 1025389

[RF88]reeves–flack
J. H. Reeves and V. F. Flack, A generalization of the classical secretary
  problem: dependent arrival sequences, J. Appl. Probab. 25 (1988),
  no. 1, 97–105. 929508

[SV99]golden
Dimitris A. Sardelis and Theodoros M. Valahas, Decision making: a golden
  rule, Amer. Math. Monthly 106 (1999), no. 3, 215–226. 1682342



