Modern Stochastics: Theory and Applications

Recommender systems and information retrieval platforms rely on ranking algorithms to present the most relevant items to users, thereby improving engagement and satisfaction. Assessing the quality of these rankings requires reliable evaluation metrics. Among them, Mean Average Precision at cutoff k (MAP@k) is widely used, as it accounts for both the relevance of items and their positions in the list for some groups of users.

Multisets are like sets, except that they can contain multiple copies of their elements. If there are ${n_{i}}$ copies of i, $1\le i\le t$, in multiset ${M_{t}}$, then there are $\left(\genfrac{}{}{0.0pt}{}{{n_{1}}+\cdots +{n_{t}}}{{n_{1}},\dots ,{n_{t}}}\right)$ possible permutations of ${M_{t}}$. Knuth showed how to factor any multiset permutation into cycles. For fixed ${n_{i}}$, $i\ge 1$, we show how to adapt the Chinese restaurant process, which generates random permutations on n elements with weighting ${\theta ^{\# \hspace{0.1667em}\mathrm{cycles}}}$, $\theta \gt 0$, sequentially for $n=1,2,\dots $, to the multiset case, where we fix the ${n_{i}}$ and build permutations on ${M_{t}}$ sequentially for $t=1,2,\dots $. The number of cycles of a multiset permutation chosen uniformly at random, i.e. $\theta =1$, has distribution given by the sum of independent negative hypergeometric distributed random variables. For all $\theta \gt 0$, and under the assumption that ${n_{i}}=O(1)$, we show a central limit theorem as $t\to \infty $ for the number of cycles.