Recommendation systems play a pivotal role in modern digital environments, designed to predict and suggest items such as movies on streaming platforms, products on e-commerce sites, or news articles on media platforms based on users’ preferences and historical interactions. These systems leverage sophisticated algorithms that analyze user behavior, item attributes, and contextual data to provide personalized recommendations, thereby enhancing user satisfaction and engagement.

Ranking algorithms are fundamental to recommendation systems, as they determine the order in which items are presented to users. These algorithms prioritize relevant items and arrange them in a sequence designed to maximize user engagement and satisfaction.

Metrics that assess the effectiveness of these rankings are essential for evaluating algorithmic performance. Among various evaluation metrics, Average Precision at k (AP@k) plays a crucial role in recommendation systems due to its ability to assess the precision of recommended items up to a specified rank k. It not only accounts for the relevance of the items but also their position in the recommendation list, providing a comprehensive evaluation of ranking effectiveness. A review of this and other relevant metrics is provided in [7, 9], offering a deeper exploration of the evaluation methods.

AP@k is particularly important for evaluations of algorithms developed for scenarios where users are more likely to interact with top-ranked items, like book propositions on Amazon, short videos on YouTube, or news on Google News. While AP@k evaluates the ranking quality for individual users, MAP@k provides an overall measure of the algorithm’s performance across the entire user base, giving a more generalized assessment of the system’s ability to rank relevant items consistently.

There are a variety of different ranking methods, but none of them is the best. The effectiveness of a ranking algorithm depends on the particular problem, the data available, what rank must represent, and what properties are needed. The most well-known so far is the PageRank method used in search engines like Google (for details, see [4, 5] and the references therein).

In this paper, we calculated the closed-form expressions for the expected value and the variance of AP@k under random rankings. Since MAP@k averages user-level AP@k, the expectation of AP@k specifies the random baseline for the metric MAP@k, whereas the variance determines the scale of random fluctuations around that baseline. For a good ranking algorithm, MAP@k is expected to be significantly greater than the expectation of AP@k. This baseline supports principled benchmarking and guides the optimization of recommendation strategies. Together, these basic probabilistic parameters can be used for testing hypotheses on whether the algorithm is substantially better than just random ranking.

The paper is organized as follows. Section 2 introduces two evaluation settings that we consider (offline and online) in connection with corresponding randomization models and explains their practical relevance. Section 3 provides formal definitions of AP@k and MAP@k and clarifies their relationship. Sections 4 and 5 present closed-form expressions for the expectation and variance of AP@k in both offline and online scenarios. Section 6 presents some numerical examples and simulation results and comparative tables that illustrate the particularities of AP@k in several scenarios, whereas Section 7 summarizes the main findings and suggests directions for future research. The proofs of the theorems from the Sections 4 and 5 are placed in the Appendix.

In the evaluation of recommendation systems, two principal approaches are widely used: offline evaluation and online one. A comprehensive discussion of these methods can be found in [1, 6]. In both these approaches, we restrict ourselves to treating item relevance as binary — classifying items as relevant or not — but they differ in the methodology.

It is important to note that the notion of relevance itself is not universal and is typically defined by the underlying business objective of the system. Depending on the task, relevance may correspond to different user actions, such as clicking on an item, visiting a product page, completing a purchase, or consuming a certain fraction of the content. For instance, in a recommendation system optimized for traffic generation, a click or page visit may be treated as a relevant outcome, whereas in a revenue-oriented setting, relevance may be defined by a completed transaction. Consequently, while AP@k and MAP@k assume a binary relevance indicator, the definition of this indicator is inherently task-dependent and reflects the specific optimization goal of the application.

Offline evaluation relies on historical data, where the relevance of items for each user is known. It is particularly useful when comprehensive, labeled data, such as historical interactions, is available, making it possible to test recommendation algorithms in a controlled environment. In this case, we can design a training set and a test set according to our preferences. The common practice is to group the users who have the same number of relevant items in the list in order to make them homogeneous in some sense and comparable. We can explore several groups with a different number m of relative items in the list.

What if we do not use the advanced ranking algorithms but propose the items to the user randomly? And what does it mean by ‘randomly’? What will the expected value of AP@k be in this case? First of all, we need to define the random experiment that can be utilized under such a scenario. We can consider the experiment in which one random result differs from another only at the places where m relevant elements (no matter which) are located among N available places. It is stochastically equivalent to sampling m items from N with equal probabilities and without replacement (SWOR).

