English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In the classical secretary problem, $n$ ranked items arrive one by one, andeach item's rank relative to its predecessors is noted. The observer mustselect or reject each item as it arrives, with the object of selecting the itemof highest rank. For $M_n\in\{0,1,\cdots, n-1\}$, let $\mathcal{S}(n,M_n)$denote the strategy whereby the observer rejects the first $M_n$ items, andthen selects the first later-arriving item whose rank is higher than that ofany of the first $M_n$ items (if such an item exists). If the ranked itemsarrive in a uniformly random order, it is well-known that the limiting optimalprobability of success is $\frac1e$, which occurs if $M_n\sim\frac ne$. It hasbeen shown that when the ranked items arrive according to certain non-uniformdistributions on the set of permutations, $\frac1e$ serves as a lower bound forthe optimal probability. There is a fundamental reason for this phenomenon. Weconsider certain distributions for which that reason does not apply. We beginby noting a cooked-up class of distributions for which $\mathcal{S}(n,M)$yields the lowest possible probability of success -- namely $\frac1n$, for all$M$. We then consider the uniform distribution over all permutations avoiding aparticular pattern of length three. In the case of the pattern 231 or 132, forany choice of $M_n$, the strategy $\mathcal{S}(n,M_n)$ yields the very sameprobability of success; namely $\frac{n+1}{2(2n-1)}$, which gives a limitingprobability of $\frac14$. For the pattern 213, the optimal strategy is obtainedfor $M\in\{0,1\}$, also yielding a limiting probability of $\frac14$. For thepattern 123, the optimal strategy is obtained for $M=1$, yielding a limitingprobability of $\frac34$. For the other two patterns, 312 and 321, an optimalstrategy will yield a limiting probability of at least $\frac7{16}$.

The secretary problem with items arriving according to a random permutation avoiding a pattern of length three