---
abstract: '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 permutations, one can generalize the uniform distribution on the symmetric group by weighting 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. We also introduce a general class of permutation statistics that always produces games of best choice whose optimal strategy is positional. Specializing this result produces a new proof of a foundational result from the literature on the secretary problem.'
address: 'Department of Mathematics and Statistics, MSC 1911, James Madison University, Harrisonburg, VA 22807'
author:
- Brant Jones
title: Weighted games of best choice
---

Introduction {#s:intro}
============

The game of best choice (or secretary problem) is a model for sequential decision making. 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 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 also approaches $1/e$.

The classical model assumes that all $N!$ interview rank orders are equally likely, which we believe is mathematically expedient but unrealistic. Over the period that the player is conducting the $N$ interviews, there may exist extrinsic trends in the candidate pool. Also, as the interviewer ranks the candidates at each step, they acquire information about the domain that allows them to hone the pool to include more relevant candidates. Overall, this results in candidate ranks that are improving over time rather than uniform. We call this process [**intrinsic learning**]{}. As a first step towards understanding such mechanisms, we are interested in studying how different assumptions for the distribution of interview rank orders change the optimal strategy and probability of success in the game of best choice. Continuing work from [@fowlkes] and [@jones18], we establish in this paper a class of weighted models that generalize the uniform game in a natural way.

We model interview orderings as [**permutations**]{}. The permutation $\pi$ of $N$ is expressed in [**one-line notation**]{} as $[\pi_1 \pi_2 \cdots \pi_N]$ where the $\pi_i$ consist of the elements $1, 2, \ldots, N$ (so each element appears exactly once). In the best choice game, $\pi_i$ is the rank of the $i$th candidate interviewed [*in reality*]{}, where rank $N$ is best and $1$ is worst. What the player sees at each step, however, are [*relative*]{} rankings. For example, corresponding to the interview order $\pi = [2516374]$, the player 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 $\pi$ consist of the elements $\pi_j$ that are larger in value than all elements $\pi_i$ lying to the left. The [**inversions**]{} of $\pi$ consist of pairs $\pi_i > \pi_j$ where $i <
j$.

Now, let $c: {\mathfrak{S}}_N \rightarrow {\mathbb{N}}$ be a statistic on the symmetric group of permutations of size $N$. Then we can weight the permutation $\pi \in {\mathfrak{S}}_N$ by ${\theta}^{c(\pi)}$ where ${\theta}$ is a positive real number to obtain a discrete probability distribution on ${\mathfrak{S}}_N$. When ${\theta}= 1$, we recover the uniform model. Distributions of this form were introduced by Mallows where $c(\pi)$ represented some measure of distance from a fixed permutation, typically the identity. More recently, these distributions have been used by researchers in combinatorics; see [@elizalde; @bouvel; @log-book] for example. In our first result, Theorem \[t:main\], 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 model: to reject an initial set of candidates and accept the next left-to-right maximum thereafter. This seems mildly surprising given that the full history of relative rankings are available at each step to guide a strategy; evidently, however, the positions of the left-to-right maxima are the only information required to play these games optimally. Also, it seems remarkable that even for $\theta = 1$ where this result is reported to be well-known, we have not encountered reasoning along the lines we have given here. Hence, our proof gives a new perspective on an important result from the literature on the secretary problem; see Remark \[r:hist\].

In our setting, we interpret $c(\pi)$ as a goal for intrinsic learning by the interviewer, over the course of the $N$ interviews. The first model is based on the Ewens distribution where $c(\pi)$ is the number of left-to-right maxima in $\pi$. When ${\theta}> 1$, this has the effect of amplifying the probability of experiencing candidates whose rank exceeds that of all earlier candidates. The second model is based on what has become known as the Mallows distribution where $c(\pi)$ is the number of inversions in $\pi$. When ${\theta}< 1$, this has the effect of dampening the probability of experiencing “disappointing pairs,” where an earlier candidate ranks higher than a later candidate. In terms of permutation patterns, the Mallows model weights each permutation $\pi$ by the number of $21$-instances in $\pi$, which facilitates comparison with results in [@fowlkes] and [@jones18] for the $321$-avoiding model.

Once we know by Theorem \[t:main\] that [*some*]{} positional strategy is optimal for each value of $\theta$, we can define the [**strategy function**]{} ${\kappa}_N(\theta)$ for a weighted game of best choice to be the number of candidates that we initially reject in the optimal strategy for value $\theta$. Hence, ${\kappa}_N$ is some function from $\mathbb{R}_{> 0}$ to $\{0, 1, \cdots,
N-1\}$. In Corollary \[c:ewensmain\], we describe this function precisely for the Ewens model.

When we perform the asymptotic analysis for the Ewens model, we find that the optimal strategy depends on ${\theta}$ with the optimal number of initial rejections being $k = N/e^{1/{\theta}}$. Remarkably though, the probability of success is always $1/e$, independent of ${\theta}$, neither better nor worse than the classical case.

The Mallows model is more subtle. When ${\theta}< 1$, the optimal strategy is to reject all but the last $j = \max(-1/(\ln {\theta}), 1)$ candidates and select the next left-to-right maximum thereafter. This “right-justified” strategy succeeds with probability $j {\theta}^{j-1} (1-{\theta})$. When ${\theta}> 1$, the optimal strategy is “left-justified,” rejecting the first $k$ candidates for some $k$ depending on ${\theta}$ but independent of $N$. Consequently, this shows that the classical model (as embedded in the Mallows model) is highly unstable, another reason we find it to be unrealistic: even an infinitesimal change away from ${\theta}= 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 suggests a goal for future work of finding models where the asymptotic optimal strategy varies continuously with parameterizations of the distribution.

We now mention some earlier work in this area. Martin Gardner’s 1960 Scientific American column popularized what he called “the game of googol,” although the problem has roots which predate this. His article has been reprinted in [@gardner]. One of the first papers to systematically study the game of best choice in detail is [@gilbert--mosteller]. Many other variations and some history have been given in [@ferguson] and [@freeman]. Recently, researchers (e.g. [@kleinberg08]) 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.

Only a few papers have previously considered nonuniform distributions for the secretary problem. Pfeifer [@pfeifer] considers the case where interview ranks are independent but have cumulative distribution functions containing parameters determined by the position of the interview. The paper [@reeves--flack] considers an explicit continuous probability distribution that allows for dependencies between nearby arrival ranks via a single parameter. Inspired by approximation theory, the paper [@kleinberg--etal] studies some general properties of non-uniform rank distributions for the secretary problem.

We now outline the rest of the paper. In Section \[s:setup\] we review the form of the optimal strategy for games of best choice, and show in Section \[s:tilt\] that any sufficiently local statistic will generate a game with an optimal strategy having the same form as the classical model. In Sections \[s:ew\] and \[s:aew\], we obtain precise and asymptotic results for the Ewens model. The Mallows model is treated in Section \[s:m\].

The weighted game of best choice {#s:setup}
================================

Fix a discrete probability distribution on the symmetric group ${\mathfrak{S}}_N$ where $f(\pi)$ is the probability of the permutation $\pi~\in~{\mathfrak{S}}_N$. This defines a game of best choice as follows.

\[d:pflat\] Given a sequence of $i$ distinct integers, we define its [**flattening**]{} to be the unique permutation of $\{1, 2, \ldots, i\}$ having the same relative order as the elements of the sequence. Given a permutation $\pi$, define the [**$i$th prefix flattening**]{}, denoted ${\pi|_{[i]}}$, to be the permutation obtained by flattening the sequence $\pi_1, \pi_2, \ldots, \pi_i$. In the [**game of best choice**]{} some $\pi \in {\mathfrak{S}}_N$ is chosen randomly, with probability $f(\pi)$, and each prefix flattening ${\pi|_{[1]}}, {\pi|_{[2]}}, \ldots$ is presented sequentially to the player. If the player stops at value $N$, they win; otherwise, they lose.

In this work, we are primarily interested in probability distributions obtained from weighting by some statistic $c : {\mathfrak{S}}_N \rightarrow {\mathbb{N}}$ and a positive real number $\theta$ via $$f(\pi) = \frac{ \theta^{c(\pi)} }{ \sum_{\pi \in {\mathfrak{S}}_N} \theta^{c(\pi)} }.$$ For example, we may take $c(\pi)$ to be the number of left-to-right maxima in $\pi$, obtaining the [**Ewens distribution**]{}; if $c(\pi)$ is the number of inversions then we obtain the [**Mallows distribution**]{}. When $\theta = 1$, we recover the [**complete uniform distribution**]{}.

A [**strike strategy**]{} for a game of best choice is defined by a collection of prefixes from $\bigcup_{i=1}^N {\mathfrak{S}}_i$ that we call the [**strike set**]{}. To play the strategy on a particular interview ordering $\pi$, compare prefix flattenings to the strike set at each step. As soon as the $i$th prefix flattening occurs in the strike set, accept the candidate at position $i$ and end the game. Otherwise, the strike strategy rejects the candidate at position $i$ to continue playing. It follows directly from the definitions that any strategy (including the optimal strategy) for a game of best choice can be represented as a strike strategy because the player has only the relative ranking information captured in the prefix flattenings to guide them as they play. We can visualize the set of all possible prefixes as a tree, partially ordered by containment of prefix flattening, which we call the [**prefix tree**]{}. See Figure \[f:treeex\] for a small example.

To find the optimal strike set, we define several conditional probabilities. For brevity, we say that $\pi \in {\mathfrak{S}}_N$ is [**$p$-prefixed**]{} if it contains $p$ as a prefix flattening, and we say that $\pi$ is [**$p$-winnable**]{} if including $p$ in the strike set would win the interview order $\pi$. Explicitly for $p = p_1 p_2 \cdots p_k$, we have that $\pi$ is $p$-winnable if $\pi$ is $p$-prefixed and $\pi_k = N$. For each prefix $p$, the [**strike probability**]{} ${\mathcal{S}}(p)$ is the probability of winning the game if the prefix $p$ is included in the strike set restricted to those interview rank orders having $p$ as a prefix. Since each denominator of $f(\pi)$ is just a normalizing constant, we may cancel it obtaining $${\mathcal{S}}(p) = \left( \sum\limits_{p\text{-winnable } \pi \in {\mathfrak{S}}_N} \theta^{c(\pi)} \right)\Big/\left( \sum\limits_{p\text{-prefixed } \pi \in {\mathfrak{S}}_N} \theta^{c(\pi)} \right)$$ In particular, ${\mathcal{S}}_N(p)$ is $0$ unless $p$ ends in a left-to-right maximum; for this reason we refer to a prefix as [**eligible**]{} if it ends in a left-to-right maximum or has size $N$ (included for completeness). Hence, it suffices to restrict our attention to strike sets

1.  consisting of prefixes that are eligible, and

2.  having no pair of elements such that one contains the other as a prefix flattening, and

3.  such that every permutation in ${\mathfrak{S}}_N$ contains some element of the strike set as a prefix flattening.

Given this setup, we let ${\mathcal{S}}(p^{\circ})$ 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 ${\mathcal{S}}(\bar{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$. Let each of these be conditional probabilities with [**standard denominator**]{} $\sum_{p\text{-prefixed } \pi \in
{\mathfrak{S}}_N} \theta^{c(\pi)}$. Then, it follows directly from the definitions that $${\mathcal{S}}(\bar{p}) = \max({\mathcal{S}}(p), {\mathcal{S}}(p^{\circ})).$$ This formula can be used to recursively determine ${\mathcal{S}}(\bar{1})$, the globally optimal probability of a win. To also keep track of the globally optimal strategy, let us say that $p$ is [**positive**]{} if ${\mathcal{S}}(p) \geq {\mathcal{S}}(p^{\circ})$ and [**negative**]{} otherwise. The positive prefixes represent locally optimal strikes.

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 $\bigoplus_{p \in A} {\mathcal{S}}(p)$ where we define $\frac{a}{b} \oplus \frac{c}{d} =
\frac{a+c}{b+d}$ and use the standard denominator for all strike probabilities.

We first show that all of the probabilities are determined. 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 ${\mathcal{S}}(p^{\circ})$ probabilities for each prefix of size $i$ can be obtained as $\bigoplus_{p\text{-prefixed } q \text{ of size }i+1}{\mathcal{S}}(\bar{q})$, and then the ${\mathcal{S}}(\bar{p})$ probabilities can be determined from the formula. (The $\oplus$ operation represents the probability of a disjoint union of events.) This process is essentially a discrete version of “backwards induction.”

The positive prefixes are locally optimal by definition. If a prefix $p$ has no (proper) prefix flattenings that are positive, then $p$ must be globally optimal as well.

Consider the tree shown in Figure \[f:treeex\] for $N = 4$ at ${\theta}= 1$. The strike probabilities ${\mathcal{S}}(p)$ are illustrated in the figure. Since ${\mathcal{S}}(123) =
3/4 \geq 1/4 = {\mathcal{S}}(123^{\circ})$, we have that $123$ is a positive prefix. Similarly, ${\mathcal{S}}(12) = 6/12 \geq 5/12 = {\mathcal{S}}(12^{\circ})$ so $12$ is also a positive prefix. On the other hand, ${\mathcal{S}}(1) = 6/24 < 11/24 = {\mathcal{S}}(1^{\circ})$ 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 all of the 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 $\oplus$-sum of these contributions, namely $11/24$.

Prefix equivariance and positional strategies {#s:tilt}
=============================================

While any game of best choice has an optimal strike strategy, the classical game (where $f(\pi) = 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. From our point of view, this seems to be a minor miracle as there are [*many*]{} antichains in the partial order of prefix-containment that would serve as potentially optimal strike sets but only $N$ possible positional strategies. 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. To define it, let ${\mathcal{T}}(p^{\circ})$ be the “open” subforest of prefixes containing (but not equal to) $p$, and let ${\mathcal{T}}(\bar{p})$ be the “closed” subtree of prefixes containing $p$, including $p$ itself.

Suppose that $p = [12 \cdots k]$ and let $\sigma_q$ be the permutation that rearranges the prefix $p$ to give some other prefix $q$ of size $k$. We can extend this to an action on ${\mathcal{T}}(\bar{p})$, denoted $\sigma_q \cdot \pi$, by similarly permuting the first $k$ entries and fixing the last $i-k$ entries of $\pi$, where $i$ is the size of $\pi \in {\mathcal{T}}(\bar{p})$. Then $\sigma_q$ is a bijection from ${\mathcal{T}}(\bar{p})$ to ${\mathcal{T}}(\bar{q})$.

Suppose that the statistic $c$ satisfies $c(\pi) - c(\sigma_q \cdot \pi) = c(12
\cdots k) - c(q)$ for all prefixes $q$ and all $\pi \in {\mathcal{T}}(\overline{12 \cdots
k})$, where $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(\pi)$ that results from permuting the first $k$ entries of $\pi$ is the same as the change that would result if we restricted $c$ to $k$ entries. Hence, statistics that count sufficiently local phenomena in permutations will be prefix equivariant.

It is straightforward to check that $c(\pi) = \#$ left-to-right maxima in $\pi$ and $c(\pi) = \#$ inversions in $\pi$ are each prefix equivariant statistics. Explicitly, if $\pi = \pi_1 \pi_2 \cdots \pi_k | \pi_{k+1} \pi_{k+2} \cdots
\pi_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(\pi) = \#321$-instances in $\pi$ is not prefix equivariant because, for example, $c(2468|1357) = 0$ yet $c(4268|1357) = 1$ even though $c(2468) = 0 = c(4268)$.

\[t:pres\] Any statistic that is prefix equivariant yields strike probabilities that are preserved under the restricted bijection $\sigma_q: {\mathcal{T}}(12 \cdots k^{\circ})
\rightarrow {\mathcal{T}}(q^{\circ})$, where $k$ is the size of $q$. If $q$ is eligible then these probabilities are also preserved under $\sigma_q: {\mathcal{T}}(\overline{12 \cdots
k}) \rightarrow {\mathcal{T}}(\bar{q})$.

Consequently, for $p \in {\mathcal{T}}(12 \cdots k^{\circ})$ (and additionally for $p = [12 \cdots k]$ if $q$ is eligible), we have that

-   the ${\mathcal{S}}(p^{\circ})$ probabilities are preserved by $\sigma_q$, and

-   the ${\mathcal{S}}(\bar{p})$ probabilities are preserved by $\sigma_q$, and

-   if $p$ and $q$ are eligible, we have $p$ is positive if and only if $\sigma_q \cdot p$ is positive.

Fix $q$ to be any prefix of size $k$, and let $p \in {\mathcal{T}}(\overline{12 \cdots k})$ with size $m$. Then, ${\mathcal{S}}(p) = \frac{ \sum_{p\text{-winnable } \pi \in {\mathfrak{S}}_N} \theta^{c(\pi)} }{
\sum_{p\text{-prefixed } \pi \in {\mathfrak{S}}_N} \theta^{c(\pi)} }$.

Since the weights satisfy $c(\pi) - c(\sigma_q \cdot \pi) = c(12 \cdots k) -
c(q)$ for all $\pi \in {\mathcal{T}}(\overline{12 \cdots k})$, we have $${\mathcal{S}}(\sigma_q \cdot p) = \frac{ \sum_{(\sigma_q \cdot p)\text{-winnable } \pi
\in {\mathfrak{S}}_N} \theta^{c(\pi)} }{ \sum_{(\sigma_q \cdot p)\text{-prefixed } \pi
\in {\mathfrak{S}}_N} \theta^{c(\pi)} } = \frac{ \sum_{p\text{-winnable } \pi \in {\mathfrak{S}}_N}
\theta^{c(\sigma_q \cdot \pi)} }{ \sum_{p\text{-prefixed } \pi \in {\mathfrak{S}}_N} \theta^{c(\sigma_q \cdot \pi)} }$$ which is $\frac{ \theta^{c(q) - c(12 \cdots k)} }{ \theta^{c(q) - c(12 \cdots
k)}} S(p)$ unless $q$ happens to be ineligible and $p = [12 \cdots k]$ in which case $\sigma_q \cdot p = q$ and so ${\mathcal{S}}(q) = 0$.

The probability ${\mathcal{S}}(p^{\circ})$ is an $\oplus$-sum of strike probabilities, say $${\mathcal{S}}(p^{\circ}) = {\mathcal{S}}(r_1) \oplus {\mathcal{S}}(r_2) \oplus \cdots \oplus {\mathcal{S}}(r_n),$$ for some prefixes $r_i \in \bigcup_{j = m+1}^N {\mathfrak{S}}_j$. Then since $\sigma_q$ is a strike-probability preserving bijection, we have $${\mathcal{S}}((\sigma_q \cdot p)^{\circ}) = {\mathcal{S}}(\sigma_q \cdot r_1) \oplus {\mathcal{S}}(\sigma_q \cdot
r_2) \oplus \cdots \oplus {\mathcal{S}}(\sigma_q \cdot r_n)$$ $$= \frac{ \theta^{c(q) - c(12 \cdots k)} }{ \theta^{c(q) - c(12 \cdots
k)}} {\mathcal{S}}(r_1) \oplus \frac{ \theta^{c(q) - c(12 \cdots k)} }{ \theta^{c(q) - c(12
\cdots k)}} {\mathcal{S}}(r_2) \oplus \cdots \oplus \frac{ \theta^{c(q) - c(12 \cdots k)}
}{ \theta^{c(q) - c(12 \cdots k)}} {\mathcal{S}}(r_n)$$ which is $\frac{ \theta^{c(q) - c(12 \cdots k)} }{ \theta^{c(q) - c(12 \cdots
k)}} {\mathcal{S}}(p^{\circ})$.

The other consequences follow directly from the definitions.

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 ${\mathcal{S}}(p), {\mathcal{S}}(p^{\circ})$, and ${\mathcal{S}}(\bar{p})$ each refer to their numerators over the standard denominator $\sum_{p\text{-prefixed } \pi \in {\mathfrak{S}}_N}
\theta^{c(\pi)}$. To ensure that this is valid, we avow that all of our equalities will occur between quantities for which their implied denominators agree.

\[t:pc\] For the increasing prefixes $p = [12 \cdots (k-1)]$ and $q = [12 \cdots k]$, we have $${\mathcal{S}}(p^{\circ}) = {\mathcal{S}}(\bar{q}) + {\mathcal{S}}(q^{\circ}) \sum_{\substack{\text{nontrivial
permutations} \\r \text{ of } q \text{ having } p \text{ as a prefix }}} \theta^{c(r)-c(q)}, \text{ and }$$ $${\mathcal{S}}(p) = {\mathcal{S}}(q) \sum_{\substack{\text{nontrivial permutations} \\r \text{ of }
q \text{ having } p \text{ as a prefix }}} \theta^{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 ${\mathcal{S}}(\bar{q})$ is the optimal probability under this subtree. The subtrees under each of the other $k-1$ children of $p$ are isomorphic to ${\mathcal{T}}(q^{\circ})$ via the bijection $\sigma_r$ where $r$ is a nontrivial permutation of $q$ having $p$ as a prefix. For each $\pi \in {\mathfrak{S}}_N$ that is won in ${\mathcal{S}}(q^{\circ})$, we have $\theta^{c(\sigma_r \cdot \pi)} = \theta^{c(\pi)} \theta^{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 $\pi \in {\mathfrak{S}}_N$ are $p$-winnable. Each of the $p$-winnable permutations arises by applying one of the $\sigma_r$ to a $q$-winnable permutation $\pi$. This has the effect of placing the value $N$ into position $k-1$, as desired. Prefix equivariance produces a factor of $\theta^{c(r)-c(q)}$ for each choice of $\sigma_r$.

\[c:t1\] For any increasing prefixes $p = [12 \cdots (k-1)]$ and $q = [12 \cdots k]$, we have that if $q$ is negative then $p$ is negative.

Suppose $q$ is negative so ${\mathcal{S}}(q^{\circ}) > {\mathcal{S}}(q)$. Then, by Theorem \[t:pc\] we have $${\mathcal{S}}(p^{\circ}) = {\mathcal{S}}(\bar{q}) + {\mathcal{S}}(q^{\circ}) \sum_{\substack{\text{nontrivial permutations} \\r \text{ of } q \text{ having } p \text{ as a prefix }}} \theta^{c(r)-c(q)}$$ $$> {\mathcal{S}}(q) \left( 1 + \sum_{\substack{\text{nontrivial permutations} \\r \text{ of } q \text{ having } p \text{ as a prefix }}} \theta^{c(r)-c(q)} \right) =  {\mathcal{S}}(q) + {\mathcal{S}}(p)  \geq {\mathcal{S}}(p),$$ so $p$ is negative as well.

\[t:main\] For a weighted game of best choice defined using a prefix equivariant statistic, the optimal strategy is positional.

By Corollary \[c:t1\], 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 $\sigma_q$ isomorphisms, the same $k$ also serves to separate positive and negative eligible prefixes in the rest of the tree by Theorem \[t:pres\]. 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.

\[r:hist\] It is interesting to compare this proof at ${\theta}= 1$ with arguments from the literature on the secretary problem. The paper of Gilbert–Mosteller [@gilbert--mosteller] is often cited (e.g. by [@ferguson]) as a proof of the result that among all potential strategies, the optimal one must be positional. However, their proof only considers strategies that always stop at a single particular position and does not address the possibility that a player may stop at various positions depending on the relative rankings encountered in the game. The paper of Kadison [@kadison] does provide a complete proof of the desired result (along different lines than ours), but it does not seem to have been widely cited.

$$\scalebox{0.67}{ \begin{tikzpicture}[grow=down]
                    \tikzstyle{level 1}=[sibling distance=120mm]
     \tikzstyle{level 2}=[sibling distance=40mm]
     \tikzstyle{level 3}=[sibling distance=10mm]
     \node {$\substack{1 \\ \ \\ \frac{6{\theta}}{{\theta}^4 + 6{\theta}^3 + 11{\theta}^2 + 6{\theta}}}$ }
     child{ node {$\substack{12 \\ \ \\ \frac{6{\theta}^2}{{\theta}^4 + 5{\theta}^3 + 6{\theta}^2}}$ } 
     child{ node {$\substack{123 \\ \ \\ \frac{3{\theta}^3}{{\theta}^4 + 3{\theta}^3}}$ }
     child{ node{$\substack{1234 \\ \ \\ \frac{{\theta}^4}{{\theta}^4}}$}}
       child{ node{1243}}
       child{ node{1342}}
       child{ node{2341}}
   }
   child{ node[gray]  {132 }
   child{ node{$\substack{1324 \\ \ \\ \frac{{\theta}^3}{{\theta}^3}}$} }
       child{ node{1423}}
       child{ node{1432}}
       child{ node{2431}}
   }
   child{ node[gray]  {231 }
   child{ node{$\substack{2314 \\ \ \\ \frac{{\theta}^3}{{\theta}^3}}$} }
       child{ node{2413}}
       child{ node{3412}}
       child{ node{3421}}
   }
 }
 child{ node[gray]  {21 } 
 child{ node {$\substack{213 \\ \ \\ \frac{3{\theta}^2}{{\theta}^3 + 3{\theta}^2}}$ }
 child{ node{$\substack{2134 \\ \ \\ \frac{{\theta}^3}{{\theta}^3}}$}}
       child{ node{2143}}
       child{ node{3142}}
       child{ node{3241}}
   }
   child{ node[gray]  {312 }
   child{ node{$\substack{3124 \\ \ \\ \frac{{\theta}^2}{{\theta}^2}}$} }
       child{ node{4123}}
       child{ node{4132}}
       child{ node{4231}}
   }
   child{ node[gray]  {321 }
   child{ node{$\substack{3214 \\ \ \\ \frac{{\theta}^2}{{\theta}^2}}$} }
       child{ node{4213}}
       child{ node{4312}}
       child{ node{4321}}
   }
 };
\end{tikzpicture}
}$$

In Figure \[f:treeex\] we have illustrated the prefix tree with ineligible prefixes shown in gray and strike probabilities given below each eligible prefix.

Precise results for Ewens distribution {#s:ew}
======================================

When we weight by $c(\pi) = \#$ left-to-right maxima in $\pi$, 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 ${\theta}$ defined by $${\{N\}!} =  {\theta}({\theta}+1)({\theta}+2) \cdots ({\theta}+(N-1)).$$

The following result justifies our “${\theta}$-analogue” notation.

We have $${\{N\}!} = \sum_{\pi \in {\mathfrak{S}}_N} \theta^{\# \text{left-to-right maxima in } \pi}.$$ Hence, the coefficients of ${\theta}$ 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 $\pi$ of $N-1$ by placing one of the values $1, 2, \ldots, N-1$ in the last position and arranging the complementary values according to $\pi$ (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 $\pi$ (which does create a new left-to-right maximum, so contributes ${\theta}{\{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) = \sum_{k\text{-winnable } \pi \in {\mathfrak{S}}_N} {\theta}^{\#\text{left-to-right maxima in } \pi}.$$ Here, we say that $\pi$ 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 \[f:W\]. Our next result provides a recursive description for them.

\[t:W\] We have $$W(N,k) = (N-1) W(N-1,k) + \frac{(N-2)!}{(k-1)!} {\theta}{\{k\}!}$$ with initial conditions $W(1, 0) = {\theta}$ and $W(N,N) = 0$.

We have two cases for the $k$-winnable permutations $\pi \in {\mathfrak{S}}_{N}$.

-   If the last position contains one of the values $1, 2, \ldots, N-1$, then it is not a left-to-right maximum and we may view the complementary values as some $k$-winnable $\widetilde{\pi} \in {\mathfrak{S}}_{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 $\pi$ to be $k$-winnable. We can choose the rest of the values to place among the first $k$ positions in ${ {N-2} \choose {k-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, \ldots, N-1$ in $(N-k-1)!$ ways. All together, these contribute $${\theta}^1 { {N-2} \choose {k-1}} {\{k\}!} (N-k-1)! = \frac{(N-2)!}{(k-1)!}
            {\theta}{\{k\}!}$$ to $W(N,k)$.

The initial conditions are immediate.

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

\[c:Wrec\] We have $${\Delta W}(N,k) = (N-1) {\Delta W}(N-1,k) + {\theta}^2 \frac{(N-2)!}{k!} {\{k\}!}$$ with initial conditions ${\Delta W}(N,N-2) = {\theta}({\theta}-(N-1)){\{N-2\}!}$.

By Theorem \[t:W\], we have $${\Delta W}(N,k) = W(N,k+1) - W(N,k) = (N-1) \left(W(N-1,k+1) - W(N-1,k)\right)$$ $$+ {\theta}(N-2)! \left( \frac{ {\{k+1\}!} }{ k! } - \frac{{\{k\}!}}{(k-1)!} \right)$$ $$= (N-1) {\Delta W}(N-1,k) + {\theta}\frac{(N-2)!}{k!} {\{k\}!} \left( ({\theta}+ k) - k \right)$$ yielding the result.

The initial conditions follow by subtracting $W(N,N-2) = (2N-3) {\theta}{\{N-2\}!}$ from $W(N,N-1) = {\theta}{\{N-1\}!}$.

It turns out that we can solve this recurrence.

\[t:dwmain\] We have $${\Delta W}(N,k) = c_1(N,k) \left( \left(\sum_{i=k+1}^{N-1} \frac{1}{i}\right){\theta}- 1 \right) {\theta}{\{k\}!}$$ for some $c_1$ which is constant in ${\theta}$. Hence, ${\Delta W}$ has only real roots. Moreover, the only positive root of ${\Delta W}(N,k)$ occurs at $${\theta}= 1 \Big/ \left(\sum_{i=k+1}^{N-1} \frac{1}{i}\right).$$

We fix $N$ and argue by induction. The base case for $k = N-2$ matches the initial conditions in Corollary \[c:Wrec\] with $c_1(N,N-2) = (N-1)$.

Now suppose the result holds for $N-1$. Then, by Corollary \[c:Wrec\] $${\Delta W}(N,k) = (N-1) \left(  c_1 \left( \left(\sum_{i=k+1}^{N-2} \frac{1}{i}\right){\theta}- 1 \right) {\theta}{\{k\}!} \right) + {\theta}^2 \frac{(N-2)!}{k!} {\{k\}!}$$ $$= \left(  (N-1) c_1 \left( \left(\sum_{i=k+1}^{N-2} \frac{1}{i}\right){\theta}- 1 \right) + {\theta}\frac{(N-2)!}{k!} \right) {\theta}{\{k\}!}$$ $$= (N-1) c_1 \left( \left( \frac{(N-2)(N-3) \cdots (k+1)}{(N-1) c_1} + \frac{\sum\limits_{k+1 \leq i \leq N-2}\ \ \prod\limits_{\substack{k+1 \leq j \leq N-2 \\ j \neq i}} j }{(N-2)(N-3) \cdots (k+1)} \right) {\theta}- 1 \right) {\theta}{\{k\}!}.$$ Now, if we let $c_1 = (N-2)(N-3) \cdots (k+1)$, we may rewrite the linear term as $$\left( \frac{(N-2)(N-3) \cdots (k+1)}{(N-1)(N-2)(N-3) \cdots (k+1)} + \frac{(N-1)\sum\limits_{k+1 \leq i \leq N-2}\ \ \prod\limits_{\substack{k+1 \leq j \leq N-2 \\ j \neq i}} j }{(N-1)(N-2)(N-3) \cdots (k+1)} \right) {\theta}- 1  = \left( \sum_{i=k+1}^{N-1} \frac{1}{i}\right){\theta}- 1$$ obtaining $(N-1) c_1 \left( \left( \sum_{i=k+1}^{N-1} \frac{1}{i}\right){\theta}- 1
\right) {\theta}{\{k\}!}$ as desired.

\[c:ewensmain\] We have $${\kappa}_N({\theta}) = \begin{cases} 
        0 & \text{ if } 0 < {\theta}\leq \left(\sum_{i=1}^{N-1} \frac{1}{i}\right)^{-1} \\
        k & \text{ if }  \left(\sum_{i=k}^{N-1} \frac{1}{i}\right)^{-1} < {\theta}\leq \left(\sum_{i=k+1}^{N-1} \frac{1}{i}\right)^{-1} \\
        N-1 & \text{ if } {\theta}> N-1.
\end{cases}$$

Since, for fixed $N$, the positive roots from Theorem \[t:dwmain\] are unique and increasing in $k$, we find that the strategy function ${\kappa}_N({\theta})$ is increasing as well.

This completely determines the optimal strategy precisely for all $N$. Some of the cutoff values for ${\theta}$ are illustrated in Figure \[f:cr\]. We have highlighted the optimal range including ${\theta}= 1$ corresponding to the classical uniform case.

Asymptotic results for Ewens distribution {#s:aew}
=========================================

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

Optimal strategy
----------------

For fixed ${\theta}$ and large $N$, the optimal $k$ is given by solving $${\theta}^{-1} = \sum_{i=k}^{N-1} \frac{1}{i} = \sum_{i=k}^{N-1} \frac{1}{i/(N-1)} \frac{1}{N-1}$$ for $k$. The latter is a Riemann sum approximation for the integral $\int_x^1
\frac{1}{t} \ dt$ where $t = \frac{i}{N-1}$ and $x = \frac{k}{N-1}$.

Therefore, as $N \rightarrow \infty$ we obtain $${\theta}^{-1} = \int_x^1 \frac{1}{t} \ dt = -\ln x$$ which we can solve for $x = 1/e^{1/{\theta}}$. Thus, the optimal number of initial rejections is approximately $k = N/e^{1/{\theta}}$ for $N$ sufficiently large. A plot is shown in Figure \[f:4\].

$$\includegraphics[scale=0.3]{ewens_thetak}$$

Optimal probability of success
------------------------------

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

\[t:eds\] For all $N$ and $k \geq 1$, we have $$W(N,k) = {\theta}{\{k\}!} \frac{(N-1)!}{(k-1)!} \sum_{i=k}^{N-1} \frac{1}{i}.$$ When $k = 0$, we have $W(N,0) = (N-1)! {\theta}$.

This is straightforward to prove by induction from Theorem \[t:W\].

Since the optimal value of $k$ satisfies ${\theta}= \left(\sum_{i=k}^{N-1}
\frac{1}{i}\right)^{-1}$ we can cancel it and the optimal probability $W$ simplifies to $$\frac{W(N,k)}{{\{N\}!}} = \frac{{\{k\}!}}{(k-1)!} \frac{(N-1)!}{{\{N\}!}}.$$

When ${\theta}$ is an integer, this is just a ratio of binomial coefficients, but for arbitrary positive real ${\theta}$ we use gamma functions (see e.g. [@NIST]). By iterating the recurrence ${\Gamma}(z+1)=z{\Gamma}(z)$ we obtain ${\{N\}!} = \frac{{\Gamma}({\theta}+N)}{{\Gamma}({\theta})}$. Hence, $$\frac{{\{k\}!}}{(k-1)!} \frac{(N-1)!}{{\{N\}!}}
= \frac{{\Gamma}({\theta}+k)}{{\Gamma}({\theta})(k-1)!} \frac{{\Gamma}({\theta})(N-1)!}{{\Gamma}({\theta}+N)}
= \frac{{\Gamma}({\theta}+k)}{{\Gamma}(k)} \frac{{\Gamma}(N)}{{\Gamma}({\theta}+N)}.$$ Using $\lim_{x \rightarrow \infty} \frac{{\Gamma}(x+{\theta})}{{\Gamma}(x) x^{\theta}} = 1$, we get $$\lim_{N \rightarrow \infty} \frac{{\Gamma}({\theta}+k)}{{\Gamma}(k)} \frac{{\Gamma}(N)}{{\Gamma}({\theta}+N)}
= \lim_{N \rightarrow \infty} \frac{k^{\theta}}{N^{\theta}} 
= \lim_{N \rightarrow \infty} \left(\frac{k}{N}\right)^{{\theta}}  
= \left(\frac{1}{e^{1/{\theta}}}\right)^{\theta}= 1/e.$$ Remarkably, this probability of success is independent of ${\theta}$.

Results for Mallows distribution {#s:m}
================================

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

Let ${[N]}$ be the polynomial in ${\theta}$ defined by $1+{\theta}+{\theta}^2+\cdots+{\theta}^{N-1}$. Let ${[N]!}$ be the polynomial in ${\theta}$ defined by $${[N]!} =  {[N]} {[N-1]} \cdots {[1]}.$$

We have $${[N]!} = \sum_{\pi \in {\mathfrak{S}}_N} \theta^{\# \text{inversions in } \pi}.$$

This is straightforward to prove using induction since we may extend each permutation $\pi$ of $N-1$ by placing one of the values $i = 1, 2, \ldots, N$ in the last position and arranging the complementary values according to $\pi$. This creates $N-i$ new inversions, so contributes ${[N]} {[N-1]!}$ to ${[N]!}$.

Let us redefine $$W(N,k) = \sum_{k\text{-winnable } \pi \in {\mathfrak{S}}_N} {\theta}^{\#\text{inversions in } \pi}$$ for the Mallows distribution. Our next result provides a recursive description for these polynomials.

\[t:mW\] We have $$W(N,k) = {\theta}{[N-1]} W(N-1,k) + {\theta}^{N-k-1} {[k]} {[N-2]!}$$ with initial conditions $W(1, 0) = 1$ and $W(N,N) = 0$.

We have two cases for the $k$-winnable permutations $\pi \in {\mathfrak{S}}_{N}$.

-   If the last position contains one of the values $i = 1, 2, \ldots,
            N-1$, then it contributes $N-i$ to the inversion count and we may view the complementary values as some $k$-winnable $\widetilde{\pi} \in
            {\mathfrak{S}}_{N-1}$. Hence, these contribute ${\theta}{[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 $\pi$ to be $k$-winnable. These choices for the position of value $N-1$ contribute ${\theta}^{N-k-1} {[k]}$. 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.

\[c:mm\] We have $$W(N,k) = {\theta}^{N-k-1} {[N-1]!} \sum_{i=k}^{N-1} \frac{ {[k]} }{ {[i]} }$$ for $k > 0$ and $W(N,0) = {\theta}^{N-1} {[N-1]!}$.

This is straightforward to prove by induction on $N$ from Theorem \[t:mW\].

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 \[f:m1\] shows a plot of the optimal success probability for various values of ${\theta}< 1$ based on the following theorem.

$$\includegraphics[scale=0.3]{mallows_tleq1}$$

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

Rewriting the probability $W(N,k)/{[N]!}$ from Corollary \[c:mm\] gives $${\theta}^{N-k-1} \frac{ {[k]} }{ {[N]} } \sum_{i=k}^{N-1} \frac{1}{{[i]}} =
(1-{\theta}) {\theta}^{N-k-1} \frac{1-{\theta}^k}{1-{\theta}^N} \sum_{i=k}^{N-1} \frac{ 1 }{ 1-{\theta}^i }$$ $$= \frac{{\theta}^N-{\theta}^{N-1}-{\theta}^{N-k}+{\theta}^{N-k-1}}{1 - {\theta}^N} \sum_{i=k}^{N-1} \frac{ 1 }{
1-{\theta}^i }.$$

For fixed ${\theta}\in (0,1)$, as $N$ becomes large, the fraction tends to ${\theta}^{N-k-1}(1 - {\theta})$ and the terms in the series become close to $1$ so the probability reduces to ${\theta}^{N-k-1}(1-{\theta})(N-k)$. By continuity, 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 \rightarrow \infty} W(N,k)/{[N]!}
= j {\theta}^{j-1} (1-{\theta})$. Differentiating with respect to $j$ and set equal to zero, we solve to obtain the optimal $j = -1/(\ln {\theta})$. For ${\theta}< 1/e$, we have $j < 1$ but we cannot reject more than $N-1$ candidates so max appears in the expression.

The case where ${\theta}> 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 ${\theta}$ which would seem to limit the durability of any “policy advice” derived from the classical model (such as e.g. [@golden]).

$$\includegraphics[scale=0.25]{mallows_g1k1} \includegraphics[scale=0.25]{mallows_g1k2} \includegraphics[scale=0.25]{mallows_g1k3}$$

\[c:mm2\] Fix ${\theta}> 1$ and an integer $k \geq 1$. Then, $$\lim_{N \rightarrow \infty} \frac{W(N,k)}{{[N]!}} = ({\theta}-1) \frac{{\theta}^k - 1}{{\theta}^{k+1}} \sum_{i=k}^{\infty} \frac{1}{{\theta}^i - 1}.$$ In particular, we approach a single asymptotic distribution as $N {\rightarrow}\infty$ 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 $$\frac{W(N,k)}{{[N]!}} = \frac{{\theta}^N-{\theta}^{N-1}-{\theta}^{N-k}+{\theta}^{N-k-1}}{{\theta}^N - 1} \sum_{i=k}^{N-1} \frac{ 1 }{ {\theta}^i - 1 }.$$ For fixed ${\theta}> 1$, as $N$ becomes large, the fraction tends to $1-{\theta}^{-1}-{\theta}^{-k}+{\theta}^{-(k+1)} = (1-{\theta}^{-1})(1 - {\theta}^{-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 \rightarrow \infty$. As $k$ becomes large, the series tends to zero, being approximately $\sum_{i=k}^\infty (1/{\theta})^i = {\theta}^{-k}/(1-{\theta}^{-1})$. Therefore, the optimal asymptotic probability will occur for some fixed $k$ (depending on ${\theta}$).

Figure \[f:m2\] shows some plots (obtained numerically) of the optimal success probabilities for various values of ${\theta}$ and $k$. For any particular value of ${\theta}> 1$, one can explicitly compute the probabilities in Corollary \[c:mm2\] and find the optimal strategy $k$. For example, it appears that $k = 1$ is optimal for all ${\theta}> 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 ${\theta}\approx 1.55$ (for which $k = 1$ is the optimal strategy). It would be interesting to determine this maximum more precisely.

Acknowledgements {#acknowledgements .unnumbered}
================

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

[ABNP16]{}

Nicolas Auger, Mathilde Bouvel, Cyril Nicaud, and Carine Pivoteau, *Analysis of algorithms for permutations biased by their number of records*, Proceedings of the 27th [I]{}nternational [C]{}onference on [P]{}robabilistic, [C]{}ombinatorial and [A]{}symptotic [M]{}ethods for the [A]{}nalysis of [A]{}lgorithms—[A]{}of[A]{}’16, Jagiellonian Univ., Dep. Theor. Comput. Sci., Kraków, 2016, p. 12. [MR ]{}[3817514]{}

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. [MR ]{}[2032426]{}

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

Harry Crane, Stephen DeSalvo, and Sergi Elizalde, *The probability of avoiding consecutive patterns in the [M]{}allows distribution*, Random Structures Algorithms **53** (2018), no. 3, 417–447. [MR ]{}[3854041]{}

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

Aaron Fowlkes and Brant Jones, *Positional strategies in games of best choice*, [arXiv:1810.09887 \[math.CO\]]{} (2018).

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

Martin Gardner, *New mathematical diversions*, revised ed., MAA Spectrum, Mathematical Association of America, Washington, DC, 1995. [MR ]{}[1335231]{}

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

Brant Jones, *Avoiding patterns and making the best choice*, [ arXiv:1812.00963 \[math.CO\]]{} (2018).

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

Thomas Kesselheim, Robert Kleinberg, and Rad Niazadeh, *Secretary problems with non-uniform arrival order*, S[TOC]{}’15—[P]{}roceedings of the 2015 [ACM]{} [S]{}ymposium on [T]{}heory of [C]{}omputing, ACM, New York, 2015, pp. 879–888. [MR ]{}[3388268]{}

Frank W. J. Olver, Daniel W. Lozier, Ronald F. Boisvert, and Charles W. Clark (eds.), *N[IST]{} 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). [MR ]{}[2723248]{}

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

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. [MR ]{}[929508]{}

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