The offline evaluation is easier and reproducible. But it does not always predict online behavior and trends. Therefore, the offline evaluation is usually followed by the online evaluation. Online evaluation attempts to evaluate recommender systems by a method called A/B testing, where a part of users are served by recommender system A and another part of users by recommender system B in real-time mode, and then compare them with each other. We refer the interested reader to [1, 6] for more details on this issue. In A/B testing, one of the systems (i.e., B) can propose the items randomly. With time, all the recommender algorithms degrade, and the level of their degradation is regularly monitored, but instead of conducting an online test with random sorting of recommendations, which is quite costly and leads to reduced user satisfaction, it can be simulated using the randomization model.

We propose a model that also treats item relevance as binary. But it is unreasonable to require a predefined number of relevant items m within a set of N items per user, as was in the offline evaluation framework, since the model will be unrealistic. Instead, it is important to ensure that every participant in the sample testing the recommender system is shown at least k items from the recommendation list. For reliable evaluation in this scenario, two key conditions must be met: the pool of items used to generate the recommendation list must be sufficiently large, and the proportion of relevant items should remain approximately stable across all users in the treated group. In practice, it means that we need to choose users with similar characteristics, like gender or age. This comparison is facilitated by the probability p, which represents the likelihood of each item being relevant. The probability p can be estimated from the historical data. Given this probability, it is possible to calculate the expected value and the variance of the evaluation metric AP@k under random item ranking.

One possible random experiment that can be considered to fit this setting is Bernoulli sampling. It assumes that we have N items, and every item can be either relevant or not, independently of each other, with a probability of being relevant equal to p. This is equivalent to sampling from N items, where m = p N (m is assumed to be natural) with equal probabilities and with replacement (SWR). The number of relevant items for each user under this model is not fixed, but on average it is equal to N p = m.

Having established the context of offline and online evaluation, we now turn to the formal definition of the metrics Average Precision at k (AP@k) and Mean Average Precision at k (MAP@k), which are central to this paper. To begin, we first define AP@k for a single user, which serves as the building block for MAP@k.

The Average Precision at k measures the ranking quality of relevant items proposed to one user by averaging precision values at positions where relevant items appear. Formally, it is defined as: (1) A P @ k = 1 k ∑ i = 1 k P @ i · I i , where:

In this general form, the denominator k normalizes the metric over the entire recommendation list shown to the user. However, when the total number of relevant items m is smaller than k, a modified normalization factor, min ( m , k ), should be used: (2) A P @ k = 1 min ( m , k ) ∑ i = 1 k P @ i · I i .

This adjustment ensures that the metric appropriately handles situations where there are fewer relevant items than the length of the recommendation list, avoiding artificially deflated scores. Without this modification, even in the best scenario – where all m relevant items are ranked in the top positions – the AP@k score would never reach 1, because the denominator would be larger than m, preventing the score from reaching its maximum value.

As it was mentioned before, MAP@k aggregates the AP@k values across all users in the dataset and provides a more comprehensive evaluation of the recommendation system, thereby reflecting the system’s overall performance of ranking. Formally, MAP@k is computed as: (3) M A P @ k = 1 | U | ∑ u ∈ U A P @ k u , where:

Turning to the interpretation of the MAP@k metric, a high MAP@k value indicates that most users encounter relevant items ranked highly, reflecting an effective recommendation system. Conversely, a low MAP@k suggests that relevant items appear lower, signaling a less efficient algorithm. The metric ranges from 0 to 1, where 1 means all relevant items are within the top-k positions, and 0 means none are included. However, for a comprehensive evaluation, it is essential to compare the MAP@k score with the expected value derived from random recommendation generation. While one might assume that this expected value equals the proportion of relevant items in the collection, this is not the case. As demonstrated by Yves Bestgen in his work [2], the expected average precision for random recommendations is more complex and varies depending on various factors such as the number of relevant items in the list and other characteristics. In the current study, we derive precise formulas for the calculation of random baselines for both random ranking algorithms described above (sampling without and with replacement).

If we want to determine how much the algorithm outperforms random chance, we can compare MAP@k calculated for the developed ranking algorithm with the expected value of AP@k if randomness is imposed by sampling without replacement. The expected AP@k alone is not sufficient for a comprehensive evaluation, but it provides the crucial baseline against which meaningful improvements can be interpreted. In addition, the variance quantifies the spread of AP@k values around this baseline, completing the picture by indicating the scale of random fluctuations.

We begin with the offline evaluation setting described in Section 2, corresponding to sampling without replacement. In this case, among N items, exactly m are relevant, and one random outcome differs from another only by the positions of the m relevant items in the ranking. Equivalently, the random ranking can be viewed as a uniformly random permutation of all N items, so that the m relevant items are placed at random positions. From the mathematical point of view, this means that for each item j = 1 , 2 , … , N we define a binary random variable I j , with I j = 1 if the item at position j is relevant and I j = 0 otherwise. Furthermore, ∑ j = 1 N I j = m and the random variables I 1 , I 2 , … , I N are not independent.

Under this model, the probability that the j-th item is relevant can be calculated as P ( I j = 1 ) = C N − 1 m − 1 C N m = m N .

So, E ( I j ) = m / N for every j and the random variable ∑ j = 1 i I j , which counts the number of relevant items among the first i items, follows the Hypergeometric distribution with parameters N, m and i. Moreover E ( P @ i ) = 1 i ∑ j = 1 i E ( I j ) = m N , i = 1 , … , k . In this case, we should compute A P @ k according to formula (2), where the normalization is made by min ( m , k ).

Hereafter, for the identification that the expectations are calculated with respect to different random models, we used different subscripts (SWOR and SWR) in the theorems’ formulation. In the proofs placed in Appendix A, we omit these subscripts to simplify the formulas.

The explicit expressions for the expected value E ( A P @ k ) and the variance Var ( A P @ k ) under the random model corresponding to sampling without replacement (SWOR) are established in the following theorem. Theorem 1.

Assume that among N available items, exactly m are relevant for each user and their places are chosen randomly with equal probability by sampling without replacement. Then the expectation and the variance of A P @ k with respect to all possible random results are equal to (4) E S W O R ( A P @ k ) = m N · min ( k , m ) m − 1 N − 1 k + N − m N − 1 H k , Var S W O R ( A P @ k ) = 1 min ( k , m ) 2 m N [ k ( C + 2 ( E − F ) + ( k − 1 ) G ) + + H k ( B − 2 ( E − k F ) ) + H k 2 · D + H k 2 ( A − D ) ] , where A = 1 − m N − m − 1 N − 1 3 − 2 m − 2 N − 2 − m N 2 − m − 1 N − 1 ; B = m − 1 N − 1 3 1 − m − 2 N − 2 − 2 m N 1 − m − 1 N − 1 ; C = m − 1 N − 1 m − 2 N − 2 − m ( m − 1 ) N ( N − 1 ) ; D = m − 1 N − 1 2 − 5 m − 2 N − 2 + 3 ( m − 2 ) ( m − 3 ) ( N − 2 ) ( N − 3 ) − m N 1 − m − 1 N − 1 2 ; E = m − 1 N − 1 3 m − 2 N − 2 1 − m − 3 N − 3 − m N 1 − m − 1 N − 1 ; F = m − 1 N − 1 m − 2 N − 2 1 − m − 3 N − 3 − m N 1 − m − 1 N − 1 ; G = m − 1 N − 1 ( m − 2 ) ( m − 3 ) ( N − 2 ) ( N − 3 ) − m N m − 1 N − 1 ; H k = ∑ i = 1 k 1 i ; H k ( 2 ) = ∑ i = 1 k 1 i 2 .

We now turn to the online evaluation setting described in Section 2. Here, we assume that each item is relevant to a user with a constant probability p. The randomness can be modeled as a sequence of independent Bernoulli trials, or equivalently, as sampling with replacement (SWR), where each item has probability p of being sampled. In this case, the decision whether a recommendation is relevant is assumed to be independent for each item. Moreover, we assume a uniform relevance probability p for all recommendations and all users. These probabilistic assumptions differ from the offline case and lead to distinct formulas for the expectation and variance of AP@k.

From a mathematical point of view, this means that for each recommendation j = 1 , 2 , … , N, we define the random variables I j = 1 if it is relevant and I j = 0 otherwise, as in the previous section. But here the random variables I 1 , I 2 , … , I N are independent with mean E ( I j ) = p and variance Var ( I j ) = p ( 1 − p ), where p is assumed to be known. Of course, this assumption is quite strong and can be applied only when the users are relatively similar (homogeneous), as described in Section 2 for the online evaluation scenario.

Under these assumptions and notations, we have the following: P @ i = 1 i ∑ j = 1 i I j , E ( P @ i ) = 1 i ∑ j = 1 i E ( I j ) = p , and A P @ k = 1 k ∑ i = 1 k P @ i · I i .

The basic benchmarking characteristics for M A P @ k under random recommendations corresponding to the sampling with replacement are presented in the following theorem. Theorem 2.

If, for each user, every item is assumed to be independently relevant with constant probability p and the places for the relevant items in the list of N items are chosen using sampling with replacement with probability p, then the expectation and the variance of A P @ k are equal to (5) E S W R ( A P @ k ) = p p + 1 − p 1 k H k ; Var S W R ( A P @ k ) = 5 k · p 3 ( 1 − p ) + 1 k 2 · p ( 1 − p ) p ( 1 − 2 p ) ( 3 H k + H k 2 ) + ( 1 − p ) ( 1 − 3 p ) H k 2 . Here H k = ∑ i = 1 k 1 i is the k-th harmonic number and H k 2 = ∑ i = 1 k 1 i 2 is the k-th partial sum of the 2nd order harmonic series as well as in Theorem 1.

Before presenting some practical results, it is helpful to summarize the key differences in the formulas for the offline and online settings. In the offline case, the distribution of AP@k depends on the total number of items N, the number of relevant items m, and the cut-off k that specifies how many top-ranked positions are taken into account. This reflects the fact that evaluation is performed on a finite set of items, where exactly m out of N are relevant and their positions in the ranking determine the outcome. In the online setting, by contrast, the parameter N does not appear in the formulas, since evaluation is restricted to the top-k recommendations and each of them is modeled as an independent Bernoulli trial with relevance probability p. This makes the outcome depend only on k and p, regardless of the overall size of the candidate pool, which in practice may be very large. Conceptually, the probability p plays a role analogous to the ratio m / N in the offline case: while offline evaluation fixes the proportion of relevant items deterministically, online evaluation assumes it probabilistically.

To cover a representative range of conditions, N = 50 is fixed, and several choices of m and k are examined. The half-density case ( m = 25) with varying cut-offs illustrates the situations m > k, m = k, and m < k. Lower prevalences ( m = 10 and m = 2) are also included along with a high-prevalence setting ( m = 35, corresponding to p > 0.5). These scenarios span the spectrum from very sparse to very dense relevance distributions, thereby testing the formulas under diverse conditions. The selected configurations are summarized in Table 1.

Table 2 reports the theoretical (derived from the formulas in Sections 4 and 5) means and variances of AP@k for the selected scenarios. The offline and online settings are placed side by side, allowing examination of their behavior under comparable conditions and observation of where the two randomization schemes produce similar outcomes and where differences emerge.

As seen in Table 2, the comparison between offline (SWOR) and online (SWR) shows no uniform pattern: in some scenarios the two models behave very similarly, while in others their outcomes diverge noticeably. The observed differences reflect the min ( m , k ) normalization in offline evaluation and the independence structure of online sampling. Together, these results provide a clear basis for interpreting MAP@k under the random rankings.

In addition to the values reported in Table 2, Figures 1 and 2 show the simulated distributions of AP@k for two representative scenarios. These examples illustrate how SWOR and SWR can differ not only in their means but also in their variability.

In Scenario A3 ( m < k), the distributions are shifted relative to each other: the offline case yields systematically higher values due to normalization by min ( m , k ), while the online case, which models relevance probabilistically, results in lower means.

In Scenario C (very low prevalence), the contrast lies in variability. The SWR distribution is sharply concentrated, reflecting that almost always no relevant items appear in the top-k, whereas the SWOR distribution remains wider because the fixed number of relevant items can still occupy different positions in the ranking.

The results obtained clarify what levels of AP@k are expected under random ranking and how much variability surrounds them. From a practical standpoint, these findings offer two key insights. First, the expected value of AP@k serves as a clear reference point against which observed performance can be compared. Second, the variance quantifies the random fluctuations around this reference, helping to distinguish genuine improvements from chance outcomes. Together, expectation and variance can be used to build the statistical test to check the hypothesis on whether the studied new ranking algorithm is significantly better than a random one or not by comparing the empirical MAP@k obtained from offline or online evaluation procedure with E ( A P @ k ). But this task is left for future research. It will also be interesting to extend this analysis to other related metrics and investigate how statistical testing frameworks can build on these results for a robust comparison of ranking systems.